Rank Detection Methods for Sparse Matrices
 Citation data:

SIAM Journal on Matrix Analysis and Applications, ISSN: 08954798, Vol: 13, Issue: 4, Page: 12791297
 Publication Year:
 1992

 EBSCO 1

 CrossRef 10
 Repository URL:
 http://stars.library.ucf.edu/facultybib/2003; http://stars.library.ucf.edu/facultybib1990/403
 DOI:
 10.1137/0613078
 Author(s):
 Publisher(s):
 Tags:
 SPARSE MATRICES; ORTHOGONAL FACTORIZATION; CONDITION ESTIMATION; NUMERICAL RANK; LEASTSQUARES PROBLEMS; INCREMENTAL CONDITION ESTIMATION; CONDITION; NUMBER; DECOMPOSITION; ALGORITHM; SET; Mathematics; Applied
article description
A method is proposed for estimating the numerical rank of a sparse matrix. The method uses orthogonal factorization along with a onenorm incremental condition estimator that is an adaptation of the LINPACK estimator. This approach allows the use of static storage allocation as is used in SPARSPAKB, whereas there is no known way to implement column pivoting without dynamic storage allocation. It is shown here that this approach is probably more accurate than the method presently used by SPARSPAKB. The method is implemented with an overhead of O(n(U) log n) operations, where n(U) is the number of nonzeros in the upper triangular factor of the matrix. In theory, it can be implemented in O(max{n(U), n log n}) operations, but this requires the use of a complicated data structure. It is shown how a variant of this strategy may be implemented on a messagepassing architecture. A prototype implementation is done and tests show that the method is accurate and efficient. Ways in which the condition estimator and the rank detection method can be used are also discussed, along with the rankrevealing orthogonal factorizations of Foster [Linear Algebra Appl., 74 (1986), pp. 4772] and Chan [Linear Algebra Appl., 88/89 (1987), pp. 6782].