J'essaie de trouver la meilleure façon de résoudre une matrice pentadiagonale. Y a-t-il quelque chose de plus rapide que l'élimination gaussienne?Quel est le meilleur algorithme pour résoudre une matrice bande-diagonale?
Répondre
Vous devez faire une décomposition LU ou Cholesky de la matrice, selon que votre matrice est hermitienne définie positive ou non, puis effectuez une substitution arrière avec les facteurs. Ceci est essentiellement l'élimination gaussienne, mais tend à avoir de meilleures propriétés numériques. Je recommande d'utiliser LAPACK car ces implémentations ont tendance à être les plus rapides et les plus robustes. Regardez les routines _GBSV, où le blanc est l'un de s, d, c, z, selon votre type de numéro.
Modifier: Dans le cas où vous demandez s'il existe un algorithme plus rapide que la méthode factor/solve (élimination gaussienne), non, il n'y en a pas. Une routine de factorisation spécialisée pour une matrice en bandes prend environ 4n * k^2 opérations (k est la bande passante), tandis que la substitution vers l'arrière prend environ 6 * n * k opérations. Ainsi, pour une bande passante fixe, vous ne pouvez pas faire mieux que le temps linéaire en n.