Le nombre minimum d'opérations arithmétiques pour calculer le déterminant

Y at - il eu des travaux visant à trouver le nombre minimum d'opérations arithmétiques élémentaires nécessaires pour calculer le déterminant d'un par matrice pour les petites et fixe ? Par exemple, . $n$ $n$ $n$ $n=5$

cc.complexity-theory linear-algebra determinant Lembik
la source

J'ai interrogé des experts à ce sujet, et apparemment, on ne sait même pas actuellement si 9 multiplications sont nécessaires ou non pour calculer le déterminant d'une matrice 3x3.

Jeffrey Shallit

@JeffreyShallit Si

9

$9$ est possible c'est déjà intéressant (car il est inférieur à

n^{3}

$n^3$ par exemple). Que diriez-vous de

n = 4

$n=4$ ?

Lembik

Non, pas du tout intéressant. 9 multiplications pour n = 3 suivies d'une expansion par des mineurs. Pour n = 4 encore, l'expansion par les mineurs donne 40. Je ne sais pas comment le faire en moins de 40 multiplications.

Jeffrey Shallit

@JeffreyShallit Oh je vois, bon point. C'est incroyable (du moins pour moi) si rien de mieux que naïf n'est connu pour un

fixe .

n

$n$

Lembik

Si quelqu'un le sait, il pourra peut-être nous le dire.

Jeffrey Shallit

On sait que le nombre d'opérations arithmétiques nécessaires pour calculer le déterminant d'une matrice est , où est la constante de multiplication de la matrice. Voir par exemple ce tableau sur Wikipédia, ainsi que ses notes de bas de page et références. Notez que la complexité asymptotique de l'inversion matricielle est également la même que la multiplication matricielle dans ce même sens. $n\times n$ $n^{\omega+o(1)}$ $\omega$

L'équivalence est assez efficace. En particulier, vous pouvez calculer récursivement le déterminant d'une matrice en travaillant sur des blocs utilisant le complément 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).$

Ainsi, vous pouvez calculer un déterminant en calculant deux déterminants, en inversant une matrice, en multipliant deux paires de matrices, et quelques opérations plus simples. En élargissant récursivement les appels déterminants, la complexité finit par être dominée par la multiplication et l'inversion matricielles. $n\times n$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$

Cela fonctionne bien même pour les petits $n$ et même sans utiliser d'algorithmes de multiplication de matrice sous-cubique. (Bien sûr, cela finit par être plus ou moins équivalent à l'élimination gaussienne.) Par exemple, pour , nous pouvons calculer avec deux multiplications, avec quatre divisions, avec multiplications, $n=4$ $\det(D)$ $D^{-1}$ $BD^{-1}C$ $2\times 8=16$ $\det(A-BD^{-1}C)$ avec deux multiplications, et la réponse finale avec une multiplication. Le nombre total est de multiplications plus divisions, ce qui est inférieur aux de l'expansion des cofacteurs. L'utilisation de l'algorithme de Strassen enregistre ici deux multiplications, mais de manière plus asymptotique. $2+4+16+2+1=25$ $40$

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

A. Rex
la source

Connaissez-vous une limite inférieure sur le seul nombre de multiplications? Même pour n = 3?

Jeffrey Shallit

Votre formulation "le nombre d'opérations arithmétiques nécessaires pour calculer le déterminant d'une matrice

est

" suggère qu'une borne inférieure est connue. Mais je n'ai vu cela dans aucun des ouvrages cités. Suis-je en train de manquer quelque chose?

n \times n

$n \times n$

n^{ω + o (1)}

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

Jeffrey Shallit du

La borne inférieure est dans l'article de W.Baur et V.Strassen "La complexité des dérivées partielles" ( dx.doi.org/10.1016/0304-3975(83)90110-X )

Vladimir Lysikov

Le nombre minimum d'opérations arithmétiques pour calculer le déterminant

Réponses: