LINEAR-ALGEBRA · Unit 4 · Video 3 · Interactive Practice

How Expensive Is Gaussian Elimination? Operation Count Explained

IKey Formulas

Formula Name Description
12+22+⋯+n2=n(n+1)(2n+1)61^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} Sum of squares Exact formula for the total elimination cost
Elimination≈13n3\text{Elimination} \approx \tfrac{1}{3}n^3 Gaussian elimination cost Approximate flop count for forward elimination
Each RHS≈n2\text{Each RHS} \approx n^2 Triangular solve cost Forward sub (12n2\tfrac{1}{2}n^2) + back sub (12n2\tfrac{1}{2}n^2)
LU total=13n3+m⋅n2\text{LU total} = \tfrac{1}{3}n^3 + m \cdot n^2 LU with mm right-hand sides Factor once, solve mm times

IIVisualization 1 — Where ⅓n³ Comes From

The per-step costs k2k^2 stack into the area under x2x^2, so the total is about 13n3\tfrac{1}{3}n^3.

IIIVisualization 2 — The Shrinking Active Block

Each elimination step works only on the shrinking active block, so its cost falls as (n−k)2(n{-}k)^2.

IVVisualization 3 — Factor Once, Solve Many

Factor once for 13n3\tfrac{1}{3}n^3, then each of mm solves costs only n2n^2 — how big is the payoff over re-eliminating every time?

💡 Even at m=1m = 1 LU already wins, and the payoff climbs toward n/3n/3 — which is why numerical libraries factor once and reuse LL and UU for every right-hand side.

VQuiz Questions

Question 1

A matrix is n=100n = 100. What is the approximate flop count for Gaussian elimination (forward elimination only)?

✅ Correct! Gaussian elimination costs approximately ⅓n³ flops, which comes from summing the squares n² + (n−1)² + ⋯ + 1².

❌ Not quite. Remember: the total cost is the sum of squares 1² + 2² + ⋯ + n², which equals approximately ⅓n³.

Show solution

Solution:

The cost of Gaussian elimination is approximately 13n3\tfrac{1}{3}n^3 flops.

For n=100n = 100: 13×1003=1,000,0003≈333,333\frac{1}{3} \times 100^3 = \frac{1{,}000{,}000}{3} \approx 333{,}333

The exact sum is 12+22+⋯+1002=100×101×2016=338,3501^2 + 2^2 + \cdots + 100^2 = \frac{100 \times 101 \times 201}{6} = 338{,}350, which is within 2% of the 13n3\tfrac{1}{3}n^3 approximation.

  • n2/2=5,000n^2 / 2 = 5{,}000 — this would be the cost of one triangular solve, not full elimination.
  • n2=10,000n^2 = 10{,}000 — this is the cost per right-hand side after factorization.
  • n3=1,000,000n^3 = 1{,}000{,}000 — too large by a factor of 3.

Question 2

True or False: Once you have the LU factorization stored, each additional right-hand side costs approximately 13n3\tfrac{1}{3}n^3 flops to solve.

✅ Correct! Each additional RHS costs only about n² (two triangular solves), not ⅓n³. That's the whole benefit of LU factorization!

❌ Not quite. Think about what work remains once L and U are already computed — you only need forward and back substitution.

Show solution

Solution: False

Once LL and UU are stored, each right-hand side requires only two triangular solves:

  1. Forward substitution (Lc=bLc = b): row kk needs k−1k{-}1 operations → total ≈12n2\approx \tfrac{1}{2}n^2
  2. Back substitution (Ux=cUx = c): row kk needs k−1k{-}1 operations → total ≈12n2\approx \tfrac{1}{2}n^2

Combined cost per RHS =12n2+12n2=n2= \tfrac{1}{2}n^2 + \tfrac{1}{2}n^2 = n^2 — not 13n3\tfrac{1}{3}n^3.

This is the entire point of LU factorization: the expensive 13n3\tfrac{1}{3}n^3 work is done once during factorization. Each subsequent solve is vastly cheaper at only n2n^2.

Question 3

You have a 1000×10001000 \times 1000 system with 100 different right-hand sides. What is the approximate speedup of LU factorization over running naive Gaussian elimination 100 separate times?

Hint: Naive cost =100×13n3= 100 \times \tfrac{1}{3}n^3. LU cost =13n3+100×n2= \tfrac{1}{3}n^3 + 100 \times n^2.

✅ Correct! LU saves a factor of ~77 by avoiding 99 redundant eliminations. The speedup approaches n/3 = 333 as more RHS are added.

❌ Not quite. Try computing both costs explicitly: Naive = 100 × ⅓ × 10⁹ and LU = ⅓ × 10⁹ + 100 × 10⁶, then divide.

Show solution

Solution:

With n=1000n = 1000 and m=100m = 100:

Naive approach: 100×13(1000)3=100×333,000,000=33,300,000,000≈33.3 billion flops100 \times \tfrac{1}{3}(1000)^3 = 100 \times 333{,}000{,}000 = 33{,}300{,}000{,}000 \approx 33.3 \text{ billion flops}

LU approach: 13(1000)3⏟333,000,000+100×(1000)2⏟100,000,000=433,000,000≈433 million flops\underbrace{\tfrac{1}{3}(1000)^3}_{333{,}000{,}000} + \underbrace{100 \times (1000)^2}_{100{,}000{,}000} = 433{,}000{,}000 \approx 433 \text{ million flops}

Speedup: 33,300,000,000433,000,000≈76.9≈77×\frac{33{,}300{,}000{,}000}{433{,}000{,}000} \approx 76.9 \approx \mathbf{77\times}

Same answers, 77 times less work!

Why not 333×? Because the first factorization still costs ⅓n³ in the LU approach. The speedup approaches n/3=333n/3 = 333 only as m→∞m \to \infty.

Question 4

For a 5×55 \times 5 matrix, elimination proceeds through steps k=0,1,2,3,4k = 0, 1, 2, 3, 4. At step kk, the active submatrix has size (5−k)×(5−k)(5{-}k) \times (5{-}k). What is the cost of the second elimination step (k=1k = 1)?

✅ Correct! After step k=0 eliminates the first row and column, the active region is 4×4, costing (5−1)² = 16 flops.

❌ Not quite. At step k=1, one row and one column have already been eliminated. The active submatrix size is (n−k) = (5−1) = 4.

Show solution

Solution:

For a 5×55 \times 5 matrix (n=5n = 5), the cost at each step:

Step kk Active size Cost
k=0k = 0 (first) 5×55 \times 5 52=255^2 = 25
k=1k = 1 (second) 4×44 \times 4 42=164^2 = 16
k=2k = 2 (third) 3×33 \times 3 32=93^2 = 9
k=3k = 3 (fourth) 2×22 \times 2 22=42^2 = 4
k=4k = 4 (fifth) 1×11 \times 1 12=11^2 = 1

At step k=1k = 1, the first row and column have been eliminated, leaving a (5−1)×(5−1)=4×4(5{-}1) \times (5{-}1) = 4 \times 4 active submatrix. The cost is 42=164^2 = \mathbf{16} flops.

Verification: Total =25+16+9+4+1=55=5×6×116= 25 + 16 + 9 + 4 + 1 = 55 = \frac{5 \times 6 \times 11}{6} ✓

Solved: 0 / 4