Pivot element

<h2 id="examples-of-systems-that-require-pivoting">Examples of systems that require pivoting</h2>
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.

[
          
            
              
                
                  1
                
                
                  −
                  1
                
                
                  2
                
                
                  8
                
              
              
                
                  0
                
                
                  0
                
                
                  −
                  1
                
                
                  −
                  11
                
              
              
                
                  0
                
                
                  2
                
                
                  −
                  1
                
                
                  −
                  3
                
              
            
          
          ]
        
      
    
    {\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&0&-1&-11\\0&2&-1&-3\end{array}}\right]}

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.

[
          
            
              
                
                  1
                
                
                  −
                  1
                
                
                  2
                
                
                  8
                
              
              
                
                  0
                
                
                  2
                
                
                  −
                  1
                
                
                  −
                  3
                
              
              
                
                  0
                
                
                  0
                
                
                  −
                  1
                
                
                  −
                  11
                
              
            
          
          ]
        
      
    
    {\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&2&-1&-3\\0&0&-1&-11\end{array}}\right]}

Furthermore, in Gaussian elimination it is generally desirable to choose a pivot element with large <a href="/facts/Absolute_value/dwJBpEs5">absolute value</a>. This improves the <a href="/facts/Numerical_stability/jRDdo8zV">numerical stability</a>. The following system is dramatically affected by round-off error when Gaussian elimination and backwards substitution are performed.

[
          
            
              
                
                  0.00300
                
                
                  59.14
                
                
                  59.17
                
              
              
                
                  5.291
                
                
                  −
                  6.130
                
                
                  46.78
                
              
            
          
          ]
        
      
    
    {\displaystyle \left[{\begin{array}{cc|c}0.00300&59.14&59.17\\5.291&-6.130&46.78\\\end{array}}\right]}

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

[
          
            
              
                
                  5.291
                
                
                  −
                  6.130
                
                
                  46.78
                
              
              
                
                  0.00300
                
                
                  59.14
                
                
                  59.17
                
              
            
          
          ]
        
        .
      
    
    {\displaystyle \left[{\begin{array}{cc|c}5.291&-6.130&46.78\\0.00300&59.14&59.17\\\end{array}}\right].}

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

<h2 id="partial-rook-and-complete-pivoting">Partial, rook, and complete pivoting</h2>
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. More specifically, when reducing a matrix to row echelon form, partial pivoting swaps rows before the column's row reduction to make the pivot element have the largest absolute value compared to the elements below in the same column. 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 interchanges both rows and columns in order to use the largest (by absolute value) element in the matrix as the pivot. Complete pivoting is usually not necessary to ensure numerical stability and, due to the additional cost of searching for the maximal element, the improvement in numerical stability that it provides is typically outweighed by its reduced efficiency for all but the smallest matrices. Hence, it is rarely used.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
Another strategy, known as rook pivoting also interchanges both rows and columns but only guarantees that the chosen pivot is simultaneously the largest possible entry in its row and the largest possible entry in its column, as opposed to the largest possible in the entire remaining submatrix.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> When implemented on serial computers this strategy has expected cost of only about three times that of partial pivoting and is therefore cheaper than complete pivoting. Rook pivoting has been proved to be more stable than partial pivoting both theoretically and in practice.

<h2 id="scaled-pivoting">Scaled pivoting</h2>
A variation of the partial pivoting strategy is scaled 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 in a system like the one below where a row's entries vary greatly in magnitude. In the example below, it would be 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.

[
          
            
              
                
                  30
                
                
                  591400
                
                
                  591700
                
              
              
                
                  5.291
                
                
                  −
                  6.130
                
                
                  46.78
                
              
            
          
          ]
        
      
    
    {\displaystyle \left[{\begin{array}{cc|c}30&591400&591700\\5.291&-6.130&46.78\\\end{array}}\right]}

<h2 id="pivot-position">Pivot position</h2>
A pivot position in a matrix, A, is a position in the matrix that corresponds to a row–leading 1 in the <a href="/facts/Reduced_row_echelon_form/U9LQHBYq">reduced row echelon form</a> of A. Since the reduced row echelon form of A is unique, the pivot positions are uniquely determined and do not depend on whether or not row interchanges are performed in the reduction process. Also, the pivot of a row must appear to the right of the pivot in the above row in <a href="/facts/Row_echelon_form/U9LQHBYq">row echelon form</a>.

This article incorporates material from Pivoting on <a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a>, which is licensed under the Creative Commons Attribution/Share-Alike License.

<ul><li>R. L. Burden, J. D. Faires, Numerical Analysis, 8th edition, Thomson Brooks/Cole, 2005. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-534-39200-8</li>
<li>G. H. Golub, C. F. Loan, Matrix Computations, 3rd edition, Johns Hopkins, 1996. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-8018-5414-8.</li>
<li><a href="/facts/Komei_Fukuda/H88HI0Q4">Fukuda, Komei</a>; <a href="/facts/Tam%25C3%25A1s_Terlaky/dLobLWrP">Terlaky, Tamás</a> (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997. 79 (1–3): 369–395. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373">10.1.1.36.9373</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02614325">10.1007/BF02614325</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1464775">1464775</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2794181">2794181</a>. <a href="http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps">Postscript preprint</a>.</li>
<li>Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. Degeneracy in optimization problems. 46–47 (1): 203–233. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.7658">10.1.1.36.7658</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02096264">10.1007/BF02096264</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0254-5330">0254-5330</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1260019">1260019</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6058077">6058077</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Edelman, Alan, 1992. The Complete Pivoting Conjecture for Gaussian Elimination is False. Mathematica Journal 2, no. 2: 58-61. <a href="http://www-math.mit.edu/~edelman/publications/complete_pivoting.pdf" target="_blank">http://www-math.mit.edu/~edelman/publications/complete_pivoting.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Poole, George; Neale, Larry (November 2000). "The Rook's Pivoting Strategy". Journal of Computational and Applied Mathematics. 123 (1–2): 353–369. Bibcode:2000JCoAM.123..353P. doi:10.1016/S0377-0427(00)00406-4. <a href="https://doi.org/10.1016%2FS0377-0427%2800%2900406-4" target="_blank">https://doi.org/10.1016%2FS0377-0427%2800%2900406-4</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Pivot element open-in-new

Pivot element