Speed of Calculating Determinants

For large matrices, finding the determinant by using row operations is typically much faster than using the permutation expansion. We make this statement precise by finding how many operations each method performs.

To compare the speed of two algorithms, we find for each one how the time taken grows as the size of its input data set grows. For instance, if we increase the size of the input by a factor of ten does the time taken grow by a factor of ten, or by a factor of a hundred, or by a factor of a thousand? That is, is the time taken proportional to the size of the data set, or to the square of that size, or to the cube of that size, etc.? An algorithm whose time is proportional to the square is faster than one that takes time proportional to the cube.

First consider the permutation expansion formula.

$$\left|\begin{array}{cccc}{t}_{1,1}& t_{1,2}& \dots & t_{1,n}\\ t_{2,1}& t_{2,2}& \dots & t_{2,n}\\ & ⋮\\ t_{n,1}& t_{n,2}& \dots & t_{n,n}\end{array}\right|=\sum _{\text{permutations }\varphi }{t}_{1,\varphi (1)}{t}_{2,\varphi (2)}\cdots t_{n,\varphi (n)}\left|P_{\varphi }\right|$$

There are $n!=n\cdot (n-1)\cdots 2\cdot 1$ different $n$-permutations so for a matrix with $n$ rows this sum has $n!$ terms (and inside each term is $n$-many multiplications). The factorial function grows quickly: when $n$ is only $10$ the expansion already has $10!=3,628,800$ terms. Observe that growth proportional to the factorial is bigger than growth proportional to the square $n!>n^2$ because multiplying the first two factors in $n!$ gives $n\cdot (n-1)$, which for large $n$ is approximately $n^2$ and then multiplying in more factors will make the factorial even larger. Similarly, the factorial function grows faster than $n^3$, etc. So an algorithm that uses the permutation expansion formula, and thus performs a number of operations at least as large as the factorial of the number of rows, would be very slow.

In contrast, the time taken by the row reduction method does not grow so fast. Below is a script for row reduction in the computer language Python. (Note: The code here is naive; for example it does not handle the case that the m(p_row, p_row) entry is zero. Analysis of a finished version that includes all of the tests and subcases is messier but would gives us roughly the same speed results.)

import random

def random_matrix(num_rows, num_cols):
    m = []
    for col in range(num_cols):
        new_row = []
        for row in range(num_rows):
            new_row.append(random.uniform(0,100))
        m.append(new_row)
    return m

def gauss_method(m):
    """Perform Gauss's Method on m.  This code is for illustration only
    and should not be used in practice.
      m  list of lists of numbers; each included list is a row
    """
    num_rows, num_cols = len(m), len(m[0])
    for p_row in range(num_rows):
        for row in range(p_row+1, num_rows):
            factor = -m[row][p_row] / float(m[p_row][p_row])
            new_row = []
            for col_num in range(num_cols): 
                p_entry, entry = m[p_row][col_num], m[row][col_num]
                new_row.append(entry+factor*p_entry)
            m[row] = new_row
    return m

response = raw_input('number of rows? ')
num_rows = int(response)
m = random_matrix(num_rows, num_rows)
for row in m:
    print row
M = gauss_method(m)
print "-----"
for row in M:
    print row

Besides a routine to do Gauss’s Method, this program also has a routine to generate a matrix filled with random numbers (the numbers are between $0$ and $100$, to make them readable below). This program prompts a user for the number of rows, generates a random square matrix of that size, and does row reduction on it.

$ python gauss_method.py
number of rows? 4
[69.48033741746909, 32.393754742132586, 91.35245787350696, 87.04557918402462]
[98.64189032145111, 28.58228108715638, 72.32273998878178, 26.310252241189257]
[85.22896214660841, 39.93894635139987, 4.061683241757219, 70.5925099861901]
[24.06322759315518, 26.699175587284373, 37.398583921673314, 87.42617087562161]
-----
[69.48033741746909, 32.393754742132586, 91.35245787350696, 87.04557918402462]
[0.0, -17.40743803545155, -57.37120602662462, -97.2691774792963]
[0.0, 0.0, -108.66513774392809, -37.31586824349682]
[0.0, 0.0, 0.0, -13.678536859817994]

Inside of the gauss_method routine, for each row prow, the routine performs $\mathrm{𝚏𝚊𝚌𝚝𝚘𝚛}\cdot {\rho }_{\mathrm{𝚙𝚛𝚘𝚠}}+{\rho }_{\mathrm{𝚛𝚘𝚠}}$ on the rows below. For each of these rows below, this involves operating on every entry in that row. That is a triply-nested loop. So this program has a running time that is something like the cube of the number of rows in the matrix. (Comment. We are glossing over many issues. For example, we may worry that the time taken by the program is dominated by the time to store and retrieve entries from memory, rather than by the row operations. However, development of a computation model is outside of our scope.)

If we add this code at the bottom,

def do_matrix(num_rows):
    gauss_method(random_matrix(num_rows, num_rows))

import timeit
for num_rows in [10,20,30,40,50,60,70,80,90,100]:
    s = "do_matrix("+str(num_rows)+")"
    t = timeit.timeit(stmt=s, setup="from __main__ import do_matrix",
                      number=100)
    print "num_rows=", num_rows, " seconds=", t  

then Python will time the program. Here is the output from a timed test run.

num_rows= 10  seconds= 0.0162539482117
num_rows= 20  seconds= 0.0808238983154
num_rows= 30  seconds= 0.248152971268
num_rows= 40  seconds= 0.555531978607
num_rows= 50  seconds= 1.05453586578
num_rows= 60  seconds= 1.77881097794
num_rows= 70  seconds= 2.75969099998
num_rows= 80  seconds= 4.10647988319
num_rows= 90  seconds= 5.81125879288
num_rows= 100  seconds= 7.86893582344  

Graphing that data gives part of the curve of a cubic.

Finding the fastest algorithm to compute the determinant is a topic of current research. So far, researchers have found algorithms that run in time between the square and cube of the number of rows.

The contrast between the times taken by the two determinant computation methods of permutation expansion and row operations makes the point that although in principle they give the same answer, in practice we want the one with the best performance.