El número mínimo de operaciones aritméticas para calcular el determinante

¿Ha habido algún trabajo en encontrar el mínimo número de operaciones aritméticas elementales necesarios para calcular el determinante de una $n$ por $n$ matriz para la pequeña y fija $n$ ? Por ejemplo, $n=5$ .

cc.complexity-theory linear-algebra determinant Lembik
fuente

He preguntado a los expertos sobre esto, y aparentemente ni siquiera se sabe actualmente si se necesitan 9 multiplicaciones para calcular el determinante de una matriz 3x3.

Jeffrey Shallit

@JeffreyShallit Si

es posible, eso ya es interesante (ya que es menor que

por ejemplo). ¿Qué tal

9

$9$

n^{3}

$n^3$

n = 4

$n=4$

Lembik

No, no es interesante en absoluto. 9 multiplicaciones para n = 3 sigue por expansión por menores. Para n = 4 nuevamente, la expansión por menores da 40. No sé cómo hacerlo en menos de 40 multiplicaciones.

Jeffrey Shallit

@JeffreyShallit Oh, ya veo, buen punto. Es sorprendente (al menos para mí) si no se conoce nada mejor que ingenuo para cualquier

fijo .

n

$n$

Lembik

Si alguien lo sabe, quizás nos puedan decir.

Jeffrey Shallit

Se sabe que el número de operaciones aritméticas necesarias para calcular el determinante de una matriz es , donde es la constante de multiplicación de la matriz. Vea, por ejemplo, esta tabla en Wikipedia, así como sus notas al pie y referencias. Tenga en cuenta que la complejidad asintótica de la inversión de la matriz también es la misma que la multiplicación de la matriz en este mismo sentido. $n\times n$ $n^{\omega+o(1)}$ $\omega$

La equivalencia es bastante efectiva. En particular, puede calcular recursivamente el determinante de una matriz trabajando en bloques utilizando el complemento de Schur: $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).$

Por lo tanto, puede calcular un determinante calculando dos determinantes, invirtiendo una matriz , multiplicando dos pares de matrices, y algunas operaciones más simples. Al expandir las llamadas determinantes de forma recursiva, la complejidad termina siendo dominada por la multiplicación e inversión de la matriz. $n\times n$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$

Esto funciona bien incluso para pequeños e incluso sin usar algoritmos de multiplicación de matriz subcúbica. (Por supuesto, termina siendo más o menos equivalente a la eliminación gaussiana). Por ejemplo, para , podemos calcular con dos multiplicaciones, con cuatro divisiones, con multiplicaciones, $n$ $n=4$ $\det(D)$ $D^{-1}$ $BD^{-1}C$ $2\times 8=16$ $\det(A-BD^{-1}C)$ con dos multiplicaciones, y la respuesta final con una multiplicación. El número total es multiplicaciones más divisiones, que es menor que los de la expansión del cofactor. Usar el algoritmo de Strassen ahorra dos multiplicaciones aquí, pero más asintóticamente. $2+4+16+2+1=25$ $40$

Puede notar que esta expansión usa crucialmente la división. Si desea evitar la división, puede hacerlo en operaciones trabajando con secuencias de Clow y programación dinámica . También se sabe cómo lograr multiplicaciones y sin divisiones. $O(n^4)$ $n^{2+\omega/2+o(1)}$

A. Rex
fuente

¿Conoces algún límite inferior con solo el número de multiplicaciones? ¿Incluso para n = 3?

Jeffrey Shallit el

Su frase "el número de operaciones aritméticas necesarias para calcular el determinante de una matriz

" sugiere que se conoce un límite inferior. Pero no vi esto en ninguno de los trabajos citados. ¿Me estoy perdiendo de algo?

n \times n

$n \times n$

n^{ω + o (1)}

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

Jeffrey Shallit

El límite inferior está en el artículo de W.Baur y V.Strassen "La complejidad de los derivados parciales" ( dx.doi.org/10.1016/0304-3975(83)90110-X )

Vladimir Lysikov

El número mínimo de operaciones aritméticas para calcular el determinante

Respuestas: