Solution of sparse rectangular systems using LSQR and CRAIG
Tóm tắt
We examine two iterative methods for solving rectangular systems of linear equations: LSQR for over-determined systemsAx ≈ b, and Craig's method for under-determined systemsAx = b. By including regularization, we extend Craig's method to incompatible systems, and observe that it solves the same damped least-squares problems as LSQR. The methods may therefore be compared on rectangular systems of arbitrary shape. Various methods for symmetric and unsymmetric systems are reviewed to illustrate the parallels. We see that the extension of Craig's method closes a gap in existing theory. However, LSQR is more economical on regularized problems and appears to be more reliable if the residual is not small. In passing, we analyze a scaled “augmented system” associated with regularized problems. A bound on the condition number suggests a promising direct method for sparse equations and least-squares problems, based on indefiniteLDL
T
factors of the augmented matrix.
Tài liệu tham khảo
M. Arioli, I. S. Duff and P. P. M. de Rijk,On the augmented system approach to sparse least-squares problems, Numer. Math., 55 (1989), pp. 667–684.
Å. Björck,Iterative refinement of linear least squares solutions I, BIT, 7 (1967), pp. 257–278.
Å. Björck,A bidiagonalization algorithm for solving ill-posed systems of linear equations, Report LITH-MAT-R-80-33, Dept. of Mathematics, Linköping University, Linköping, Sweden, 1980.
Å. Björck,Pivoting and stability in the augmented system method, in D. F. Griffiths and G. A. Watson (eds.),Numerical Analysis 1991: Proceedings of the 14th Dundee Conference, Pitman Research Notes in Mathematics 260, Longman Scientific and Technical, Harlow, Essex, 1992.
J. E. Craig,The N-step iteration procedures, J. Math. and Phys., 34, 1 (1955), pp. 64–73.
A. Dax,On row relaxation methods for large constrained least-squares problems, SIAM J. Sci. Comp., 14 (1993), pp. 570–584.
I. S. Duff and J. K. Reid,Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems, ACM Trans. Math. Softw., to appear.
D. K. Faddeev and V. N. Faddeeva,Computational Methods of Linear Algebra, Freeman, London, 1963.
R. W. Freund,Über einige CG-ähnliche Verfahren zur Lösung linearer Gleichungssysteme, Ph.D. Thesis, Universität Würzburg, FRG, 1983.
P. E. Gill, M. A. Saunders and J. R. Shinnerl,On the stability of Cholesky factorization for quasi-definite systems, SIAM J. Mat. Anal., 17(1) (1996), to appear.
G. H. Golub and W. Kahan,Calculating the singular values and pseudoinverse of a matrix, SIAM J. Numer. Anal., 2 (1965), pp. 205–224.
G. H. Golub and C. F. Van Loan,Unsymmetric positive definite linear systems, Linear Alg. and its Appl., 28 (1979), pp. 85–98.
P. C. Hansen,Test matrices for regularization methods, SIAM J. Sci. Comput., 16(2) (1995), pp. 506–512.
G. T. Herman, A. Lent and H. Hurwitz,A storage-efficient algorithm for finding the regularized solution of a large, inconsistent system of equations, J. Inst. Math. Appl., 25 (1980), pp. 361–366.
D. P. O'Leary, Private communication, 1990.
C. Lanczos,An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Standards, 45 (1950), pp. 255–282.
P. Matstoms,Sparse QR factorization in MATLAB, ACM Trans. Math. Software, 20(1) (1994), pp. 136–159.
C. C. Paige,Bidiagonalization of matrices and solution of linear equations, SIAM J. Numer. Anal., 11 (1974), pp. 197–209.
C. C. Paige,Krylov subspace processes, Krylov subspace methods and iteration polynomials, in J. D. Brown, M. T. Chu, D. C. Ellison, and R. J. Plemmons, eds.,Proceedings of the Cornelius Lanczos International Centenary Conference, Raleigh, NC, Dec. 1993, SIAM, Philadelphia, 1994, pp. 83–92.
C. C. Paige and M. A. Saunders,Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12(4) (1975), pp. 617–629.
C. C. Paige and M. A. Saunders,LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8(1) (1982), pp. 43–71.
C. C. Paige and M. A. Saunders,Algorithm 583. LSQR: Sparse linear equations and least squares problems, ACM Trans. Math. Software, 8(2) (1982), pp. 195–209.
M. A. Saunders,Cholesky-based methods for sparse least squares: The benefits of regularization, Report SOL 95-1, Dept. of Operations Research, Stanford University, California, USA, 1995.
R. J. Vanderbei,Symmetric quasi-definite matrices, SIAM J. Optim., 5(1) (1995), pp. 100–113.