Pivot element

The pivot or pivot element is the element of a matrix, which is selected first by an algorithm (e.g. Gaussian elimination, Quicksort, Simplex algorithm, etc.), to do certain calculations with the matrix. These matrix algorithms require an entry distinct from zero in pivot position to work properly or at all. Finding this element is called pivoting. Pivoting interchanges the rows or columns of a matrix to allow the algorithms to be performed successfully or to reduce round-off error.

Pivoting might be thought of as swapping or sorting rows or columns in a matrix, and thus it can be represented as multiplication by permutation matrices. However, algorithms rarely move the matrix elements because this would cost too much time; instead, they just keep track of the permutations.

The pivot element in quicksort is the element that is selected as the boundary for partitioning. Quicksort sorts all elements "left" and "right" of the pivot element recursively.

Overall, pivoting adds more operations to the computational cost of an algorithm. These additional operations are sometimes necessary for the algorithm to work at all. Other times these additional operations are worth it because they add numerical stability to the final result.

Examples of systems that require pivoting

In the case of Gaussian elimination, the algorithm requires that pivot elements not be zero. Interchanging rows or columns in the case of a zero pivot element is necessary. The system below requires the interchange of rows 2 and 3 to perform elimination.

The system that results from pivoting is as follows and will allow the elimination algorithm and backwards substitution to output the solution to the system.

Furthermore, in Gaussian elimination it is generally desirable to choose a pivot element with large absolute value. This improves the numerical stability. The following system (taken from Numerical Analysis, Burden and Faires, 8th Edition.) is dramatically affected by round-off error when Gaussian elimination and backwards substitution are performed.

This system has the exact solution of x₁ = 10.00 and x₂ = 1.000, but when the elimination algorithm and backwards substitution are performed using four-digit arithmetic, the small value of a₁₁ causes small round-off errors to be propagated. The algorithm without pivoting yields the approximation of x₁ ≈ -10.00 and x₂ ≈ 1.001. In this case it is desirable that we interchange the two rows so that a₂₁ is in the pivot position

Considering this system, the elimination algorithm and backwards substitution using four-digit arithmetic yield the correct values x₁ = 10.00 and x₂ = 1.000.

Partial and complete pivoting

In partial pivoting, the algorithm selects the entry with largest absolute value from the column of the matrix that is currently being considered as the pivot element. Partial pivoting is generally sufficient to adequately reduce round-off error. However for certain systems and algorithms, complete pivoting (or maximal pivoting) may be required for acceptable accuracy. Complete pivoting considers all entries in the whole matrix, interchanging rows and columns to achieve the highest accuracy. Complete pivoting is usually not necessary to ensure numerical stability and, due to the additional computations it introduces, it may not always be the most appropriate pivoting strategy.

Scaled pivoting

A variation the partial pivoting strategy is scaled partial pivoting. In this approach, the algorithm selects as the pivot element the entry that is largest relative to the entries in its row. This strategy is desirable when entries' large differences in magnitude lead to the propagation of round-off error. Scaled pivoting should be used to in system like the one below where a row's entries vary greatly in magnitude. In the example below, it would desirable to interchange the two rows because the current pivot element 30 is larger than 5.291 but it is relatively small compared with the other entries in its row. Without row interchange in this case, rounding errors will be propagated as in the previous example.

References

• G. H. Golub, C. F. Loan, Matrix Computations, 3rd edition, Johns Hopkins, 1996. ISBN 0801854148.

• R. L. Burden, J. D. Faires, Numerical Analysis, 8th edition, Thompson Brooks/Cole, 2005. ISBN 0534392008

This article incorporates material from Pivoting on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

This mathematics-related article is a stub. You can help Wikipedia by expanding it. v • d • e