0

I've seen partial pivoting described thus: during the $k$th step of LU factorization of $\mathbf{A}$, find the remaining element of $\mathbf{A}$ in column $k$ with the greatest absolute value, and swap its row with the $k$th row.

However, I can think of one example where this strategy leads to division-by-zero: $$\mathbf{A} = \begin{bmatrix}6&3&6\\5&\frac{5}{2}&8\\3&1&4\end{bmatrix}$$This matrix has been chosen such that the greatest values in each column are already on the diagonal, so no swapping should be necessary, according to this strategy. In this example, $u_{2,2} = 0$, and computing $l_{3,2}$ will require dividing by zero.

Am I misunderstanding the concept of partial pivoting? It seems that the problem arises from trying to choose the row based on the greatest value in $\mathbf{A}$, but I think it would make more sense to choose the row that results in the greatest value in $\mathbf{U}$. I'm not sure if that's correct, or how that could be applied practically.

Will
  • 505

2 Answers2

1

Partial pivoting is kind of 'dynamic', we should consider potential row swap for during each column pivoting.

From your matrix example, yes for the first column, no row swap needed, after row operation, your $u_{2,2} = 0, u_{3,2}= -0.5$, we need a row swap between row 2 and row 3! Updated to $u_{3,2} = 0, u_{2,2}= -0.5$ and $l_{3,2} = 0$.

Draditate
  • 119
  • Only when the remaining element in column are all zero entry, this is when we cannot proceed any further (no matter usual LU or LU with partial pivoting). – Draditate Aug 27 '20 at 04:29
  • OK, so it sounds like we must first calculate all possible $u_{i,k}$ values in column $k$ before deciding which one to use as the pivot, right? Algorithmically that seems like a big waste, unless I'm missing something. – Will Aug 27 '20 at 04:41
  • An common strategy to chose the pivot at step k is to look under the current pivot location and take the element with the largest absolute value – Miguel Aug 27 '20 at 06:22
  • @Miguel, that strategy is what led to the div-by-zero in the example above. Is that strategy supposed to work on all (nonsingular) matrices? – Will Aug 27 '20 at 14:22
  • Yes, it works on all nonsingular matrices (I'm writing a more detailed answer) – Miguel Aug 27 '20 at 14:31
1

There are multiple strategies on how to chose a pivot, depending on the type of factorisation that you do ($PA = LU$, $AQ = LU$, $PAQ = LU$), with $PA = LU$ (partial pivoting of the rows) being the most commonly used. In this case, we typically chose the pivot at step $k$ to be the element of the $k$-th column with the largest magnitude (and row $\ge k$)

Here is how it works if done on your matrix:

$$ A = \begin{bmatrix} 6 & 3 & 6 \\ 5 & 5/2 & 8\\ 3 & 1 & 4 \end{bmatrix} $$

We are at step 1, so we look at the first column: the largest element is the $6$ in the first row, so we don't need to swap rows. Applying Gaussian elimination gives:

\begin{bmatrix} 6 & 3 & 6 \\ 0 & 0 & 3\\ 0 & -1/2 & 1 \end{bmatrix}

the we begin step 2: the largest element in the second column (and row $\ge 2$) is the $-1/2$ on row 3, so we chose it as our next pivot. Note that in general, the $k$-th pivot is chosen at step $k$ and can't be computed beforehand (which leads to some interesting challenges with sparse matrices but I digress).

The chosen pivot is not on the second row, so we need to swap row 2 and 3, and then proceed with the elimination.

\begin{bmatrix} 6 & 3 & 6 \\ 0 & -1/2 & 1\\ 0 & 0 & 3 \end{bmatrix}

In this case, it turns out that the elimination is complete, nut in general the element in position (3,2) is not zero.

Miguel
  • 231
  • I think I misinterpreted your comment on @Draditate's answer. We are not choosing the greatest element in the $k$th column of the original matrix $\mathbf{A}$, but rather from the work-in-progress matrix $\mathbf{U}$ with all previous row operations applied. – Will Aug 27 '20 at 15:05
  • Yes, that is right, sorry for the confusion – Miguel Aug 27 '20 at 15:09
  • For the OP, regarding @Miguel's digression, in sparse LU factorization, people sometimes use static pivoting where the reordering is chosen before the factorization is computed (doing this well is challenging). This is less accurate, but usually accurate enough that an accurate solution can be recovered using iterative refinement – eepperly16 Aug 27 '20 at 18:07