Rank Detection Methods For Sparse Matrices

    Authors

    J. L. Barlow;U. B. Vemulapati

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    SIAM J. Matrix Anal. Appl.

    Keywords

    SPARSE MATRICES; ORTHOGONAL FACTORIZATION; CONDITION ESTIMATION; NUMERICAL RANK; LEAST-SQUARES PROBLEMS; INCREMENTAL CONDITION ESTIMATION; CONDITION; NUMBER; DECOMPOSITION; ALGORITHM; SET; Mathematics, Applied

    Abstract

    A method is proposed for estimating the numerical rank of a sparse matrix. The method uses orthogonal factorization along with a one-norm incremental condition estimator that is an adaptation of the LINPACK estimator. This approach allows the use of static storage allocation as is used in SPARSPAK-B, 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 SPARSPAK-B. 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 message-passing 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 rank-revealing orthogonal factorizations of Foster [Linear Algebra Appl., 74 (1986), pp. 47-72] and Chan [Linear Algebra Appl., 88/89 (1987), pp. 67-82].

    Journal Title

    Siam Journal on Matrix Analysis and Applications

    Volume

    13

    Issue/Number

    4

    Publication Date

    1-1-1992

    Document Type

    Article

    Language

    English

    First Page

    1279

    Last Page

    1297

    WOS Identifier

    WOS:A1992JQ32900019

    ISSN

    0895-4798

    Share

    COinS