Pivot totale

Una ulteriore variante del pivot consiste nello scambiare opportunamente anche le colonne della matrice A, calcolando così la fattorizzazione di PAQ, dove P scambia le righe e Q scambia le colonne (sono entrambe matrici di permutazione). Lo scambio di colonne serve solo a rendere l'algoritmo più stabile (teoricamente il solo scambio di righe basta per l'esistenza della fattorizzazione LU).

Al passo k, anziché prendere come pivot a_kk si può prendere un qualunque a_ij (con $i,j\geq k$). Di solito si sceglie l'elemento di massimo modulo in tutta la sottomatrice di indici $i,j\geq k$. Fare questa scelta però richiede O(n²)operazioni solo per determinare il pivot:

    /* Passo k dell'eliminazione di Gauss con pivot totale */
                       /* Ricerca del pivot su righe e colonne */
    pivot = a[k][k];
    irig = k;
    icol = k;
    for (i=k; i<n; i++)
        for (j=k; j<n; j++)
            if ( fabs(a[i][j])>fabs(pivot) ) {
                pivot = a[i][j];
                irig = i;
                icol = j;
            }
    ...

Adesso bisogna scambiare la riga k con la irig, e la colonna k con la icol. Lo scambio di righe si fa come prima. Quello di colonne si può fare

1.

scambiando effettivamente tutti gli elementi a[i][k] con a[i][icol]; questo però richiede molto tempo e molti accessi in memoria;

2.

utilizzando per l'accesso alla matrice un ``indice di colonna'', cioè un vettore c, inizializzato a c[j]=j. Con questo metodo, quando si vuole l'elemento (i,j) di A si deve scrivere a[i][c[j]] (bisogna quindi riscrivere il codice mostrato in precedenza). Lo scambio delle colonne si può fare scambiando i valori di c[k] e di c[icol].

Se si risolve un sistema lineare, bisogna tener conto che lo scambio di colonne non trasforma il sistema in un altro equivalente: si deve infatti ``riaggiustare'' il vettore soluzione. In pratica si è trasformato il sistema $A{\bf x}={\bf b}$ in $AQQ^{-1}{\bf x}={\bf b}$. Quindi alla fine dell'intero algoritmo (dopo la sostituzione all'indietro) il vettore soluzione trovato sarà $Q^{-1}{\bf x}$, e bisogna applicargli Q a sinistra (= scambio di righe) per ottenere il vero ${\bf x}$. Utilizzando il vettore indice di colonna, ciò significa che

                       /* Sia x[] il vettore ottenuto */
    for (i=0; i<n; i++)
        verox[i] = x[ c[i] ];

Si noti che il metodo di Gauss con il pivot totale viene molto rallentato sia dalla ricerca del pivot, sia dall'accesso ad ogni singolo elemento (che richiede l'accesso al vettore indice). Questi rallentamenti consentono un miglioramento della stabilità solo marginale, per cui questo metodo, nella pratica, non è molto utilizzato.