On the existence and computation of lu factorizations with small pivots

Tony Chan*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

Let A be an n by n matrix which may be singular with a one-dimensional null space, and consider the /.(/-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 0(an) or 0(k˜\A)), where o is the smallest singular value of A and k(A) is the condition number of A. These conditions are expressed in terms of the elements of /f_1 in general but reduce to conditions on the elements of the singular vectors corresponding to o 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 ¿¿/factorization of the n by n upper triangular matrix 7 = that has an nth pivot equal to 2 ' 2.

Original languageEnglish (US)
Pages (from-to)535-547
Number of pages13
JournalMathematics of Computation
Volume42
Issue number166
DOIs
StatePublished - Jan 1 1984

Keywords

  • LU-factorizations
  • Singular systems

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On the existence and computation of lu factorizations with small pivots'. Together they form a unique fingerprint.

Cite this