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}