Back to the on-screen lesson ·
What elimination and Cholesky cost in work and storage, why a factorisation is kept rather than repeated, and what partial pivoting actually buys in the backward error analysis.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to count the work and storage of the standard factorisations, choose one from the structure of the matrix, state the backward error bound for elimination and where the growth factor enters it, and say what pivoting does not buy.
You can eliminate, pivot and factorise, and you know a matrix condition number and what backward stability means. This lesson asks what those factorisations cost, and what exactly pivoting is buying in the backward error analysis.
A flop is one arithmetic operation. The growth factor $\rho$ is the largest entry met during elimination divided by the largest entry of $A$. Partial pivoting takes the largest entry of the column as the pivot; the multipliers are then at most one in size. A matrix is positive definite when $x^{\mathsf{T}}Ax > 0$ for every non-zero $x$, which is what makes Cholesky possible.
Elimination costs about $\tfrac23 n^{3}$ operations; a triangular solve costs $n^{2}$. The ratio is the reason a factorisation is kept: the expensive part depends on $A$ alone, so a second right-hand side costs two solves rather than another elimination. For a symmetric positive definite matrix, Cholesky computes $A = LL^{\mathsf{T}}$ at half the work and half the storage, and needs no pivoting at all, because positive definiteness guarantees a positive pivot at every step. What pivoting is for is subtler than avoiding division by zero. Writing every rounded operation as exact-times-$(1 + \delta)$ and collecting gives $\hat{L}\hat{U} = A + E$ exactly, and the computed solution satisfies $(A + \Delta)\hat{x} = b$ with
$$\|\Delta\| \;\lesssim\; c\,n\,\rho\,\varepsilon\,\|A\|,$$
where $\rho$ is the growth factor. Partial pivoting keeps the multipliers at most one, which is what keeps $\rho$ from exploding — so pivoting buys backward stability, not accuracy. The forward error is still $\kappa(A)$ times that bound, and no arrangement of the elimination touches $\kappa$. The worst case for $\rho$ under partial pivoting is $2^{n-1}$, attained by matrices built for the purpose; in practice it is about ten, on essentially everything, and why remains one of the open questions of the subject.
Another way: steps
Another way: example
$A = \begin{pmatrix} 4 & 2 \\ 2 & 5 \end{pmatrix}$ is symmetric positive definite. Cholesky: $l_{11} = 2$, $l_{21} = 1$, $l_{22} = \sqrt{5 - 1} = 2$, so $L = \begin{pmatrix} 2 & 0 \\ 1 & 2 \end{pmatrix}$. A negative number under the root would have proved $A$ was not positive definite — the factorisation is also the test.
Pivoting is remembered as a way of avoiding a zero pivot, and is then thought unnecessary when no pivot happens to be zero. A small pivot is the real danger: it makes the multipliers enormous, the entries grow, and the elimination becomes unstable without anything dividing by zero. The second mistake is to expect pivoting to improve the answer on an ill-conditioned system. It shrinks the backward error, which was already going to be small; the forward error is that times $\kappa$, and $\kappa$ is untouched.
$\begin{pmatrix} 10^{-20} & 1 \\ 1 & 1 \end{pmatrix}$, no pivoting: the multiplier is $10^{20}$.
Nothing divided by zero.
The $(2,2)$ entry becomes $1 - 10^{20}$, which rounds to $-10^{20}$ — the original $1$ has been lost entirely.
Catastrophic growth.
Swap the rows first: the multiplier is $10^{-20}$ and nothing is lost.
The whole of what pivoting does.
$n = 1000$: elimination is about $6.7 \times 10^{8}$ operations.
The one-off cost.
Each further right-hand side is two triangular solves: about $2 \times 10^{6}$.
Three hundred times cheaper.
The factor is lower triangular: the diagonal and everything below.
That is $\dfrac{6 \times 7}{2} = 21$ entries.
Against $36$ for the full matrix — and it can be written over the lower triangle of $A$, which was redundant anyway since $A$ is symmetric.
A symmetric positive definite matrix of size $6$ is factorised as $A = LL^{\mathsf{T}}$. How many entries of $L$ have to be stored?
Answer:
A system of size $n = 12$ is to be solved. Using $\tfrac23 n^{3}$ for elimination, $\tfrac13 n^{3}$ for Cholesky and $n^{2}$ for one triangular solve, give each cost.
| Stage | Operations | |
|---|---|---|
| Elimination | $\tfrac23 n^{3}$ | |
| Cholesky | $\tfrac13 n^{3}$ | |
| One triangular solve | $n^{2}$ |
Match each matrix to the factorisation it calls for.
| Cholesky: half the work, half the storage, no pivoting | LU with partial pivoting | $LDL^{\mathsf{T}}$ with block pivots, keeping the symmetry | No dense factorisation: the factors fill in | |
|---|---|---|---|---|
| Symmetric positive definite, of moderate size | ||||
| General and invertible | ||||
| Symmetric but indefinite | ||||
| Large and sparse |
Partial pivoting chooses the largest entry in the column as the pivot. What does that buy, in the backward error analysis?
Elimination with partial pivoting on a $3 \times 3$ matrix produced an upper factor with diagonal $6$, $3$, $2$, after $1$ row interchanges. Give the product of that diagonal and the determinant of the original matrix.
Product w, determinant z.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Put the five steps of the backward error analysis of Gaussian elimination into order.
Number the steps in order (write the number in the box):
You can cost a factorisation, choose one for a given matrix and state the backward error bound. Say in your own words why a small pivot is dangerous even though nothing divides by zero.
8. Your turn: the storage for a Cholesky factor of a $6 \times 6$ matrix, step 3