Inverser une matrice de bande

9

J'ai une matrice de bande - clairsemée, carrée, symétriqueN×N matrice dont la structure ressemble à ceci:

matrice de bande

Ici, la zone sous les bandes bleues correspond aux éléments non nuls; tout le reste est nul

Existe-t-il un algorithme pour inverser ce type de matrice qui est simple mais plus efficace que l'élimination gaussienne et la décomposition LU?

rnels12
la source
3
Ces matrices sont appelées matrices de bandes (et pour autant que je sache, elles étaient la motivation d'origine pour trouver la bande passante d'un graphique ), et ce document pourrait peut-être être un point de départ utile.
G. Bach
@ G.Bach Merci, je vais jeter un œil au journal. Pourriez-vous me dire la complexité de calcul de la méthode?
rnels12
Désolé, je ne sais pas, googlé pendant une minute ou deux, mais à partir du résumé, cela semblait être un début prometteur.
G. Bach
2
Voulez-vous l'inverser ou voulez-vous résoudre le système linéaire? La réponse est probablement la dernière, car l'inverse d'une matrice de bande est généralement dense. Question supplémentaire: Y a-t-il plus de structure à exploiter?
Pseudonyme
2
D'ACCORD. La raison pour laquelle je pose la question est que dans la plupart des cas, les gens qui pensent vouloir inverser une matrice ne le font probablement pas. De toute façon, c'est une bonne question!
Pseudonyme

Réponses:

5

Puisqu'aucun des commentaires n'a donné de réponse concrète, je l'écrirai explicitement ici au cas où quelqu'un en aurait besoin (comme je l'ai fait).

Premièrement, malheureusement, l'inverse d'une matrice à bande limitée est une matrice complète (non à bande limitée) en général, donc il suffit de remplir les entrées de la matrice inverse Ω(n2). Je suppose donc que vous voulez simplement résoudre un système linéaireUNEX=b.

En utilisant l'algorithme de cet article , une matrice générale à bande limitéeUNE de taille n×n avec bande passante k peut être décomposé en triangulaire kmatrices de bande passante L et U dans O(k2n)temps. De là,LUX=b peut être résolu rapidement en O(kn)temps. Donc, dans l'ensemble, le temps d'exécution seraO(k2n). À titre de suivi, sik est constant, cela signifie que le système peut être résolu en temps linéaire (très utile).

chausies
la source