The Cost of Elimination

You can solve a system by reducing it to Gaussian Elimination and Echelon Form and back substituting. On a computer the question becomes: how much work is that? We count flops (floating-point operations): each addition, subtraction, multiplication or division counts as one.

Key idea

Gaussian elimination on an $n \times n$ matrix takes about $\frac{2}{3}n^{3}$ flops; each triangular solve (forward or back substitution) takes about $n^{2}$. Doubling $n$ multiplies the elimination work by about $2^{3} = 8$.

Why it works

At step $k$, each of the $n - k$ rows below the pivot gets a multiplier (one division) and then has $n - k$ entries updated, each with a multiply and a subtract: about $2(n - k)^{2}$ flops for the step. Adding up, $$\sum_{k=1}^{n-1}2(n - k)^{2} = 2\sum_{j=1}^{n-1}j^{2} \approx \frac{2}{3}n^{3}.$$ In back substitution, the row $i$ places from the bottom needs $i - 1$ multiplies, $i - 1$ subtracts and one divide: $\sum_{i=1}^{n}(2i - 1) = n^{2}$.

The cubic term dominates quickly.
$n$	elimination, $\frac{2}{3}n^{3}$	time at $10^{9}$ flops/s	back substitution, $n^{2}$
$100$	$6.7 \times 10^{5}$	under a millisecond	$10^{4}$
$1{,}000$	$6.7 \times 10^{8}$	about $0.7$ s	$10^{6}$
$10{,}000$	$6.7 \times 10^{11}$	about 11 minutes	$10^{8}$

Worked example: Scaling up

Elimination on a $1{,}000 \times 1{,}000$ system takes $0.5$ s. Estimate the time for $2{,}000 \times 2{,}000$ and for $10{,}000 \times 10{,}000$.

Work grows like $n^{3}$. Doubling $n$: $2^{3} = 8$ times the work, about $4$ s.
Multiplying $n$ by 10: $10^{3} = 1000$ times, about $500$ s, over 8 minutes.

Answer: about $4$ s and about $500$ s

Worked example: Back substitution exactly

Count the flops of back substitution for $n = 4$.

Bottom row: $x_4 = c_4/u_{44}$, 1 division.
Next rows: $3$, then $5$, then $7$ flops (each adds one multiply and one subtract).
Total $1 + 3 + 5 + 7 = 16 = 4^{2}$.

Answer: $16$

Worked example: Many right-hand sides

A program must solve $A\mathbf{x} = \mathbf{b}$ for 100 different $\mathbf{b}$, with $n = 1000$. Compare redoing elimination each time with factoring once.

Redo each time: $100 \times \frac{2}{3}(1000)^{3} \approx 6.7 \times 10^{10}$ flops.
Factor once ($PA = LU$, about $\frac{2}{3}n^{3} \approx 6.7 \times 10^{8}$), then two triangular solves per $\mathbf{b}$ ($100 \times 2n^{2} = 2 \times 10^{8}$): about $8.7 \times 10^{8}$ in all.
About 77 times less work. This is why libraries separate "factor" from "solve".

Answer: factoring once is about 77 times cheaper

Operation counts, and times at a billion operations per second, for three ways to solve many systems with the same matrix.

The same counting shows why computing $A^{-1}$ is a poor way to solve: forming the inverse means solving with all $n$ columns of the identity, about $2n^{3}$ flops, three times the cost of one elimination, and the product $A^{-1}\mathbf{b}$ is usually less accurate than elimination with pivoting.

Common mistake

Computing $A^{-1}$ to solve $A\mathbf{x} = \mathbf{b}$. Even with many right-hand sides, an $LU$ factorization reused for each $\mathbf{b}$ costs no more than $A^{-1}$ and gives better answers. Write $\mathbf{x} = A^{-1}\mathbf{b}$ on paper if you like; on a computer, solve.

Sources and further reading

Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation (University of Delaware, free online edition): chapter "Square linear systems", section "Efficiency of matrix computations"

MIT OpenCourseWare 18.335J, Introduction to Numerical Methods: lecture notes on Gaussian elimination and its cost

The Cost of Elimination

Practice

Builds on

Leads to

Sources and further reading