How to calculate the determinant of the matrix more efficiently?

The code below counts the determinant of the 20x20 matrix by the minor method and records the time it took to calculate it. But it takes a very long time to count such a large matrix, several hours.

How can this be optimized?

import time, random
from random import randint

Ic = [0 for i in range(10)]

def minor(array):
    return array[0][0] * array[1][1] - array[1][0] * array[0][1]

def division(array):
    if len(array[0]) > 2:
        result = 0
        for i in range(len(array[0])):
            new_arr = []
            for j in range(len(array[0])):
                if j != i:
                    new_arr.append([array[j][k] for k in range(1, len(array[0]))])
            result += division(new_arr) * array[i][0] * (-1 + 2 * ((i + 1) % 2))
        return result
    else:
        return minor(array)

N = 20
result = 0
print(f"\nN:\t{N}\n")
timer = time.time()
matrix = [[randint(0, 9) for row in range(N)] for row in range(N)]
print(f"result:\t{division(matrix)}")
for i in range(N):
    print(matrix[i])
print(f"Time:\t{time.time() - timer}")
Author: 0xdb, 2020-10-21
Source

2 answers

How can this be optimized?

Use the numpy module:

In [32]: import numpy as np   #  pip install numpy

In [33]: a = np.random.rand(20, 20)

In [34]: res = np.linalg.det(a)

In [35]: res
Out[35]: 0.09252260373277807

Working time for a 20x20 matrix:

In [36]: %timeit np.linalg.det(a)
27.6 µs ± 37 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
 7
Author: MaxU, 2020-10-21 17:58:01

Calculating the determinant in terms of minors has factorial complexity and is unsuitable for n>10.

Instead, you should implement the LU decomposition of the matrix (cubic complexity) and then calculate the determinant as the product of the diagonal elements of the L and U matrices.

 3
Author: MBo, 2020-10-21 17:55:31