Cost of Gaussian Elimination

Question

Reference: Linear Algebra and Its Applications, Fourth Edition Gilbert Strang.

How many separate arithmetical operations does elimination require, for n equations in n unknowns?

While addressing this question in above book, it is said that if we look at only left side calculations for Gaussian elimination then (n^3 - n)/3 operations are required.

When n is large good estimate is n^3/3.

After that i didn't understand this statement,"If the size is doubled, and few of the coefficients are zero, the cost is multiplied by 8." Shouldn't cost (no.of operations) of elimination be multiplied by 8/3 if size (n) is doubled?

How few of coefficient being zero reduces the number of operations required in Gaussian elimination?

Answer 1

The factor of $\frac13$ is canceled.

$$\frac{\frac{(2n)^3}{3}}{\frac{n^3}{3}}=\frac{(2n)^3}{n^3}=8$$

If the matrix is sparse, then we can omit some steps. For example, we zero out elements using the pivot element, if it is already zero in the first place, we can skip that step.

Answer 2

You are looking at $\frac{n^3}{3}$ vs $\frac{(2n)^3}{3} = \frac{8n^3}{3} = 8 \left(\frac{n^3}{3}\right)$.

The $\frac{1}{3}$ does not change when the size is doubled, so it has the same effect before and after the size is doubled.