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

14

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 = 5nnnn=5

Lembik
la source
4
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 est possible c'est déjà intéressant (car il est inférieur à n3 par exemple). Que diriez-vous de n=4 ?
Lembik
3
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
Lembik
Si quelqu'un le sait, il pourra peut-être nous le dire.
Jeffrey Shallit

Réponses:

9

On sait que le nombre d'opérations arithmétiques nécessaires pour calculer le déterminant d'une matrice est n ω + o ( 1 ) , 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×nnω+o(1)ω

L'équivalence est assez efficace. En particulier, vous pouvez calculer récursivement le déterminant d'une matrice en travaillant sur des blocs ( n / 2 ) × ( n / 2 ) en utilisant le complément de Schur:n×n(n/2)×(n/2)

D invertibledet(ABCD)=det(D)det(ABD1C).

Ainsi, vous pouvez calculer un déterminant en calculant deux ( n / 2 ) × ( n / 2 ) déterminants, en inversant une ( n / 2 ) × ( n / 2 ) matrice, en multipliant deux paires de ( n / 2 ) × ( n / 2 ) 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×n(n/2)×(n/2)(n/2)×(n/2)(n/2)×(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 det ( D ) avec deux multiplications, D - 1 avec quatre divisions, B D - 1 C avec 2 × 8 = 16 multiplications, det ( A - B D - 1 C )n=4det(D)D1BD1C2×8=16det(ABD1C)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 40 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=2540

O(n4)n2+ω/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 n ω + o ( 1 ) " 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×nnω+o(1)
Jeffrey Shallit du
2
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