Как эффективней вычислить определитель матрицы?

Question

Код ниже считает определитель матрицы 20х20 методом миноров и записывает время, которое ему понадобилось для расчета. Но такую большую матрицу он считает очень долго, несколько часов.

Как это можно оптимизировать?

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}")

Answer 1

Как это можно оптимизировать?

воспользоваться модулем numpy:

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

время работы для матрицы 20x20:

In [36]: %timeit np.linalg.det(a)
27.6 µs ± 37 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Answer 2

Вычисление определителя через миноры имеет факториальную сложность и непригодно для n>10.

Вместо этого стоит реализовать LU разложение матрицы (кубическая сложность) и затем вычислить определитель как произведение диагональных элементов L и U матриц.

БЛОГ НА HUSL

Как эффективней вычислить определитель матрицы?

Ответы (2 шт):