Interactive Educational Modules in
Scientific Computing

Gaussian Elimination

This module illustrates LU factorization of a matrix using Gaussian elimination with pivoting. The initial matrix is reduced to upper triangular form by applying a sequence of elementary elimination matrices to annihilate the subdiagonal entries in successive columns. Each elementary elimination matrix is composed of an identity matrix plus some multipliers below the diagonal in the relevant column. Row interchanges (pivoting) can be used to avoid potential division by zero and limit the magnitudes of the multipliers, thereby enhancing numerical stability.

The user first selects a matrix size (n = 2, 3, or 4), then selects a matrix by choosing a preset example, a random matrix, or typing in desired entries. The successive steps of Gaussian elimination are then carried out sequentially by repeatedly clicking on NEXT or on the currently highlighted step. The current column is indicated by an arrow. For each column, the default choice of pivot is the entry of largest magnitude on or below the diagonal (partial pivoting), but any nonzero entry can be selected as pivot by clicking on it. Row interchanges are depicted explicitly. When Gaussian elimination is complete, the resulting L and U factors are displayed as separate lower and upper triangular matrices. Formats provided for displaying numeric entries include exponential (e), fixed (f), and generic (g), with g the default.

Reference Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 2.4.4, especially Algorithm 2.4 and Example 2.16.

Developers: Jessica Schoen and Michael Heath