Introduction

Sometimes the order in which the equations are presented to the solution algorithm has a significant effect on the results. For example, consider the equations

The corresponding augmented coefficient matrix is

(a)

Equations (a) are in the right order in the sense that we would have no trouble obtaining the correct solution x ₁= x ₂= x ₃=1 by Gauss elimination or LU decomposition. Now suppose that we exchange the first and third equations, so that the augmented coefficient matrix becomes

(b)

Since we did not change the equations (only their order was altered), the solution is still x ₁= x ₂= x ₃=1. However, Gauss elimination fails immediately due to the presence of the zero pivot element (the element A ₁₁).

The above example demonstrates that it is sometimes essential to reorder the equations during the elimination phase. The reordering, or row pivoting, is also required if the pivot element is not zero, but very small in comparison to other elements in the pivot row, as demonstrated by the following set of equations:

(c)

These equations are the same as Eqs. (b), except that the small number ? replaces the zero element A ₁₁ in Eq. (b). Therefore, if we let ? ?0, the solutions of Eqs. (b) and (c) should become identical. After the first phase of Gauss elimination, the augmented coefficient matrix becomes

(d)

Because the computer works with a fixed word length,...