Advanced Review Gaussian elimination Nicholas J.Higham* As the standard method for solving systems of linear equations,Gaussian elimination(GE)isone ofthe mostimportant and ubiquitous numericalalgorithms. succes sfu relies on understan ters.We givean of GE from thee xpa hycmputes factor and thearousetofthis matrix factor ization viewpoint.Pivoting strategies for ensuring numerical stability are descrbe al properties of G r certain cla ses of stru LU factorization,corresponding to the use of pivot blocks instead of pivot elements, in how iterative refinement can be used to improve a solution topic e GE for spars 20113230-238DoL10.102wics.16 computers.2011 John Wiley &Sons,Inc.WIREs Comp Sta Gat an elimination;LU factorization;pivoting numerical stability; INTRODUCTION The ies for ensurine numerical stability.In the section'Structured Matr specia results that hold for LU it and plays a fundamental role in scientific computation. when as particular proper GE was known to the ancient Chinesel and is wellas eron of GE that uses block pivots.Iterative familiar to rehnement- natu me nea computed s describe fol oundoff (or machin method in linear algebra courses where it is usually taught in conjunction with reduction to echelon form =2 ≈1.1×10-16.We write fl(A)for the result In this linear a br ra context,GE is shown to be a tool unding th ele ments of A to ing all sol loating poin system,for c ndenotes the vector [1,2,... n:-1: to GE from the point of view of matrix analysis and denotes the vector matrix computations. nd ve denotes the many facets of by and the columns the any summarizing GE and its basic linear algebraic the oo-norm,given for A E R"x by the formula erties,including conditions for its suc ss and the key interpretation of the elimination as LU factorization LU FACTORL☑ATIO Nicholas i.high The aim of GE is to reduce a full system of n linear D0L:10.1002 /wics..16 olve to one t we can. 230 2011 John Wiley Sons,Inc Volume 3,Mayllune 2011 Advanced Review Gaussian elimination Nicholas J. Higham∗ As 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 how to organize its computations for efficient execution on modern computers. We give an overview of GE, ranging from theory to computation. We explain why GE computes an LU factorization and the various benefits of this matrix factorization viewpoint. Pivoting strategies for ensuring numerical stability are described. Special properties of GE for certain classes of structured matrices are summarized. How to implement GE in a way that efficiently exploits the hierarchical memories of modern computers is discussed. We also describe block LU factorization, corresponding to the use of pivot blocks instead of pivot elements, and explain how iterative refinement can be used to improve a solution computed by GE. Other topics are GE for sparse matrices and the role GE plays in the TOP500 ranking of the world’s fastest computers.  2011 John Wiley & Sons, Inc. WIREs Comp Stat 2011 3 230–238 DOI: 10.1002/wics.164 Keywords: Gaussian elimination; LU factorization; pivoting; numerical stability; iterative refinement INTRODUCTION Gaussian elimination (GE) is the standard method for solving a system of linear equations. As such, it is one of the most ubiquitous numerical algorithms and plays a fundamental role in scientific computation. GE was known to the ancient Chinese1 and is familiar to many school children as the intuitively natural method of eliminating variables from linear equations. Gauss used it in the context of the linear least squares problem.2–4 Undergraduates learn the method in linear algebra courses, where it is usually taught in conjunction with reduction to echelon form. In this linear algebra context, GE is shown to be a tool for obtaining all solutions to a linear system, for com￾puting the determinant, and for deducing the rank of the coefficient matrix. However, there is much more to GE from the point of view of matrix analysis and matrix computations. In this article, we survey the many facets of GE that are relevant to computation—in statistics or in other contexts. We begin in the next section by summarizing GE and its basic linear algebraic prop￾erties, including conditions for its success and the key interpretation of the elimination as LU factorization. ∗Correspondence to: Nicholas.j.higham@manchester.ac.uk School of Mathematics, The University of Manchester, Manchester, UK DOI: 10.1002/wics.164 Then we turn to the numerical properties of LU fac￾torization and discuss pivoting strategies for ensuring numerical stability. In the section ‘Structured Matri￾ces’, we describe some special results that hold for LU factorization when the matrix has particular proper￾ties. Computer implementation is then discussed, as well as a version of GE that uses block pivots. Iterative refinement—a means for improving the quality of a computed solution—is also described. We will need the following notation. The unit roundoff (or machine precision) is denoted by u; in IEEE double precision arithmetic it has the value u = 2−53 ≈ 1.1 × 10−16. We write fl(A) for the result of rounding the elements of A to floating point numbers. The ith unit vector ei is the vector that is zero except for a 1 in the ith element. The notation 1: n denotes the vector [1, 2, ... , n], while n: − 1: 1 denotes the vector [n, n − 1, ... , 1]. A(i, j), with i and j vectors of indices, denotes the submatrix of A comprising the intersection of the rows specified by i and the columns specified by j. A denotes any subordinate matrix norm, and we sometimes use the ∞-norm, given for A ∈ Rn×n by the formula A∞ = max1≤i≤n
n j=1 |aij|. LU FACTORIZATION The aim of GE is to reduce a full system of n linear equations in n unknowns to triangular form using elementary row operations, thereby reducing a prob￾lem that we cannot solve to one that we can. There 230  2011 John Wiley & Son s, In c. Volume 3, May/June 2011