Inverser une matrice de bande

J'ai une matrice de bande - clairsemée, carrée, symétrique$N \times N$ matrice dont la structure ressemble à ceci:

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?

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 $\Omega\left(n^2\right)$. Je suppose donc que vous voulez simplement résoudre un système linéaire$A x = b$.

En utilisant l'algorithme de cet article , une matrice générale à bande limitée$A$ de taille $n \times n$ avec bande passante $k$ peut être décomposé en triangulaire $k$matrices de bande passante $L$ et $U$ dans $O \left( k^2 n \right)$temps. De là,$L U x = b$ peut être résolu rapidement en $O(k n)$temps. Donc, dans l'ensemble, le temps d'exécution sera$O\left(k^2 n\right)$. À titre de suivi, si$k$ est constant, cela signifie que le système peut être résolu en temps linéaire (très utile).