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 Free Access

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]**Tony F. Chan,*An improved algorithm for computing the singular value decomposition*, ACM Trans. Math. Software**8**(1982), no. 1, 72–83. MR**661122**, https://doi.org/10.1145/355984.355990**[2]**Tony F. Chan,*Deflation techniques and block-elimination algorithms for solving bordered singular systems*, SIAM J. Sci. Statist. Comput.**5**(1984), no. 1, 121–134. MR**731886**, https://doi.org/10.1137/0905009**[3]**Tony F. Chan,*Deflated decomposition of solutions of nearly singular systems*, SIAM J. Numer. Anal.**21**(1984), no. 4, 738–754. MR**749368**, https://doi.org/10.1137/0721050**[4]**Tony F. C. Chan and H. B. Keller,*Arc-length continuation and multigrid techniques for nonlinear elliptic eigenvalue problems*, SIAM J. Sci. Statist. Comput.**3**(1982), no. 2, 173–194. MR**658631**, https://doi.org/10.1137/0903012**[5]**A. K. Cline,*An elimination method for the solution of linear least squares problems*, SIAM J. Numer. Anal.**10**(1973), 283–289. Collection of articles dedicated to the memory of George E. Forsythe. MR**0359294**, https://doi.org/10.1137/0710027**[6]**A. K. Cline, C. B. Moler, G. W. Stewart, and J. H. Wilkinson,*An estimate for the condition number of a matrix*, SIAM J. Numer. Anal.**16**(1979), no. 2, 368–375. MR**526498**, https://doi.org/10.1137/0716029**[7]**R. E. Cline and R. J. Plemmons,*𝑙₂-solutions to underdetermined linear systems*, SIAM Rev.**18**(1976), no. 1, 92–106. MR**0396604**, https://doi.org/10.1137/1018004**[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 and C. Reinsch,*Handbook Series Linear Algebra: Singular value decomposition and least squares solutions*, Numer. Math.**14**(1970), no. 5, 403–420. MR**1553974**, https://doi.org/10.1007/BF02163027**[10]**G. H. Golub and J. H. Wilkinson,*Ill-conditioned eigensystems and the computation of the Jordan canonical form*, SIAM Rev.**18**(1976), no. 4, 578–619. MR**0413456**, https://doi.org/10.1137/1018113**[11]**Herbert B. Keller,*Numerical solution of bifurcation and nonlinear eigenvalue problems*, Applications of bifurcation theory (Proc. Advanced Sem., Univ. Wisconsin, Madison, Wis., 1976) Academic Press, New York, 1977, pp. 359–384. Publ. Math. Res. Center, No. 38. MR**0455353****[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]**Herbert B. Keller,*The bordering algorithm and path following near singular points of higher nullity*, SIAM J. Sci. Statist. Comput.**4**(1983), no. 4, 573–582. MR**725653**, https://doi.org/10.1137/0904039**[16]**R. G. Melhem and W. C. Rheinboldt,*A comparison of methods for determining turning points of nonlinear equations*, Computing**29**(1982), no. 3, 201–226 (English, with German summary). MR**680470**, https://doi.org/10.1007/BF02241698**[17]**Dianne Prost O’Leary,*Estimating matrix condition numbers*, SIAM J. Sci. Statist. Comput.**1**(1980), no. 2, 205–209. MR**594756**, https://doi.org/10.1137/0901014**[18]**G. Peters & J. H. Wilkinson, "The least squares problem and pseudo-inverses,"*Comput. J.*, v. 13, 1970, pp. 309-316.**[19]**Robert J. Plemmons,*Linear least squares by elimination and MGS*, J. Assoc. Comput. Mach.**21**(1974), 581–585. MR**0356474**, https://doi.org/10.1145/321850.321855**[20]**Werner C. Rheinboldt,*Numerical methods for a class of finite dimensional bifurcation problems*, SIAM J. Numer. Anal.**15**(1978), no. 1, 1–11. MR**0494915**, https://doi.org/10.1137/0715001**[21]**G. W. Stewart,*On the implicit deflation of nearly singular systems of linear equations*, SIAM J. Sci. Statist. Comput.**2**(1981), no. 2, 136–140. MR**622710**, https://doi.org/10.1137/0902011**[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*, Clarendon Press, Oxford, 1965. MR**0184422**

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