Accurate Computations with (Singular) Totally Nonnegative Matrices



Current version posted: April, 2018.

Acknowledgement

This software was developed under the support of the San Jose State University Woodward Fund and San Jose State RSCA Funds.

How to cite

  • Plamen Koev, Accurate eigenvalues and zero Jordan blocks of (singular) totally nonnegative matrices. Submitted for publication, 2018.

Installation instructions:

Download and unzip the package STNTool.zip. You may need to recompile mexdlasq1.c by typing "mex mexdlasq1.c -lmwlapack" at the MATLAB prompt.

Description:

This software package can performs matrix computations with potentially singular totally nonnegative matrices to high relative accuracy.
See the above referenced paper from my "Publications" page for a description on how the algorithms work and how to supply the input. All TN matrices are represented by their BIDIAGONAL decompositions. Definitions of the matrices E_i and J_i:
  • The matrix J_i(x,y,z) equals the identity with the only exception of the entries x, y, and z in positions (i,i-1), (i-1,i-1), and (i,i), respectively.
  • E_i(x,y)=J_i(x,y,1);

HRA stands for "High Relative Accuracy." Most functions deliver such accuracy.

Function description:

STNEigenvalues

Syntax: [z,jb]=STNEigenvalues(B,C)
Description: Computes the eigenvalues of the TN matrix A, whose bidiagonal decomposition is stored in [B,C] (i.e., [B,C]=BD(A)) to HRA. z is a vector of eigenvalues, jb is a vector with the sizes of the Jordan blocks corresponding to eigenvalue 0.
Example: [z,jb]=STNEigenvalues([1 0 3; 1 1 0; 1 1 0], [1 1 1; 0 1 1; 1 0 1]) returns z=[3;0;0]; jb=2, meaning that the eigenvalues are 3,0,0 and there is one Jordan block of size 2 for the eigenvalue 0 for the matrix [0 0 0; 1 0 0; 1 1 3], whose bidiagonal decomposition is stored in the matrices passed as arguments.

STNAddToNext

Syntax: [B1,C1]=TNAddToNext(B,C,x,y,i)
Description: If A is a TN matrix, such that [B,C]=BD(A), this function computes the bidiagonal decomposition of E_i(x,y)*A. The procedure is subtraction-free and the result is computed to HRA.
Comments: For the same operation on the columns, work on B',C', and then transpose the result.

STNAddToPrevious

Syntax: [B1,C1]=STNAddToPrevious(B,C,x,y,z,i)
Description: Given [B,C]=BD(A), where A is TN, this routine computes the bidiagonal decomposition of A*J_i(x,y,z). The procedure is subtraction-free and the result is computed to HRA.
Comments: For the same operations on the rows, work on B',C', and then transpose the result.

STNBD

Syntax: [B,C]=STNBD(A)
Description: Computes the bidiagonal decomposition of the matrix A by performing Neville elimination.
Comments: This is the only function in the package that does NOT guarantee high relative accuracy. It is provided as a debugging tool. In exact arithmetic, [B,C]=STNBD(A); A1=STNExpand(B,C); will result in A1=A.

STNDiagonalScale

Syntax: [B1,C1]=STNDiagonalScale(B,C,d,i)
Description: If [B,C]=BD(A), computes the bidiagonal decomposition of the matrix resulting from A by scaling column i by a scalar d>=0. Computed to HRA.

STNExpand

Syntax: A=STNExpand(B,C)
Description: Returns the TN matrix A, whose bidiagonal decomposition is stored in [B,C], to HRA.
Comments: Once A is computed, it is not, in general, possible to recover BD(A) from A to HRA.

STNProduct

Syntax: [B,C]=STNProduct(B1,C1,B2,C2)
Description: Given the bidiagonal decompositions [B1,C1]=BD(F) and [B2,C2]=BD(G), computes the bidiagonal decomposition [B,C] of the product FG to HRA.

STNRandom

Syntax: [B,C]=STNRandom(n,k)
Description: Generates a random bidiagonal decomposition of an non TN matrix with k total zeros among the nontrivial entries of the bidiagonal decomposition.

STNRank

Syntax: r=STNRank(B,C)
Description: Computes the rank of the TN matrix whose bidiagonal decomposition is stored in [B,C].

STNSetToZeroAndSwapWithNext

Syntax: [B1,C1]=STNSetToZeroAndSwapWithNext(B,C,i)
Description: Sets the ith column to 0 and swaps it with the following column. It works fine also if the ith column is already 0. Works only for i

STNSetToZeroAndSwapWithPrevious

Syntax: [B1,C1]=STNSetToZeroAndSwapWithPrevious(B,C,i)
Description: Sets the ith row to 0 and swaps it with row i-1. It works fine also if the ith row is already 0.

STNSubmatrix

Syntax: [B1,C1]=STNSubmatrix(B,C,i)
Description: If [B,C]=BD(A), computes the bidiagonal decomposition of the matrix obtained by erasing column i of A and adding a zero column in position n to HRA.
Comments: A zero column in position n is added to maintain the square shape of the matrix. Removing the last column of B1 and the last column of C1 would result in the theoretical bidiagonal decomposition of the resulting n x (n-1) matrix. Once the routines are updated to handle rectangular matrices, the need for a zero last column will be eliminated.

STNTests

Syntax: STNTests
Description: Performs a number of tests on the routines in this package. It is not meant to be exhaustive and no guarantees either way as it relies on comparison with conventional routines and condition numbers come into play, but a useful tool should you decide to modify or improve the routines.

STNtridiag

Syntax: [B1,C1]=STNtridiag(B,C)
Description: Computes the bidiagonal decomposition of a tridiagonal matrix with the same eigenvalues as the original matrix following the procedure of Cryer (1976).

Plamen Koev
Department of Mathematics, San Jose State University
"firstname" dot "lastname"@sjsu.edu