Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2024 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

On the existence and computation of $LU$-factorizations with small pivots
HTML articles powered by AMS MathViewer

by Tony F. Chan PDF
Math. Comp. 42 (1984), 535-547 Request permission

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

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 nth pivot. When A is not singular, we show conditions under which a pivoting strategy will produce an nth pivot that is $O({\sigma _n})$ or $O({\kappa ^{ - 1}}(A))$, where ${\sigma _n}$ is the smallest singular value of A and $\kappa (A)$ is the condition number of A. These conditions are expressed in terms of the elements of ${A^{ - 1}}$ in general but reduce to conditions on the elements of the singular vectors corresponding to ${\sigma _n}$ 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 nth pivot for nearly singular matrices. As an example, we exhibit an LU-factorization of the n by n upper triangular matrix \[ T = \left [ {\begin {array}{*{20}{c}} 1 & { - 1} & {} & { - 1} & {} & \cdot & \cdot & { - 1} \\ {} & 1 & {} & \cdot & {} & {} & {} & \cdot \\ {} & {} & {} & 1 & \cdot & {} & {} & {} \\ {} & {} & {} & {} & \cdot & \cdot & {} & \cdot \\ {} & {} & 0 & {} & {} & \cdot & \cdot & \cdot \\ {} & {} & {} & {} & {} & {} & \cdot & { - 1} \\ {} & {} & {} & {} & {} & {} & {} & 1 \\ \end {array} } \right ]\] that has an nth pivot equal to $2^{-(n-2)}$.
References
  • Tony F. Chan, An improved algorithm for computing the singular value decomposition, ACM Trans. Math. Software 8 (1982), no. 1, 72–83. MR 661122, DOI 10.1145/355984.355990
  • 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, DOI 10.1137/0905009
  • Tony F. Chan, Deflated decomposition of solutions of nearly singular systems, SIAM J. Numer. Anal. 21 (1984), no. 4, 738–754. MR 749368, DOI 10.1137/0721050
  • 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, DOI 10.1137/0903012
  • A. K. Cline, An elimination method for the solution of linear least squares problems, SIAM J. Numer. Anal. 10 (1973), 283–289. MR 359294, DOI 10.1137/0710027
  • 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, DOI 10.1137/0716029
  • R. E. Cline and R. J. Plemmons, $l_{2}$-solutions to underdetermined linear systems, SIAM Rev. 18 (1976), no. 1, 92–106. MR 396604, DOI 10.1137/1018004
  • J. J. Dongarra, J. R. Bunch, C. B. Moler & G. W. Stewart, LINPACK User’s Guide, SIAM, Philadelphia, PA, 1979.
  • 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, DOI 10.1007/BF02163027
  • 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 413456, DOI 10.1137/1018113
  • Herbert B. Keller, Numerical solution of bifurcation and nonlinear eigenvalue problems, Applications of bifurcation theory (Proc. Advanced Sem., Univ. Wisconsin, Madison, Wis., 1976) Publ. Math. Res. Center, No. 38, Academic Press, New York, 1977, pp. 359–384. MR 0455353
  • H. B. Keller, Singular Systems, Inverse Interation and Least Squares, unpublished manuscript, Applied Mathematics Department, Caltech, Pasadena, CA, 1978. H. B. Keller, Numerical Continuation Methods, Short Course Lecture Notes, National Bureau of Standards, Center for Applied Mathematics, 1981. 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.
  • 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, DOI 10.1137/0904039
  • 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, DOI 10.1007/BF02241698
  • Dianne Prost O’Leary, Estimating matrix condition numbers, SIAM J. Sci. Statist. Comput. 1 (1980), no. 2, 205–209. MR 594756, DOI 10.1137/0901014
  • G. Peters & J. H. Wilkinson, "The least squares problem and pseudo-inverses," Comput. J., v. 13, 1970, pp. 309-316.
  • Robert J. Plemmons, Linear least squares by elimination and MGS, J. Assoc. Comput. Mach. 21 (1974), 581–585. MR 356474, DOI 10.1145/321850.321855
  • Werner C. Rheinboldt, Numerical methods for a class of finite dimensional bifurcation problems, SIAM J. Numer. Anal. 15 (1978), no. 1, 1–11. MR 494915, DOI 10.1137/0715001
  • 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, DOI 10.1137/0902011
  • R. K. H. Szeto, The Flow Between Rotating Coaxial Disks, Ph.D. thesis, California Institute of Technology, 1978.
  • J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65F05, 15A23
  • Retrieve articles in all journals with MSC: 65F05, 15A23
Additional Information
  • © Copyright 1984 American Mathematical Society
  • Journal: Math. Comp. 42 (1984), 535-547
  • MSC: Primary 65F05; Secondary 15A23
  • DOI: https://doi.org/10.1090/S0025-5718-1984-0736451-4
  • MathSciNet review: 736451