Leslie V. Foster
Timothy A. Davis
Abstract
The SPQR_RANK package contains routines that calculate the numerical rank of large, sparse, numerically rank-deficient matrices. The routines can also calculate orthonormal bases for numerical null spaces, approximate pseudoinverse solutions to least squares problems involving rank-deficient matrices, and basic solutions to these problems. The algorithms are based on SPQR from SuiteSparseQR (ACM Transactions on Mathematical Software 38, Article 8, 2011). SPQR is a high-performance routine for forming QR factorizations of large, sparse matrices. It returns an estimate for the numerical rank that is usually, but not always, correct. The new routines improve the accuracy of the numerical rank calculated by SPQR and reliably determine the numerical rank in the sense that, based on extensive testing with matrices from applications, the numerical rank is almost always accurately determined when our methods report that the numerical rank should be correct. Reliable determination of numerical rank is critical to the other calculations in the package. The routines work well for matrices with either small or large null space dimensions.
Supplemental Material
Available for Download
Software for Reliable calculation of numerical rank, null space bases, pseudoinverse solutions, and basic solutions using suitesparseQR
- Anderson, E., Bai, Z., Bischof, S., Blackford, L. S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, S., Hammarling, S., McKenney, A., and Sorensen, D. 1999. LAPACK Users' Guide 3rd Ed. SIAM, Philadelphia, PA. Google Scholar
Digital Library
- Berry, M. W. 1994. Computing the sparse singular value decomposition via SVDPACK. In Recent Advances in Iterative Methods, IMA Volumes in Mathematics and its Application, vol. 60, Springer, New York, 13--29.Google Scholar
- Berry, M. W., Heath, M. T., Kaneko, I., Lawo, M., Plemmons, R. J., and Ward, R. C. 1985. An algorithm to compute a sparse basis of the null space. Numer. Math. 47, 4, 483--504.Google ScholarDigital Library
- Bischof, C. H. and Quintana-Ortí, G. 1998. Computing rank-revealing QR factorizations of dense matrices. ACM Trans. Math. Softw. 24, 2, 226--253. Google ScholarDigital Library
- Björck, Å. 1996. Numerical Methods for Least Squares Problems. SIAM, Philadelphia, PA.Google Scholar
- Chan, T. F. and Hansen, P. C. 1990. Computing truncated singular value decomposition least squares solutions by rank revealing QR-factorizations. SIAM J. Sci. Statist. Comput. 11, 3, 519--530. Google ScholarDigital Library
- Chan, T. F. and Hansen, P. C. 1992. Some applications of the rank revealing QR factorization. SIAM J. Sci. Statist. Comput. 13, 3, 727--741. Google ScholarDigital Library
- Coleman, T. F. and Pothen, A. 1986. The null space problem I. complexity. SIAM J. Algebraic Discrete Meth. 7, 4, 527--537. Google ScholarDigital Library
- Coleman, T. F. and Pothen, A. 1987. The null space problem II. algorithms. SIAM J. Algebraic Discrete Meth. 8, 4, 544--563. Google ScholarDigital Library
- Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. Fundamentals of Algorithms Vol. 2. SIAM, Philadelphia, PA. Google ScholarDigital Library
- Davis, T. A. 2011. Algorithm 915, SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization. ACM Trans. Math. Softw. 38. Google ScholarDigital Library
- Davis, T. A. and Hu, Y. F. 2011. The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38. Google ScholarDigital Library
- Demmel, J. W. 1997. Applied Numerical Linear Algebra. SIAM, Philadelphia, PA. Google ScholarDigital Library
- Enting, I. 2002. Inverse Problems in Atmospheric Constituent Transport. Cambridge University Press, Cambridge, UK.Google Scholar
- Fong, D. C. and Saunders, M. A. 2010. LSMR: An iterative algorithm for sparse least-squares problems. Tech. rep. SOL-2010-2, http://www.stanford.edu/group/SOL/reports/SOL-2010-2.pdf, Stanford.Google Scholar
- Foster, L. V. 1986. Rank and null space calculations using matrix decomposition without column interchanges. Linear Algebra Appl. 74, 47--71.Google ScholarCross Ref
- Foster, L. V. 1990. The probability of large diagonal elements in the QR factorization. SIAM J. Sci. Statist. Comput. 11, 3, 531--544. Google ScholarDigital Library
- Foster, L. V. 2007. Row echelon form is (usually) accurate after all. In Proceedings of International Linear Algebra Society Annual Conference. http://www.math.sjsu.edu/∼foster/ilas-07-17-2007.pdf.Google Scholar
- Foster, L. V. 2009. Calculating the Rank of a Matrix using SPNRANK. http://www.math.sjsu.edu/singular/matrices/software/SJsingular/Doc/spnrank.pdf.Google Scholar
- Foster, L. V. and Botev, N. B. 2009. San Jose State University Singular Matrix Data Base. http://www.math. sjsu.edu/singular/matrices/.Google Scholar
- Foster, L. V. and Kommu, R. 2006. Algorithm 853: An efficient algorithm for solving rank-deficient least squares problems.ACM Trans. Math. Softw. 32, 1. Google ScholarDigital Library
- Gilbert, J. R. and Heath, M. T. 1987. Computing a sparse basis for the null space. SIAM J. Algebraic Discrete Meth. 8, 3, 446--459. Google ScholarDigital Library
- Gill, P. E., Murray, W., and Saunders, M. A. 2005. SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM Rev. 47, 1, 99--131. Google ScholarDigital Library
- Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations 3rd Ed. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD. Google ScholarDigital Library
- Gotsman, C. and Toledo, S. 2008. On the computation of null spaces of sparse rectangular matrices. SIAM J. Matrix Anal. Appl. 30, 2, 445--463. Google ScholarDigital Library
- Hansen, P. C. 1994. Regularization tools: A MATLAB package for analysis and solution of discrete ill-posed problems. Numer. Algor. 6, 1--2, 1--35.Google ScholarCross Ref
- Hansen, P. C. 1998. Rank-Deficient and Discrete Ill-Posed Problems. SIAM Monographs on Mathematical Modeling and Computation, SIAM, Philadelphia, PA. Google ScholarDigital Library
- Heath, M. T. 1982. Some extensions of an algorithm for sparse linear least squares problems. SIAM J. Sci. Statist. Comput. 3, 2, 223--237.Google ScholarDigital Library
- Higham, N. J. 1991. Algorithm 694: A collection of test matrices in MATLAB. ACM Trans. Math. Softw. 17, 3, 289--305. Google ScholarDigital Library
- Higham, N. J. 2002. Accuracy and Stability of Numerical Algorithms 2nd Ed. SIAM, Philadelphia, PA. Google ScholarDigital Library
- Kahan, W. 1966. Numerical linear algebra. Canad. Math. Bul l. 9, 757--801.Google Scholar
- Kuczyński, J. and Woźniakowski, H. 1992. Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl. 13, 4, 1094--1122. Google ScholarDigital Library
- Lehoucq, R. B., Sorensen, D. C., and Yang, C. 1998. ARPACK Users' Guide. Software, Environments, and Tools Vol. 6. SIAM, Philadelphia, PA.Google Scholar
- Li, T. Y. and Zeng, Z. 2005. A rank-revealing method with updating, downdating and applications. SIAM J. Matrix Anal. Appl. 26, 4, 918--946. Google ScholarDigital Library
- Paige, C. C. and Saunders, M. A. 1982. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Softw. 8, 1, 43--71. Google ScholarDigital Library
- Parlett, B. N. 1980. The Symmetric Eigenvalue Problem. N.J. Prentice-Hall Series in Computational Mathematics, Prentice-Hall Inc., Englewood Cliffs. Google ScholarDigital Library
- Pierce, D. J. and Lewis, J. G. 1997. Sparse multifrontal rank revealing QR factorization. SIAM J. Matrix Anal. Appl. 18, 1, 159--180. Google ScholarDigital Library
- Saunders, M. 2006. LUSOL: A basis package for constrained optimization. Tech. rep., SCCM, Stanford University. http://www.stanford.edu/group/SOL/talks/saunders-LUSOL-linopt2006.pdf.Google Scholar
- Stewart, G. W. 1981. On the implicit deflation of nearly singular systems of linear equations. SIAM J. Sci. Statist. Comput. 2, 2, 136--140.Google ScholarDigital Library
- Stewart, G. W. and Sun, J. G. 1990. Matrix Perturbation Theory. Computer Science and Scientific Computing, Academic Press Inc., Boston, MA.Google Scholar
- Vogel, C. R. and Wade, J. G. 1994. Iterative SVD-based methods for ill-posed problems. SIAM J. Sci. Comput. 15, 3, 736--754. Google ScholarDigital Library
Index Terms
- Algorithm 933: Reliable calculation of numerical rank, null space bases, pseudoinverse solutions, and basic solutions using suitesparseQR
Recommendations
Algorithm 980: Sparse QR Factorization on the GPU
Sparse matrix factorization involves a mix of regular and irregular computation, which is a particular challenge when trying to obtain high-performance on the highly parallel general-purpose computing cores available on graphics processing units (GPUs). ...
Algorithm 915, SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization
SuiteSparseQR is a sparse QR factorization package based on the multifrontal method. Within each frontal matrix, LAPACK and the multithreaded BLAS enable the method to obtain high performance on multicore architectures. Parallelism across different ...
Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate
CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AAT, updating/downdating a sparse Cholesky factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b, ...
Reviews
Sanzheng Qiao
The rank is one of the major characteristics of a matrix. In practice, the rank is not clear cut due to measurement errors and/or noise. Thus, determining the numerical rank of a matrix is an important problem. Many applications require numerical rank, for example, filtering noise in image processing. Basically, the problem of determining numerical rank is to separate small singular values from large ones, which can be difficult when the gap between small and large may not be obvious. There are software packages that compute numerical rank, for example, SPQR from SuiteSparseQR. In this paper, based on SPQR, the authors propose a package SPQR_RANK, which is an improvement of SPQR in that it returns an indicator of the correctness of the computed numerical rank and uses implicit sparse representation of a null space to reduce the memory requirement. It is also an extension to SPQR in that it produces linear least squares solutions, an orthonormal basis for the numerical null space of a matrix, and the complete orthogonal decomposition (COD) of a matrix. The key to the indicator in the package is the estimates of the bounds for the errors between the estimated singular values s i and the exact singular values . The error bounds used in the package are based on the following equation (page 7:21, equation (18)): As pointed out by the authors, the α in the equation is some singular value, not necessarily the i th singular value used in the package. This discrepancy may cause underestimates or overestimates. Another discrepancy appears on page 7:8, where the authors claim that the computed numerical rank is the exact numerical rank of A + E , where A is the data matrix and the size of the error E is , where is the machine precision. In numerical analysis, the error E , called backward error, depends on the algorithm in addition to the finite precision arithmetic. A backward error analysis is necessary for an upper bound of the size of E . Nevertheless, the package is a practical tool rather than a theoretical work. It is reported in the paper that the package works well despite the discrepancies. The user should be cautious when the gap between the small singular values and the large ones is not obvious, and the differences between the upper bounds and lower bounds returned by the package are big. This package is useful for sparse matrices that are too large for more accurate methods such as the singular value decomposition (SVD) method or SPQR_COD in the package. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments