As I understand it, the following three pivoting techniques:
- Partial pivoting (which exchanges rows determined by a sub-column search)
- Rook pivoting (which exchanges rows or columns based on sub-row and sub-column searches)
- Complete pivoting (which exchanges rows and columns based on sub-matrix search)
can be employed to solve a linear systems $Ax=b$ through $LU$ decomposition.
The following linear system has the expressed solution:
$$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 2 & 4 & 0 \\ 0 & 3 & 5 & 0 \\ 6 & 0 & 0 & 1 \\ \end{bmatrix} \mathbf{x} = \begin{bmatrix} 1 \\ 16 \\ 21 \\ 10 \end{bmatrix}, \qquad \mathbf{x} = \begin{bmatrix} 1 \\ 2\\ 3\\ 4\\ \end{bmatrix} $$
If I performed any of the above pivoting techniques to $A$ the results would be:
Partial Pivoting
$$\begin{bmatrix} 6 & 0 & 0 & 1 \\ 0 & 3 & 5 & 0 \\ 0 & 2 & 4 & 0 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix} $$
Rook Pivoting
$$\begin{bmatrix} 6 & 0 & 0 & 1 \\ 0 & 4 & 2 & 0 \\ 0 & 5 & 3 & 0 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix} $$
Complete Pivoting
$$\begin{bmatrix} 6 & 0 & 0 & 1 \\ 0 & 5 & 3 & 0 \\ 0 & 4 & 2 & 0 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix} $$ In all cases the bottom right value is zero meaning the pivoting has effectively failed. It would have been better to leave the matrix in its original form.
In practice when linear solvers have this type of problem do they expend some operations determining if these further operations are needed? Or if one algorithm is better than another, e.g. use QR factorisation?
In this case one could analyse the trace of $A$ and determine that the ratio of any element on the diagonal relative to the maximum value of the matrix is $>=\frac{1}{6}$, hence solve without pivoting?
There is an apparent misunderstanding of how pivoting is used in the LU factorization. It is not used to permute the original matrix before the actual elimination algorithm, but instead to choose pivots by permuting the "intermediate" partially eliminated matrices generated during the individual steps of the elimination.
A step of an LU factorization can be expressed as $A_k=L'_kA_{k-1}$, where $A_0:=A$ and $L'_k$ is an elementary unit lower triangular matrix introducing zeros below the diagonal of the $k$th column of $A_{k-1}$, eventually meaning that $A_n=:U$ is upper triangular.
The partial pivoting introduces permuation matrices $P_k$ such that the $(k,k)$ entry of the row-permuted matrix $P_kA_{k-1}$ is the largest in magnitude compared to the other entries in the same column below the diagonal of $A_{k-1}$. In complete pivoting there is an extra permutation matrix $Q_k$ which together with $P_k$ selects the pivot by both row and column permutation $P_kA_{k-1}Q_k$ such that the largest element in magnitude of the trailing uneliminated part is brought to the current pivoting entry. If I remember correctly, the Rook's pivoting strategy is similar to the complete pivoting in terms of utilization of both row and column permutations.
In any case, $PAQ=LU$ is how the results of all considered pivoting techniques could be related to the original matrix $A$ and the resulting triangular factors, where $P$ and $Q$ are permutations ($Q=I$ for the partial pivoting). However, the sequence of elementary permutations forming both $P$ and $Q$ depends on the intermediate values appearing in the partially reduced matrices $A_k$, not on the values in the original matrix $A$ itself.