Quelles directives dois-je suivre lors du choix d'un solveur de système linéaire creuse?

49

Les systèmes linéaires clairsemés apparaissent de plus en plus fréquemment dans les applications. On a beaucoup de routines à choisir pour résoudre ces systèmes. Au niveau le plus élevé, il existe un fossé entre les méthodes directes (par exemple, l’élimination gaussienne ou la décomposition de Cholesky, avec des algorithmes de classement spéciaux et les méthodes multifrontales) et les méthodes itératives (par exemple, GMRES, à (bi) conjugué).

Comment détermine-t-on s'il faut utiliser une méthode directe ou itérative? Après avoir fait ce choix, comment choisit-on un algorithme particulier? Je connais déjà l'exploitation de la symétrie (par exemple, utiliser un gradient conjugué pour un système défini positif symétrique clairsemé), mais y a-t-il d'autres considérations de ce type à prendre en compte lors du choix d'une méthode?

JM
la source

Réponses:

33

L'important lors du choix de solveurs itératifs est le spectre de l'opérateur, voir ce document . Cependant, il y a tellement de résultats négatifs, consultez ce document dans lequel aucun solutionneur itératif ne gagne pour tous les problèmes et ce document dans lequel ils prouvent qu'ils peuvent obtenir une courbe de convergence pour GMRES quel que soit leur spectre. Il semble donc impossible de prédire le comportement des solveurs itératifs, sauf dans quelques cas isolés. Par conséquent, votre meilleure option est de tous les essayer, en utilisant un système tel que PETSc , qui a également des solveurs directs.

Matt Knepley
la source
2
"Jetez tout ce que vous pouvez à elle" était à peu près le conseil auquel j'étais habitué. :) Le troisième article auquel vous créez un lien est quelque chose que je n’ai jamais vu auparavant; Merci pour ça!
JM
2
Matt a une excellente réponse, mais vous devez la prendre dans le contexte de la communauté d'où il vient (calcul scientifique à grande échelle). Vous constaterez que pour les petits problèmes (disons moins de cent mille inconnus), les solveurs directs surpassent considérablement les méthodes itératives si le problème n'est pas fortement elliptique. Je n'ai vu aucun bon article général dans la littérature qui pourrait vous orienter vers une stratégie de départ initiale, ce qui est un peu gênant pour moi.
Aron Ahmadia
5
L'estimation d'Aron est bonne mais dépend beaucoup du remplissage, car les méthodes directes éparses épuisent généralement la mémoire avant de s'épuiser en patience.
Matt Knepley
18

Le choix entre les méthodes directes et itératives dépend des objectifs et du problème à résoudre.

Pour les méthodes directes, on peut noter:

  • La matrice de coefficients du système linéaire change au cours du calcul et peut, pour les systèmes épars, éponger les besoins en mémoire et augmenter l'effort de travail dû au remplissage.
  • Doit compléter pour donner des résultats utiles
  • La factorisation peut être réutilisée dans les étapes suivantes si plusieurs côtés droits sont présents
  • Peut être utilisé pour résoudre des systèmes linéaires uniquement.
  • Échoue rarement.

Pour les méthodes itératives, on peut noter:

  • L'objectif est de donner un résultat partiel seulement après un petit nombre d'itérations.
  • L’effort de solution devrait être inférieur aux méthodes directes pour le même problème.
  • Économique en ce qui concerne le stockage (pas de remplissage)
  • Souvent facile à programmer.
  • Une solution approchée connue peut être exploitée.
  • Parfois, ils sont rapides et parfois ils ne le sont pas (parfois même divergents).
  • Pour les problèmes complexes, les méthodes itératives sont considérablement moins robustes que les méthodes directes.

Lignes directrices pour savoir quand utiliser des méthodes directes ou itératives?

  • Méthodes itératives lorsque la matrice de coefficients est rare et que les méthodes directes ne peuvent pas exploiter efficacement la parcimonie (évitez de créer un remplissage).
  • Méthodes directes pour plusieurs côtés droits.
  • Les méthodes itératives peuvent être plus efficaces si la précision est moins préoccupante
  • Méthodes itératives pour les systèmes d'équations non linéaires.
Allan P. Engsig-Karup
la source
8
O(n)O(n)O(n2)O(1)
8

Je suis tout à fait d'accord avec les réponses déjà données. Je voulais ajouter que toutes les méthodes itératives nécessitent une sorte de conjecture initiale. La qualité de cette hypothèse initiale peut souvent affecter le taux de convergence de la méthode choisie. Des méthodes telles que Jacobi, Gauss Seidel et Successive Over Relaxation fonctionnent toutes pour "lisser" de manière itérative autant d’erreurs que possible à chaque étape ( voir cet article pour plus de détails).). Les premières étapes réduisent assez rapidement l’erreur de haute fréquence, mais l’erreur de basse fréquence nécessite beaucoup plus d’itérations pour être atténuée. C'est ce qui ralentit la convergence pour ces méthodes. Dans de tels cas, nous pouvons accélérer la convergence en résolvant les erreurs de basse fréquence (par exemple, résoudre le même problème sur un maillage plus grossier), puis en résolvant l'erreur de fréquence plus élevée (par exemple, sur un maillage plus fin). Si nous appliquons ce concept récursivement par division et conquête, nous obtenons ce qu'on appelle une méthode multi-grille. Même si le système linéaire n'est pas symétrique, il existe d'autres variantes de la méthode multi-grille pour tout système matriciel maigre non singulier (par exemple, la méthode multi-grille algébrique) qui peuvent accélérer la convergence du solveur. Leur évolutivité sur des systèmes parallèles fait cependant l’objet de nombreuses recherches..

Paul
la source
5
Cette réponse semble donner l’impression que l’efficacité du multigrid provient de la découverte d’une bonne hypothèse initiale. En réalité, la supposition initiale est une préoccupation mineure pour les problèmes linéaires et en réalité une préoccupation uniquement pour Full Multigrid. Multigrid fonctionne en raison de la séparation spectrale. Notez que faire en sorte que le multigrid fonctionne bien pour les problèmes difficiles est un défi majeur. Multigrid fonctionne assez bien en parallèle, il a été l’ingrédient clé de plusieurs prix Gordon Bell et quelques packages open source fonctionnent avec une efficacité élevée sur les plus grandes machines d’aujourd’hui. Pour les implémentations GPU, regardez la bibliothèque CUSP.
Jed Brown
La plupart du temps, une supposition initiale aléatoire est suffisante. Lors de l'extraction de valeurs propres à l'aide de l'algorithme Lanczos, un vecteur de démarrage / redémarrage aléatoire aide. Les redémarrages se produisent parfois dans l'algorithme Lanczos.
AnilJ
3

Il vous manque un élément d’information important dans votre question: d’où vient la matrice? La structure du problème que vous tentiez de résoudre a un grand potentiel pour suggérer une méthode de solution.

Si votre matrice est issue d’une équation différentielle partielle à coefficients lisses, il sera difficile de battre une méthode géométrique multigrille, en particulier en trois dimensions. Si votre problème est moins régulier, le multigrille algébrique est une bonne méthode. Les deux sont généralement associés aux méthodes de Krylov-space. D'autres solveurs efficaces peuvent être dérivés de méthodes multipolaires rapides ou de transformées de Fourier rapides.

Guido Kanschat
la source