On the existence and computation of -factorizations with small pivots

Author:
Tony F. Chan

Journal:
Math. Comp. **42** (1984), 535-547

MSC:
Primary 65F05; Secondary 15A23

DOI:
https://doi.org/10.1090/S0025-5718-1984-0736451-4

Corrigendum:
Math. Comp. **44** (1985), 282.

MathSciNet review:
736451

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let *A* be an *n* by *n* matrix which may be singular with a one-dimensional null space, and consider the *LU*-factorization of *A*. When *A* is exactly singular, we show conditions under which a pivoting strategy will produce a zero *n*th pivot. When *A* is not singular, we show conditions under which a pivoting strategy will produce an *n*th pivot that is or , where is the smallest singular value of *A* and is the condition number of *A*. These conditions are expressed in terms of the elements of in general but reduce to conditions on the elements of the singular vectors corresponding to when *A* is nearly or exactly singular. They can be used to build a 2-pass factorization algorithm which is *guaranteed* to produce a small *n*th pivot for nearly singular matrices. As an example, we exhibit an *LU*-factorization of the *n* by *n* upper triangular matrix

**[1]**T. F. Chan, "An improved algorithm for computing the singular value decomposition,"*ACM Trans. Math. Software*, v. 8, 1982, pp. 72-83. MR**661122 (83f:65058)****[2]**T. F. Chan,*Deflation Techniques and Block-Elimination Algorithms for Solving Bordered Singular Systems*, Technical Report 226, Computer Science Department, Yale University, New Haven, CT, 1982;*SIAM J. Sci. Statist Comput.*, v. 5, 1984. MR**731886 (85h:65065)****[3]**T. F. Chan,*Deflated Decomposition of Solutions of Nearly Singular Systems*, Technical Report 225, Computer Science Department, Yale University, New Haven, CT, 1982;*SIAM J. Numer. Anal.*(To appear.) MR**749368 (86a:65029)****[4]**T. F. Chan & H. B. Keller, "Arclength continuation and multi-grid techniques for nonlinear eigenvalue problems,"*SIAM J. Sci. Statist. Comput.*, v. 3, 1982, pp. 173-194. MR**658631 (83d:65152)****[5]**A. K. Cline, "An elimination method for the solution of linear least squares problems,"*SIAM J. Numer. Anal.*, v. 10, 1973, pp. 283-289. MR**0359294 (50:11748)****[6]**A. K. Cline, C. B. Moler, G. W. Stewart & J. H. Wilkinson, "An estimate for the condition number of a matrix,"*SIAM J. Numer. Anal.*, v. 16, 1979, pp. 368-375. MR**526498 (80g:65048)****[7]**A. K. Cline & R. J. Plemmons, " solutions to underdetermined linear systems,"*SIAM Rev.*, v. 18, 1976, pp. 92-106. MR**0396604 (53:466)****[8]**J. J. Dongarra, J. R. Bunch, C. B. Moler & G. W. Stewart,*LINPACK User's Guide*, SIAM, Philadelphia, PA, 1979.**[9]**G. H. Golub & C. Reinsch, "Singular value decomposition and least squares solutions,"*Numer. Math.*, 14, 1970, pp. 403-420. MR**1553974****[10]**G. H. Golub & J. H. Wilkinson, "Ill-conditioned eigensystems and the computation of Jordan canonical form,"*SIAM Rev.*, v. 18, 1976, pp. 578-619. MR**0413456 (54:1570)****[11]**H. B. Keller, "Numerical solution of bifurcation and nonlinear eigenvalue problems," In*Applications of Bifurcation Theory*(P. Rabinowitz, ed.), Academic Press, New York, 1977, pp. 359-384. MR**0455353 (56:13592)****[12]**H. B. Keller,*Singular Systems, Inverse Interation and Least Squares*, unpublished manuscript, Applied Mathematics Department, Caltech, Pasadena, CA, 1978.**[13]**H. B. Keller,*Numerical Continuation Methods*, Short Course Lecture Notes, National Bureau of Standards, Center for Applied Mathematics, 1981.**[14]**H. B. Keller, "Practical procedures in path following near limit points," in*Computing Methods in Applied Sciences and Engineering*(Glowinski and Lions, eds.), North-Holland, Amsterdam, 1982.**[15]**H. B. Keller, "The bordering algorithm and path following near singular points of higher nullity,"*SIAM J. Sci. Statist. Comput.*, v. 4, 1983. MR**725653 (85e:65012)****[16]**R. G. Melhem & W. C. Rheinboldt, "A comparison of methods for determining turning points of nonlinear equations,"*Computing*, v. 29, 1982, pp. 201-226. MR**680470 (84b:65054)****[17]**D. P. O'Leary, "Estimating matrix condition numbers,"*SIAM J. Sci. Statist. Comput.*, v. 1, 1980, pp. 205-209. MR**594756 (82c:15006)****[18]**G. Peters & J. H. Wilkinson, "The least squares problem and pseudo-inverses,"*Comput. J.*, v. 13, 1970, pp. 309-316.**[19]**R. J. Plemmons, "Linear least squares by elimination and MGS,"*J. Assoc. Comput. Mach.*, v. 21, 1974, pp. 581-585. MR**0356474 (50:8944)****[20]**W. C. Rheinboldt, "Numerical methods for a class of finite dimensional bifurcation problems,"*SIAM J. Numer. Anal.*, v. 15, 1978, pp. 1-11. MR**0494915 (58:13694)****[21]**G. W. Stewart, "On the implicit deflation of nearly singular systems of linear equations,"*SIAM J. Sci. Statist. Comput.*, v. 2, 1981, pp. 136-140. MR**622710 (82f:65030)****[22]**R. K. H. Szeto,*The Flow Between Rotating Coaxial Disks*, Ph.D. thesis, California Institute of Technology, 1978.**[23]**J. H. Wilkinson,*The Algebraic Eigenvalue Problem*, Oxford Univ. Press, London, 1965. MR**0184422 (32:1894)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F05,
15A23

Retrieve articles in all journals with MSC: 65F05, 15A23

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1984-0736451-4

Keywords:
LU-factorizations,
singular systems

Article copyright:
© Copyright 1984
American Mathematical Society