Минимальное количество арифметических операций для вычисления определителя

Была ли проведена работа по поиску минимального числа элементарных арифметических операций, необходимых для вычисления определителя матрицы $n$ на $n$ для малых и фиксированных $n$ ? Например, $n=5$ .

cc.complexity-theory linear-algebra determinant Lembik
источник

Я спрашивал экспертов об этом, и, по-видимому, в настоящее время даже не известно, нужно ли 9 умножений для вычисления определителя матрицы 3х3.

Джеффри Шаллит

@JeffreyShallit Если

9

$9$ возможно, это уже интересно (например, меньше

n^{3}

$n^3$ ). Как насчет

n = 4

$n=4$ ?

Лембик

Нет, совсем не интересно. 9 умножений для n = 3 следует разложением по минорам. При n = 4 снова разложение по несовершеннолетним дает 40. Я не знаю, как это сделать менее чем за 40 умножений.

Джеффри Шаллит

@JeffreyShallit О, я вижу, хорошая мысль. Удивительно (по крайней мере, для меня), если нет ничего лучше наивного для любого фиксированного

n

$n$

Лембик

Если кто-то знает, возможно, они могут сказать нам.

Джеффри Шаллит

Ответы:

Известно, что число арифметических операций, необходимых для вычисления определителя матрицы равно , где $n\times n$ $n^{\omega+o(1)}$ $\omega$ - константа умножения матрицы. Смотрите, например, эту таблицу в Википедии, а также ее сноски и ссылки. Обратите внимание, что асимптотическая сложность обращения матриц также совпадает с умножением матриц в этом же смысле.

Эквивалентность довольно эффективна. В частности, вы можете рекурсивно вычислить определитель матрицы , работая с блоками используя дополнение Шура: $n\times n$ $(n/2) \times (n/2)$

D invertible ⟹ det (\begin{matrix} A & B \\ C & D \end{matrix}) = det (D) det (A - B D^{- 1} C) .

$\text{$D$ invertible}\qquad\implies\qquad\det \begin{pmatrix}A&B\\C&D\end{pmatrix} = \det(D) \det(A-BD^{-1}C).$

Таким образом, вы можете вычислить определитель путем вычисления двух определителей, инвертирования одной матрицы, умножения двух пар матриц и некоторые более простые операции. Расширяя детерминантные вызовы рекурсивно, сложность заканчивается доминированием умножения и инверсии матриц. $n\times n$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$

$n$ $n=4$ $\det(D)$ $D^{-1}$ $BD^{-1}C$ $2\times 8=16$ $\det(A-BD^{-1}C)$ $2+4+16+2+1=25$ $40$ от расширения кофактора. Использование алгоритма Штрассена сохраняет здесь два умножения, но более асимптотически.

$O(n^4)$ $n^{2+\omega/2+o(1)}$

А. Рекс
источник

Вы знаете какую-либо нижнюю границу только по числу умножений? Даже для n = 3?

Джеффри Шаллит

n \times n

$n \times n$

n^{ω + o (1)}

$n^{\omega +o(1)}$

Нижняя граница в статье В. Баура и В. Страссена "Сложность частных производных" ( dx.doi.org/10.1016/0304-3975(83)90110-X )

Владимир Лысиков