28.2: Sparse Gaussian Elimination

This section is also very brief. As we already described in Unit III, in order to solve the matrix system \(A u=f\) in MATLAB we need only write \(u=\mathrm{A} \backslash \mathrm{f}\) - the famous backslash operator. We can now reveal, armed with the material from the current unit, that the backslash operator in fact performs Gaussian elimination (except for overdetermined systems, in which case the least-squares problem is solved by a QR algorithm). The backslash will automatically perform partial pivoting - permutations of rows to choose the maximum-magnitude available pivot - to ensure for a nonsingular matrix \(K\) that a zero pivot is never encountered and that furthermore amplification of numerical round-off errors (in finite precision) is minimized.

The sparse case is similarly streamlined. If \(A\) is a mathematically sparse matrix and we wish to solve \(A u=f\) by sparse Gaussian elimination as described in the previous chapter, we need only make sure that \(A\) is declared sparse and then write \(u=A \backslash f\). (As for the matrix vector product, \(f\) need not be declared sparse and the result \(u\) will not be sparse.) In this case the backslash does more than simply eliminate unnecessary calculations with zero operands: the backslash will permute columns (a reordering) in order to minimize fill-in during the elimination procedure. (As for the non-sparse case, row permutations will also be pursued, for purposes of numerical stability.)

The case of \(A\) SPD is noteworthy. As already indicated, in this case the Gaussian elimination process is numerically stable without any row permutations. For an SPD matrix, the backslash operator will thus permute the rows in a similar fashion to the columns; the columns, as before, are permuted to minimize fill-in, as described in the previous chapter. A particular variant of Gaussian elimination, the Cholesky factorization, is pursued in the SPD case.