The Cost of Gaussian Elimination Explained
apurba
What is Gaussian Elimination?
Gaussian Elimination is a method used to solve systems of linear equations. It systematically eliminates variables to reduce the system into an upper triangular form, followed by back-substitution to find the unknowns.
Essentially, it answers: “How can we convert any system of equations into a simpler one that’s easy to solve?”
Why Analyze Its Cost?
When solving large systems (with n equations and n unknowns), we usually let computers perform the elimination. But before running the algorithm, it’s crucial to know how much computational effort it will take.
In Gaussian Elimination, the main question is:
“How many arithmetic operations (additions, subtractions, multiplications, and divisions) are needed?”
Types of Operations
During elimination, two main types of operations occur:
- Division → To find the multiplier
λ(pivot ratio). - Multiply–Subtract → To eliminate elements below the pivot (each considered one operation).
So every time we zero out an element below the pivot, we perform a division and several multiply–subtracts.
Step-by-Step Cost Analysis
First Column
We eliminate elements below the first pivot.
- There are
(n − 1)rows below it. - For each row, roughly
noperations are needed (to modify entries along that row).
Total ≈ n(n − 1) = n² − n operations.
Next Columns
In the next steps, the system gets smaller:
- When only
kequations remain, the cost per stage is roughlyk² − k.
To find the total cost, we sum over all stages:
Σ (k² − k) from k=1 to n
= (1² + 2² + … + n²) − (1 + 2 + … + n)
= (1/3)(n³ − n)
Total Forward Elimination Cost
Hence, Forward Elimination requires approximately:
(1/3)(n³ − n) ≈ (1/3)n³That’s O(n³) complexity.
If you double the size (n → 2n), the cost increases roughly 8×.
Back-Substitution Cost
Once the matrix is in upper-triangular form:
- The last variable needs 1 operation.
- The second-last needs 2 operations, and so on.
Total:
1 + 2 + 3 + … + n = (n(n+1))/2 ≈ (1/2)n²That’s much faster — O(n²).
Right-Hand Side (RHS) Operations
The right-hand side (the constants of each equation) also gets updated during elimination, adding roughly:
n²operations in total — still smaller than the cubic cost of elimination.
Total Computation Summary
| Stage | Type | Approximate Operations | Complexity |
|---|---|---|---|
| Forward Elimination | Pivot elimination | (n³ / 3) | O(n³) |
| Back Substitution | Solving unknowns | (n² / 2) | O(n²) |
| RHS Updates | Maintaining equations | (n²) | O(n²) |
| Total | ≈ n³ / 3 | O(n³) |
Can It Be Faster?
Originally, mathematicians believed that no method could beat (n³ / 3) operations. But the Strassen’s algorithm surprised everyone by multiplying matrices using only 7 multiplications instead of 8.
That reduced the complexity from n³ to nlog₂7 ≈ n2.8.
Further research (notably at IBM) pushed the exponent even lower to about 2.376.
However, in practice:
- These algorithms have large constants (C).
- They are hard to implement.
- They offer little advantage for typical problem sizes.
So, Gaussian Elimination remains the most practical and reliable method in real-world numerical computing.