Pivoting

Pivoting is a technique to rearrange the A matrix such that more desirable (as in more stable) elements are placed along the diagonal. If you recall from the "General Considerations" section, we can interchange rows and columns of the A matrix and b vector without changing the final solution. It can be shown mathematically that a "desirable" element to place on the diagonal is one with the largest magnitude among the available choices. The row or column containing the largest magnitude element among those considered is swapped with the row or column containing the current diagonal element. The rearrangement of the rows and columns is known as pivoting.

There are two types of pivoting. With partial pivoting, only rows are exchanged. With full pivoting, rows and/or columns can be exchanged. It turns out partial pivoting yields almost the same stability enhancements as full pivoting at a reduced computational cost. We will use partial pivoting in the methods declared in the EqnSolver class.

In the partial pivoting process, start with the first diagonal element (the first element of the first row of the A matrix). The elements in the first column below the first diagonal element are examined. If the element with the largest magnitude is greater than the magnitude of the first diagonal element, those rows are switched. You then proceed to the second diagonal element (the second element of the second row of the A matrix). The elements in the second column below the second diagonal element are searched. If the element with the largest magnitude is greater than the magnitude of the second diagonal element, those rows are switched.

The process continues all the way down the diagonal of the A matrix. Remember that the search is only conducted below the diagonal element being considered. As an example, if we perform a partial pivoting on the A matrix for our test case we would obtain the matrix in Eq. (19.5).

Equation 19.5

You can see that the zero has been moved off of the first diagonal element, meaning that the solution process has been made more stable.

One final note about pivoting concerns scaling effects. We can multiply any row of the A matrix and b vector by any number and preserve the solution vector. Such scaling will affect the pivoting process as the scaled row might be moved to a position to which it would not normally be moved. A way to avoid this is to use something called implicit pivoting. With implicit pivoting you evaluate each element in the array as if it had been scaled by the largest magnitude element in its row. For the purposes of pivoting, each element will have a magnitude between 0 and 1.

Four of the methods in the EqnSolver class make use of partial pivoting. Because it is a common function, we will write a partialPivot() method that the other classes can call. The code listing for the partialPivot() method is shown next . The index[][] matrix stores the history of the row swaps. This information is needed by the Gauss-Jordan method to unscramble the inverse A matrix. The scale[] array contains the largest magnitude element for each row.

 private static void partialPivot(          double a[][], double b[], int index[][]) {   double temp;   double tempRow[];   int i,j,m;   int numRows = a.length;   int numCols = a[0].length;   double scale[] = new double[numRows];   //  Determine the scale factor (the largest element)   //  for each row to use with implicit pivoting.   //  Initialize the index[][] array for an unmodified   //  array.   for(i=0; i<numRows; ++i) {     index[i][0] = i;     index[i][1] = i;     for(j=0; j<numCols; ++j) {       scale[i] = Math.max(scale[i],Math.abs(a[i][j]));     }   }   //  Determine the pivot element for each column and   //  rearrange the rows accordingly. The m variable   //  stores the row number that has the maximum   //  scaled value below the diagonal for each column.   //  The index[][] array stores the history of the row   //  swaps and is used by the Gauss-Jordan method to   //  unscramble the inverse a[][] matrix   for(j=0; j<numCols-1; ++j) {     m=j;     for(i=j+1; i<numRows; ++i) {       if ( Math.abs(a[i][j])/scale[i] >            Math.abs(a[m][j])/scale[m] ){           m=i;       }     }     if ( m != j ) {       index[j][0] = j;       index[j][1] = m;       tempRow = a[j];       a[j] = a[m];       a[m] = tempRow;       temp = b[j];       b[j] = b[m];       b[m] = temp;       temp = scale[j];       scale[j] = scale[m];       scale[m] = temp;     }   }   return; }