Quel est l'algorithme le plus rapide pour calculer la matrice inverse et son déterminant pour les matrices symétriques définies positives?

10

Étant donné une matrice symétrique définie positive, quel est l'algorithme le plus rapide pour calculer la matrice inverse et son déterminant? Pour les problèmes qui m'intéressent, la dimension de la matrice est de 30 ou moins.

  1. Une précision et une vitesse élevées sont vraiment nécessaires. (des millions de matrices sont réalisées)
  2. Le déterminant est nécessaire: dans chaque calcul, un seul élément de la matrice ivers est requis. Merci!
Ordres
la source
Devez-vous inverser des millions de telles matrices? Sinon, la vitesse ne devrait pas être un problème.
Wolfgang Bangerth
J'ai édité votre titre et votre question pour plus de clarté. Si j'ai fait des erreurs, faites-le moi savoir.
Geoff Oxberry
@Wolfgang Bangerth Oui, la vitesse doit être prise en compte.
Commandes du
1
Savez-vous quel élément de la matrice inverse est nécessaire? Ou peut-il s'agir d'une entrée aléatoire?
Memming
2
@Ordres Vos commentaires et modifications semblent contradictoires: avez-vous besoin d' un élément de l'inverse, ou de tous ?
Federico Poloni

Réponses:

12

Pour les problèmes qui m'intéressent, la dimension de la matrice est de 30 ou moins.

Comme le note WolfgangBangerth, à moins que vous n'ayez un grand nombre de ces matrices (millions, milliards), les performances de l'inversion de matrice ne sont généralement pas un problème.

Étant donné une matrice symétrique définie positive, quel est l'algorithme le plus rapide pour calculer la matrice inverse et son déterminant?

Si la vitesse est un problème, vous devez répondre aux questions suivantes:

  • Avez-vous vraiment besoin de tout l'inverse? (De nombreuses applications n'ont pas besoin de former un inverse explicite.)
  • Avez-vous vraiment besoin du déterminant? (Les déterminants sont rares, mais certainement pas inconnus en science informatique.)
  • Avez-vous besoin d'une haute précision? (Les algorithmes de faible précision ont tendance à être plus rapides.)
  • Une approximation probabiliste suffirait-elle? (Les algorithmes probabilistes ont tendance à être plus rapides.)

A=LLTdet(A)=i=1nlii2det(A1)=i=1nlii2

En supposant que est par , la décomposition de Cholesky peut être calculée en environ flops, ce qui représente environ la moitié du coût d'une décomposition LU. Cependant, un tel algorithme ne serait pas considéré comme "rapide". Une décomposition LU aléatoireAnnn3/3pourrait être un algorithme plus rapide à considérer si (1) vous devez vraiment factoriser un grand nombre de matrices, (2) la factorisation est vraiment l'étape limitante dans votre application, et (3) toute erreur encourue lors de l'utilisation d'un algorithme randomisé est acceptable. Vos matrices sont probablement trop petites pour que les algorithmes clairsemés en valent la peine, de sorte que les seules autres opportunités pour des algorithmes plus rapides nécessiteraient une structure de matrice supplémentaire (par exemple, groupée), ou exploiter la structure du problème (par exemple, vous pouvez peut-être restructurer intelligemment votre algorithme afin que vous ne plus besoin de calculer une matrice inverse ou son déterminant). Les algorithmes de déterminants efficaces représentent à peu près le coût de résolution d'un système linéaire, à un facteur constant près, de sorte que les mêmes arguments utilisés pour les systèmes linéaires s'appliquent également au calcul des déterminants.

Geoff Oxberry
la source
Juste une brève note: si , pour calculer un seul élément on doit calculer que la ème colonne . Une fois la factorisation de Cholesky calculée, cela se fait par substitution avant et arrière par rapport à un vecteur rhs de tous les zéros et avec un seul dans la ligne . Étant donné que le calcul peut être interrompu dès que a été calculé, le meilleur cas est pour pire cas pour où l'on doit calculer en arrière complet et substitutions à terme. B=A1bijjBjbijbnn=lnn2b11
Stefano M
@StefanoM Encore mieux, vous pouvez permuter votre matrice avant le début du calcul afin d'être toujours dans le meilleur des cas.
Federico Poloni