What is scaled partial pivoting?

Question

I have been reading this topic about scaled partial pivoting. And I'm not able to figure out some things like when should we use scaled partial pivoting in a matrix? And if the first entry in the first row has the highest value in its respective column i.e. first column then should we still interchange the rows?

Answer 1

Scaled partial pivoting is a numerical technique used in algorithms for Gaussian elimination (or other related algorithms such as $LU$ decomposition) with the purpose of reducing potential propagation of numerical errors (due to finite arithmetic).

In Gaussian elimination, there are situations in which the current pivot row needs to be swapped with one of the rows below (e.g. when the current pivot element is $0$). SPP is a refinement of plain partial pivoting, in which the row whose pivot element (i.e., the element in the pivot column) has the maximal absolute value is selected. This avoids the propagation of numerical error when the original pivot is very small.

For example, consider solving the following system of equations. We'll assume we're a computer working with three-digit finite arithmetic. I'll denote with $\newcommand{\dapprox}{\stackrel{\cdot}{\approx}}$ $\dapprox$ round-offs caused by the finite arithmetic, and I'll use $\approx$ for other approximations.

$$ \begin{bmatrix} -10^{-4} & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \end{bmatrix} $$

This system has the exact solution $(x, y) = (\frac{10000}{10001}, \frac{10002}{10001}) \approx (1, 1)\,.$ Let's try to simulate the computation with finite arithmetic, without using pivoting. We'll start by calculating the factor by which we have to multiply the first row (to subtract the result from the second row).

$$m_{21} = \frac{1}{-10^{-4}} = -10^{4}\,.$$

Now we subtract $m_{21}$ times the first row from the second, obtaining:

$$ \begin{gather} a^{(1)}_{1, 2} = 0\\ a^{(1)}_{2, 2} = 1 + 10^{4}\cdot 1 = 0.0001 \cdot 10^{4} + 10^4 \dapprox 10^4\\ b^{(1)}_2 = 2 + 10^4 = 0.0002\cdot 10^4 + 10^4 \dapprox 10^4 \end{gather} $$

$$ \begin{bmatrix} -10^{-4} & 1 \\ 0 & 10^4 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 10^4 \end{bmatrix} $$

Solving the system by back-substitution we get $y = 1$, $x = \frac{1-y}{-10^{-4}} = 0$. This solution is wildly inaccurate!

Now, if we apply partial pivoting to the matrix, we solve by gaussian elimination the system

$$ \begin{bmatrix} 1 & 1 \\ -10^{-4} & 1 \end{bmatrix} \begin{bmatrix} y \\ x \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}\,. $$

Repeating the previous algorithm:

$$ \begin{gather} m_{21} = \frac{-10^{-4}}{1} = -10^{-4}\\ a^{(1)}_{1, 2} = 0\\ a^{(1)}_{2, 2} = 1 + 10^{-4}\cdot 1 = 1 + 0.0001 \dapprox 1\\ b^{(1)}_2 = 1 + 2\cdot 10^{-4} = 1 + 0.0002 \dapprox 1 \end{gather} $$

$$ \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} y \\ x \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}\,. $$

Now, by back-substitution, we get $x = 1$, $y = 1$ as a solution, which is far more accurate.

---

Well, there are situations in which partial pivoting isn't enough. Particularly, a pivot's absolute value may be greater than another but it may be very small in relation to the other elements in its row — which is what actually matters.

Consider the system

$$ \begin{bmatrix} 1 & 10000 \\ 1 & 0.0001 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 10000 \\ 1 \end{bmatrix}\,. $$

According to partial pivoting, we don't need to swap the rows, since neither pivot is greater than the other. But as you can notice, the pivot in the first row is "very small" in relation to the other element in its row (and viceversa). If you repeat the previous computations with this case with three-digit arithmetic, without swapping the rows, you will get the numerical solution $x = 0$, $y = 1$ (!). By swapping the two rows, you get the more reasonable approximation $x = 1$, $y = 1$.

This is what SPP tries to solve. SPP means selecting the row whose pivot element has the highest relative absolute value. That is, with SPP, at the $k$-th iteration of Gaussian elimination, you swap the current pivot row, at index $k$, with the row at index

$$ \arg\max_{i \in \{k, \ldots, n\}} \frac{\left| a_{i, k} \right|}{\displaystyle \max_{j \in \{k, \ldots, n\}} |a_{i,j}|}\,, $$

where $n$ is the size of the matrix.