Counting Operations in Gaussian Elimination

This page is intended to be a part of the Numerical Analysis section of Math Online. Similar topics can also be found in the Linear Algebra section of the site.

# Counting Operations in Gaussian Elimination

We have seen from The Gaussian Elimination Algorithm and the Computing the Inverse of a Matrix with Gaussian Elimination pages that solving a system of $n$ linear equations in $n$ unknowns, or finding the inverse (provided that it exists) of a square $n \times n$ matrix requires a lot of arithmetic steps, especially when $n$ is very large. It is thus important to determine the length of the computation in terms of counting the number of operations done in the process.

Consider a system of $n$ linear equations in $n$ unknowns and the corresponding $n \times n$ coefficient matrix $A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}$, the $n \times 1$ solution matrix $x = \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix}$, and the $n \times 1$ constant matrix $b = \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_n \end{bmatrix}$. Then $Ax = b$. Earlier we saw that at the $(n-1)^{\mathrm{th}}$ step of Gaussian Elimination, we obtain the following system of equations:

(1)
\begin{align} \quad u_{11}x_1 + u_{12}x_2 + \cdots + u_{1n} x_n = g_2 \\ u_{22}x_2 + \cdots + u_{2n} x_n = g_2 \\ \vdots \\ u_{nn}x_n = g_n \end{align}

The values of the $u$'s and the $g$'s were described on the The Gaussian Elimination Algorithm page. Let $U = \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{nn}\\ 0 & u_{22} & \cdots & u_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & u_{nn}\end{bmatrix}$ be the $n \times n$ coefficient matrix for this equivalent system, and let $g = \begin{bmatrix} g_1\\ g_2\\ \vdots\\ g_n \end{bmatrix}$ be the $n \times 1$ equivalent constant matrix. Then $Ux = g$. Then the following table states the operations count from going from $A$ to $U$ at each step $1, 2, ..., n -1$.

Step Number Number of Additions/Subtractions from $A \to U$ Number of Multiplications from $A \to U$ Number of Divisions from $A \to U$
$1$ $(n - 1)^2$ $(n - 1)^2$ $n - 1$
$2$ $(n - 2)^2$ $(n - 2)^2$ $n - 2$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$1$ $4$ $4$ $2$
$n-1$ $1$ $1$ $1$
Totals: $\mathrm{Total \: Num. \: of \: Add/Sub} = \frac{n(n-1)(2n-1)}{6}$ $\mathrm{Total \: Num. \: of \: Multiplications} = \frac{n(n-1)(2n-1)}{6}$ $\mathrm{Total \: Num. \: of \: Divisions} = \frac{n(n-1)}{2}$

We will count the number of additions/subtractions together and the number of multiplications/divisions together. The total number of additions/subtractions and multiplications/divisions in going from $A \to U$ is:

(2)
\begin{align} \quad \mathrm{Total \: Number \: of \: Additions / Subtractions \: from \: A \to U} = \frac{n(n-1)(2n-1)}{6} \end{align}
(3)
\begin{align} \quad \mathrm{Total \: Number \: of \: Multiplications / Divisions \: from \: A \to U} = \frac{n(n-1)(2n-1)}{6} + \frac{n(n-1)}{2} = \frac{n(n-1)(2n-1)}{6} + \frac{3n(n-1)}{6} = \frac{n(n^2 - 1)}{3} \end{align}

We will now count the number of additions/ subtractions and the number of multiplications/divisions in going from $b \to g$. We have that:

(4)
\begin{align} \quad \mathrm{Total \: Number \: of \: Additions / Subtractions \: from \: b \to g} = (n-1) + (n-2) + ... + 2 + 1 = \frac{n(n-1)}{2} \end{align}
(5)
\begin{align} \quad \mathrm{Total \: Number \: of \: Multiplications / Divisions \: from \: b \to g} = (n-1) + (n-2) + ... + 2 + 1 = \frac{n(n-1)}{2} \end{align}

Lastly we count the number of additions/subtractions and multiplications/divisions for finding the solutions from the back-substitution method.

(6)
\begin{align} \quad \mathrm{Total \: Number \: of \: Additions / Subtractions \: from \: g \to x} = 0 + 1 + ... + (n-1) = \frac{n(n-1)}{2} \end{align}
(7)
\begin{align} \quad \mathrm{Total \: Number \: of \: Multiplications / Divisons \: from \: g \to x} = 1 + 2 + ... + n = \frac{n(n+1)}{2} \end{align}

Therefore the total number of operations to obtain the solution of a system of $n$ linear equations in $n$ variables using Gaussian Elimination is:

(8)
\begin{align} \quad \mathrm{Total \: Number \: of \: Additions / Subtractions \: to \: Obtain \: Solution} = \frac{n(n-1)(2n+5)}{6} \end{align}
(9)
\begin{align} \quad \mathrm{Total \: Number \: of \: Multiplications / Divisinons \: to \: Obtain \: Solution} = \frac{n(n^2 + 3n - 1)}{3} \end{align}