Counting Operations in Gaussian Elimination

Why Count Elimination Operations?

Gaussian elimination turns a matrix into upper-triangular form through a sequence of stages. Each stage works on a smaller trailing part of the matrix than the one before it. Counting the arithmetic at those stages explains why elimination on an \(n\times n\) matrix becomes costly as \(n\) grows, and why its dominant work scales cubically rather than quadratically.

We will count scalar additions, subtractions, multiplications and divisions. Each counts as one arithmetic operation. In particular, updating an entry by \(a_{ij}\leftarrow a_{ij}-\ell_{ik}u_{kj}\) costs one multiplication and one subtraction, or two operations. This is the usual scalar-operation convention; it is not a count of processor instructions or elapsed time.

If a pivot is zero, an exchange of rows may be needed, or elimination may stop if no suitable pivot is available. The count below describes a completed elimination; it applies, for example, when row exchanges allow the process to continue through all stages. Pivot searches and exchanges are separate from the scalar-arithmetic count. Their cost is not included here.

What Happens at One Stage?

Number the pivots \(k=1,\dots,n-1\). At stage \(k\), the pivot is in column \(k\), and the rows below it are updated to make their entries in that column zero. There are \(n-k\) such rows. For each row \(i>k\), the multiplier is \(\ell_{ik}=a_{ik}/u_{kk}\), which takes one division. Thus stage \(k\) uses \(n-k\) divisions.

After calculating a multiplier, elimination updates the entries to the right of the pivot. There are \(n-k\) remaining columns and \(n-k\) rows below the pivot, so the trailing block being updated has \((n-k)^2\) entries. Each entry requires one multiplication and one subtraction. Therefore, at stage \(k\), there are \((n-k)^2\) multiplications and the same number of subtractions.

Summing the Stage Counts

As the stage index \(k\) increases, the number \(n-k\) runs through \(n-1,n-2,\dots,1\). So the total divisions are the sum of these integers, while the total multiplications and subtractions are each the sum of their squares.

Proof. Both identities hold for \(m=1\): the sums are \(1\), and the formulas also give \(1\). Suppose they hold for \(m\). For the first identity, adding the next term gives \(m(m+1)/2+(m+1)=(m+1)(m+2)/2\). For the sum of squares, adding \((m+1)^2\) gives

These are exactly the two formulas with \(m+1\) in place of \(m\). By induction, both identities hold for every positive integer \(m\). \(\square\)

Proof. At stage \(k\), there are \(n-k\) divisions and \((n-k)^2\) multiplications and subtractions. Summing over \(k=1,\dots,n-1\), and writing \(j=n-k\), the division count is \(\sum_{j=1}^{n-1}j\). By the lemma, it equals \(n(n-1)/2\). The multiplication count is \(\sum_{j=1}^{n-1}j^2\), which by the lemma equals \(n(n-1)(2n-1)/6\); the subtraction count is identical because each update has one of each. Adding all three counts gives twice the sum of squares plus the sum of integers, namely \(n(n-1)(2n-1)/3+n(n-1)/2\). Expanding the products yields \(C_n=2n^3/3-n^2/2-n/6\), as claimed. When \(n=1\), there are no stages, and this formula gives \(C_1=0\), so it also covers that case. \(\square\)

The Cubic Growth Term

The exact expression contains a cubic term, a quadratic term and a linear term. For large \(n\), the cubic term dominates: the leading operation count is \(\frac{2}{3}n^3\). This does not mean the exact count is \(\frac{2}{3}n^3\); the lower-order terms give a correction, which can matter for moderate matrix sizes.

The coefficient \(2/3\) follows from the counting convention. The trailing updates involve about \(n^3/3\) entries in total, and each entry takes two arithmetic operations. If one groups a multiplication and subtraction together as a single update, there are about \(n^3/3\) such updates instead. These are different ways of reporting the work, so a count must say which convention it uses.

Interpreting the Estimate

A cubic leading term has a practical consequence: multiplying the matrix size by a factor of \(r\) multiplies the leading estimate by \(r^3\). For example, increasing \(n\) from \(100\) to \(1000\) multiplies the leading estimate by \(10^3=1000\). The exact totals above have a ratio of about \(1007\), because the lower-order terms have a larger relative effect at \(n=100\).

An operation count is a model of arithmetic work, not a direct prediction of runtime. Actual time also depends on the computer, implementation, memory movement, parallel execution and the rate at which operations are completed. For instance, at a hypothetical sustained rate of \(10^9\) counted operations per second, the \(1000\times1000\) count corresponds to \(666{,}166{,}500/10^9=0.6661665\) seconds. This is an estimate under that assumed rate, not a guarantee of elapsed time.

The calculation also excludes pivot selection. In partial pivoting, choosing a pivot involves comparing candidate entries, and row exchanges rearrange rows. Those tasks are not scalar additions, subtractions, multiplications or divisions in our count. The central cubic term describes the trailing-matrix arithmetic; it should not be mistaken for a complete accounting of every implementation cost.

Common Counting Pitfalls

Counting each update as only one arithmetic operation. The update \(a_{ij}\leftarrow a_{ij}-\ell_{ik}u_{kj}\) contains a multiplication and a subtraction. Under the scalar-operation convention used here, that is two operations. Calling it one update is fine if the unit is stated, but it gives a different total from counting scalar arithmetic.

Using the wrong stage size. Stage \(k\) updates a square trailing block of size \((n-k)\times(n-k)\), not an \(n\times n\) block at every stage. For \(n=4\), the update counts by stage are \(3^2=9\), \(2^2=4\), and \(1^2=1\), for \(14\) updates total. Adding \(9+4+1=14\) directly checks the sum-of-squares formula.

Mixing the leading estimate with the exact count. For \(n=100\), the leading term is \(666{,}666\frac{2}{3}\), while the exact count is \(661{,}650\). The leading term is useful for describing large-scale growth; the exact formula is needed when a precise count is requested.