×

Rank and null space calculations using matrix decomposition without column interchanges. (English) Zbl 0589.65031

With this paper two stable algorithms are presented which do not require column interchanges for determining the rank and nullity of a matrix. Potential applications to sparse matrix rank determination and more specifically rank determination when sequentially adding columns are discussed.
Reviewer: D.Voukalis

MSC:

65F30 Other matrix algorithms (MSC2010)
15A23 Factorization of matrices

Software:

LSQR; LINPACK; CRAIG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bjork, A.; Duff, I. S., A direct method for the solution of sparse linear least squares problems, Linear Algebra Appl., 34, 43-67 (1980) · Zbl 0471.65021
[2] Bjork, A., Methods for sparse linear least squares problems, (Bunch, J.; Rose, D., Sparse Matrix Computations (1976), Academic), 177-199
[3] Bunch, J.; Nielsen, C., Updating the singular value decomposition, Numer. Math., 31, 111-129 (1978) · Zbl 0421.65028
[4] Cline, A.; Moler, C.; Stewart, G.; Wilkinson, J., An estimate for the condition number of a matrix, SIAM J. Numer. Anal., 16, 368-375 (1979) · Zbl 0403.65012
[5] Dongarra, J.; Moler, C.; Bunch, J.; Stewart, G., LINPACK User’s Guide (1979), SIAM: SIAM Philadelphia
[6] Draper, N.; Smith, H., Applied Regression Analysis (1966), Wiley · Zbl 0158.17101
[7] Duff, I.; Reid, J., A comparison of some methods for the solution of sparse overdetermined systems of linear equations, Inst. Math. Appl., 17, 267-280 (1976) · Zbl 0329.65026
[8] Forney, G., Minimal basis of rational vector spaces, with applications to multivariablesystems, SIAM J. Control, 13, 493-520 (1975) · Zbl 0269.93011
[9] Foster, L., A practical solution to the minimal design problem, IEEE Trans. Automat. Control, AC-24, 449-454 (1979) · Zbl 0416.93040
[10] George, A.; Heath, M., Solution of sparse linear least squares problems using Givens rotations, Linear Algebra Appl., 34, 69-83 (1980) · Zbl 0459.65025
[11] Golub, G.; Klema, V.; Stewart, G., Rank degeneracy and least squares problems, Stanford Univ. Technical Report STAN-CS-76-559 0 (1976)
[12] Golub, G.; Wilkinson, J., Ill-conditioned eigensystems and the computation of the Jordan canonical form, SIAM J. Numer. Anal., 13, 578-619 (1976) · Zbl 0341.65027
[13] Golub, G., Some modified matrix eigenvalue problems, SIAM Rev., 15, 318-334 (1973) · Zbl 0254.65027
[14] Grimes, R.; Lewis, J., Condition number estimators for sparse matrices, SIAM J. Sci. Statist. Comput., 2, 384-388 (1981) · Zbl 0469.65025
[15] Heath, M., Some extensions of an algorithm for sparse linear least squares problems, SIAM J. Sci. Statist. Comput., 3, 223-237 (1982) · Zbl 0483.65027
[16] Kung, S.; Kailath, T., Fast projection methods for minimal design problems in linear systems theory, Automatica, 66, 399-403 (1980) · Zbl 0458.93025
[17] Lawson, C.; Hanson, R., Solving Least Squares Problems (1974), Prentice-Hall · Zbl 0860.65028
[18] Manteuffel, T., An interval analysis approach to rank determination in linear least squares problems, SIAM J. Sci. Statist. Comput., 2, 335-348 (1981) · Zbl 0471.65022
[19] O’leary, D., Estimating matrix condition numbers, SIAM J. Sci. Statist. Comput., 1, 205-209 (1980) · Zbl 0445.65024
[20] Osborne, M., On the computation of stepwise regressions, Austral. Comput. J., 8, 61-68 (1976) · Zbl 0336.65009
[21] Paige, C.; Saunders, M., LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8, 43-71 (1982) · Zbl 0478.65016
[22] Peters, G.; Wilkinson, J., The least squares problem and psuedo-inverses, Comput. J., 13, 309-316 (1970) · Zbl 0195.44804
[23] Rosen, J., Minimum and basic solutions to singular linear systems, SIAM J. Appl. Math., 12, 156-162 (1964) · Zbl 0156.16205
[24] Stewart, G., Introduction to Matrix Computations (1974), Academic · Zbl 0302.65021
[25] Wilkinson, J., The Algebraic Eigenvalue Problem (1965), Oxford U.P · Zbl 0258.65037
[26] Foster, L., A comparison of solutions to the minimal design problem, IEEE Trans. Automat. Control (Feb. 1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.