L'algorithme de Thomas est-il le moyen le plus rapide de résoudre un système linéaire tridiagonal clairsemé à dominante diagonale symétrique

Je me demande si l'algorithme de Thomas est le moyen le plus rapide (de manière probable?) De résoudre un système tridiagonal clairsemé à dominante diagonale symétrique en termes de complexité algorithmique (ne pas chercher de packages d'implémentation comme LAPACK, etc.). Je sais que l'algorithme de Thomas et le multigrille sont tous deux de complexité , mais peut-être que le facteur constant pour le multigrille est moindre? Il ne me semble pas que le multigrille pourrait être plus rapide mais je ne suis pas positif. $O(n)$

Remarque: je considère le cas où les matrices sont très grandes. Des méthodes directes ou itératives sont acceptables.

linear-solver sparse-matrix complexity multigrid James
la source

Réponses:

Je pense que la comparaison d'une méthode itérative (multigrille) à une méthode directe / exacte (Thomas) en termes de nombre d'opérations exact n'est pas vraiment significative. IIRC, le nombre d'opérations Thomas est de pour tout système tridiagonal. La seule fois où je peux imaginer battre multigrille, c'est pour un cas trivial d'avoir une solution linéaire, et même alors, le coût de l'évaluation du résidu à chaque niveau serait comparable au coût de Thomas. $8N$

L' utilité du multigrille réside dans le fait qu'il est général pour les matrices clairsemées et non limité aux systèmes tridiagonaux. $O(N)$

Aurelius
la source

Merci. Je me rends compte que les méthodes itératives ne sont pas exactes. J'aurais dû spécifier une très petite tolérance (disons 10 ^ -15) et la traiter comme étant "exacte" à des fins de comparaison.

James

@ user2697246 eh bien, vous avez posé une question sur "prouvablement" le plus rapide. Le taux de convergence exact pour les multigrilles (ou tout schéma itératif) dépendra toujours de la solution elle-même et de la supposition de départ - une solution linéaire sera effectivement résolue exactement en une seule étape, tandis que quelque chose de plus oscillatoire nécessitera plus d'opérations. Thomas a un nombre d'opérations exact et fixe pour tous les cas. En pratique, vous n'allez jamais battre Thomas pour avoir résolu (en série) un système tridiagonal pour un cas non trivial.

Aurelius

@Aurelius L'algorithme Thomas peut-il être parallélisé? Sinon, c'est l'un des principaux avantages du multigrid!

Nick Alger

@NickAlger Non, l'algorithme de Thomas est strictement série, et oui la parallélisation est un gros avantage pour les multigrilles (bien que pour le cas spécifique d'un système tridiagonal je soupçonne que la latence de la communication vous tuerait.) Il existe une technique spécifique aux systèmes tridiagonaux appelée cyclique parallèle réduction (PCR) qui est

, parallélisable par

, que j'ai utilisé avec succès sur les GPU.

O (N l o g N)

$O(N log N)$

N

$N$

Aurelius

Une correction, l'algorithme Thomas nécessite 8N opérations, pas 9N. Aussi, que voulez-vous dire par "multigrille ... ayant une solution linéaire"? Tous les systèmes considérés ici sont linéaires.

Doug Lipinski

La réponse courte est que l'algorithme de Thomas sera plus rapide que n'importe quel schéma itératif pour presque tous les cas. L'exception serait peut-être d'appliquer une seule itération d'un schéma itératif très simple tel que Gauss-Seidel, mais il est peu probable que cela donne une solution acceptable. En outre, cela ignore les problèmes de traitement parallèle.

La multigrille est un choix particulièrement mauvais dans le cas d'une matrice tri-diagonale car bien que multigrille soit , la constante est assez grande. En fait, le multigrille n'a même pas d'avantage sur Gauss-Seidel jusqu'à ce que les matrices deviennent assez grandes. Cela est dû au besoin d'opérations de projection, de prolongation et de relaxation pour chaque niveau multigrille, chacune nécessitant des opérations où n est le nombre d'inconnues à ce niveau multigrille. $\mathcal O(n)$ $\mathcal O(n)$

Enfin, cette question est mieux abordée via le comptage des opérations. Pour l'algorithme Thomas, un total de multiplications et additions sont nécessaires pour la solution. Les schémas itératifs nécessitent au moins autant d'opérations que la multiplication matrice-vecteur et étant donné une matrice tri-diagonale, chaque multiplication matrice-vecteur nécessite multiplications et additions. Par conséquent, même deux applications de n'importe quel schéma itératif (même le plus simple) seront plus coûteuses que l'algorithme de Thomas. $5N$ $3N$ $3N-2$ $2N-2$

Doug Lipinski
la source

"Multigrid est un choix particulièrement mauvais dans le cas d'une matrice tri-diagonale car bien que multigrid soit O (n), la constante est assez grande." Je pense que cela aussi, mais googler a soulevé une ligne dans le livre Multigrid de Trottenburg réclamant une constante de 0,1-0,2, déclaré sans preuve. Je ne pense pas que je crois cela.

Aurelius

@Aurelius Intéressant. C'est clairement impossible dans le cas général car il y a 3 entrées N dans une matrice tridiagonale. Si le coût est de ~ 0,1 * N, cela signifie que vous ne travaillez même jamais sur la plupart des entrées.

Doug Lipinski

Oui, nous sommes sur la même longueur d'onde; évaluer simplement un gabarit à 3 points nécessite 3N opérations. Je ne faisais qu'effleurer, alors j'ai peut-être mal interprété la déclaration, mais vous pouvez le voir par vous-même dans l'extrait de Google Books.

Aurelius

La citation complète (p. 21) est «L'efficacité au sens pratique signifie que les constantes de proportionnalité dans cette déclaration O (N) sont petites ou modérées. C'est en effet le cas pour les multigrilles: si elles sont bien conçues, les facteurs de convergence indépendants de h peuvent être très petit (dans la plage de 0,1 à 0,2 ou même moins) et le nombre d'opérations par inconnu par étape d'itération est également faible. " Le 0.1-0.2 se réfère à la réduction résiduelle pour chaque cycle de multigrille. La constante sur O (N) serait de l'ordre de 1,5 à 2,0 fois la matrice multipliée par cycle (avec un total d'une douzaine ou deux cycles).

Godric Seer

Ah, merci @GodricSeer, cela a plus de sens.

Aurelius

Les boucles multigrilles, même sur un seul cœur, sont vectorisables par l'optimiseur. Ainsi, bien que le nombre d'opérations puisse aider, nous ne devons pas oublier que même dans le monde série, les processeurs ont un parallélisme vectoriel, et donc le délai de résolution peut ne pas être exactement ce que nous prédisons à partir de l'analyse des coûts.

Hasbestein
la source