Lloyd N. Trefethen
Abstract
If numerical analysts understand anything, surely it must be Gaussian elimination. This is the oldest and truest of numerical algorithms. To be precise, I am speaking of Gaussian elimination with partial pivoting, the universal method for solving a dense, unstructured n X n linear system of equations Ax = b on a serial computer. This algorithm has been so successful that to many of us, Gaussian elimination and Ax = b are more or less synonymous. The chapter headings in the book by Golub and Van Loan [3] are typical -- along with "Orthogonalization and Least Squares Methods," "The Symetric Eigenvalue Problem," and the rest, one finds "Gaussian Elimination," not "Linear Systems of Equations."
- A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1976. Google Scholar
Digital Library
- D. Coppersmith and S. Winograd, On the asymptotic complexity of matrix multiplication, SIAM J. Comput. 11 (1982), 472--492.Google ScholarDigital Library
- G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, Maryland 1983.Google Scholar
- V. Pan, How can we speed up matrix multiplication?, SIAM Review 26 (1984), 393--415. Google ScholarDigital Library
- S. Smale, On the average number of steps in the simplex method of linear programming, Math. Prog. 27 (1983), 241--262.Google ScholarDigital Library
- B. T. Smith, et al., Matrix Eigensystem Routines -- EISPACK Guide, Lect. Notes. Comp. Sci. 6, Springer, New York, 1976.Google Scholar
- V. Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354--356.Google ScholarDigital Library
- F. Stummel, Forward error analysis of Gaussian elimination I, II, Numer. Math. 46 (1984), 365--415.Google ScholarDigital Library
- J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. Google ScholarDigital Library
Index Terms
- Three mysteries of Gaussian elimination
Recommendations
Gaussian elimination
AbstractAs the standard method for solving systems of linear equations, Gaussian elimination (GE) is one of the most important and ubiquitous numerical algorithms. However, its successful use relies on understanding its numerical stability properties and ...
Sparsity structure and Gaussian elimination
In this paper we collate and discuss some results on the sparsity structure of a matrix. If a matrix is irreducible, Gaussian elimination yields an LU factorization in which L has at least one entry beneath the diagonal in every column except the last ...
Comments