Abstract
The definition of the LU factoring of a matrix usually requires that the matrix be invertible. Current software systems have extended the definition to non-square and rank-deficient matrices, but each has chosen a different extension. Two new extensions, both of which could serve as useful standards, are proposed here: the first combines LU factoring with full-rank factoring, and the second extension combines full-rank factoring with fraction-free methods. Amongst other applications, the extension to full-rank, fraction-free factoring is the basis for a fractionfree computation of the Moore-Penrose inverse.
- Anonymous. Contributors to the proceedings of the I.R.E. Proceedings of the I.R.E., page 1328, November 1947.Google Scholar
- Howard Anton and Chris Rorres. Elementary Linear Algebra. Wiley, 9th edition, 2005.Google Scholar
- T. Banachiewicz. Cracow Observatory Reprint: ' Etudes d'analyse pratique, volume 22. University of Cracow, 1938.Google Scholar
- Erwin H. Bareiss. Sylvester's identity and multistep integer-preserving Gaussian elimination. Mathematics of Computation, 22(103):565--578, 1968.Google Scholar
- A. Ben-Israel and T.N.F. Greville. Generalized Inverses: Theory and Applications. Wiley, 1974.Google Scholar
- Claude Brezinski. The life and work of André Cholesky. Numer. Algorithms, 43:279--288, 2006.Google ScholarCross Ref
- R. M. Corless and D. J. Jeffrey. The Turing factorization of a rectangular matrix. SIGSAM Bull., 31(3):20--30, 1997. Google ScholarDigital Library
- Robert M. Corless and David J. Jeffrey. Well ... it isn't quite that simple. SIGSAM Bulletin, 26(3):2--6, 1992. Google ScholarDigital Library
- P.D. Crout. A short method for evaluating determinants and solving systems of linear equations with real or complex coefficients. Trans. Amer. Institute Elec. Engng, 60:1235--1240, 1941.Google ScholarCross Ref
- James W. Demmel. Applied Numerical Linear Algebra. SIAM, 1997. Google ScholarDigital Library
- P.S. Dwyer. The Doolittle technique. Ann. Math. Stat., 12:449--458, 1941.Google ScholarCross Ref
- P.S. Dwyer. Linear Computations. Wiley, New York, 1951.Google Scholar
- R.W. Farebrother. A memoir of the life of M.H. Doolittle. Bulletin Inst. Math. Applic., 23:102, 1987.Google Scholar
- K.O. Geddes, G. Labahn, and S. Czapor. Algorithms for Computer Algebra. Kluwer, 1992. Google ScholarDigital Library
- Gene Golub and Charles Van Loan. Matrix Computations, 2nd edition. Johns Hopkins Press, 1989.Google Scholar
- Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms. Society for Industrial & Applied Mathematics, 1996. Google ScholarDigital Library
- Leslie Hogben, editor. Handbook of linear algebra. Chapman and Hall/CRC, 2007.Google Scholar
- Stephen B. Leacock. Nonsense Novels, chapter Gertrude the Governess. Wildside Press, 1911.Google Scholar
- George C. Nakos, Peter R. Turner, and Robert M. Williams. Fraction-free algorithms for linear and polynomial equations. SIGSAM Bull., 31(3):11--19, 1997. Google ScholarDigital Library
- R. Piziak and P. L. Odell. Full rank factorization of matrices. Mathematics Magazine, 72(3):193--201, 1999.Google ScholarCross Ref
- Robert Piziak and P.L. Odell. Matrix Theory: From Generalized Inverses to Jordan Form. Chapman & Hall/CRC, 2007.Google ScholarCross Ref
- Lloyd N. Trefethen and David Bau III. Numerical Linear Algebra. Society for Industrial & Applied Mathematics, 1997.Google Scholar
- Alan M. Turing. Rounding-off errors in matrix processes. Quart. J. Mech. Appl. Math., 1:287--308, 1948.Google ScholarCross Ref
- Wenqin Zhou and D.J. Jeffrey. Fraction-free matrix factors: new forms for LU and QR factors. Frontiers of Computer Science in China, 2(1):67--80, 2008.Google ScholarCross Ref
Index Terms
- LU factoring of non-invertible matrices
Recommendations
A Multilevel Dual Reordering Strategy for Robust Incomplete LU Factorization of Indefinite Matrices
A dual reordering strategy based on both threshold and graph reorderings is introduced to construct robust incomplete LU (ILU) factorization of indefinite matrices. The ILU matrix is constructed as a preconditioner for the original matrix to be used in ...
Fast structured LU factorization for nonsymmetric matrices
In this paper, an approximate LU factorization algorithm is developed for nonsymmetric matrices based on the hierarchically semiseparable matrix techniques. It utilizes a technique involving orthogonal transformations and approximations to avoid the ...
Stability of block LU factorization for block tridiagonal matrices
It is showed that if A is I-block diagonally dominant (II-block diagonally dominant), then the reduced matrix S preserves the same property. We also give a sufficient condition for the reduced matrix S also to be a block H-matrix when A is a block H-...
Comments