Méthodes itératives pour les systèmes indéfinis sans structure de blocs

9

Des systèmes indéfinis de matrices apparaissent par exemple dans la discrétisation des problèmes de point de selle par des éléments finis mixtes. La matrice du système peut alors être mise sous la forme

(\begin{matrix} UNE & B^{t} \\ B & C \end{matrix})

$\begin{pmatrix} A & B^t \\ B & C\end{pmatrix}$

où est négatif (semi) défini, est positif (semi) défini et est arbitraire. Bien sûr, selon la convention, vous pouvez utiliser des conditions de définition, mais c'est à peu près la structure de ces matrices. $A$ $C$ $B$

Pour ces méthodes, la méthode d'Uzawa peut être employée, ce qui n'est en fait qu'une "astuce" pour transformer le système en un système semi-défini équivalent qui peut être résolu par Conjugate Gradient, Gradient Descent et similaires.

Je suis confronté à un système indéfini qui n'a pas une telle structure de blocs. Les méthodes de type Uzawa ne s'appliquent pas dans ce cas. Je connais la méthode Minimal Residual (MINRES) qui a été introduite par Paige & Saunders, qui n'est qu'une récursivité à trois termes et semble facile à mettre en œuvre.

Question: MINRES est-il généralement un bon choix, par exemple, pour le prototypage? Est-ce d'une pertinence pratique? Le préconditionnement n'est pas un problème central pour le moment.

linear-algebra iterative-method shuhalo
la source

Pouvez-vous nous en dire un peu plus sur ce qui rend vos matrices spéciales? Par exemple, de quel type de problème s'agit-il? Existe-t-il un autre type de structure? Etc. Etc.

Bill Barth

Je l'ai laissé intentionnellement vide, pour obtenir la réponse la plus générale (franchement, cela suppose implicitement qu'il existe une réponse générale satisfaisante). Mais l'exemple avec l'équation de Helmholtz ci-dessous est à peu près ce que j'avais en tête.

shuhalo

7

Si vous n'êtes pas préoccupé par le préconditionnement, alors MINRES est le choix standard. Cependant, sachez que MINRES nécessite un préconditionneur défini symétrique positif.

Si vous êtes préoccupé par le préconditionnement, il est important de considérer les différences structurelles entre la plupart des problèmes de point de selle et les problèmes généraux indéfinis. La plupart des problèmes de point de selle surviennent lors de la résolution de problèmes elliptiques avec des contraintes imposées par les multiplicateurs de Lagrange. L'incompressibilité et les contraintes de contact sont des exemples courants. Pour de tels problèmes, l'opérateur est coercitif sur le sous-espace dans lequel la contrainte est satisfaite, avec les fonctions de Green qui se désintègrent rapidement. De tels problèmes peuvent être résolus efficacement en utilisant des préconditionneurs de blocs (Uzawa préconditionné fait partie de cette famille), multigrilles avec des lisseurs compatibles (par exemple Vanka ou basés sur la décomposition en blocs), ou décomposition de domaine à plusieurs niveaux avec des problèmes locaux et grossiers appropriés.

L'exemple prototypique d'un problème indéfini qui n'est pas un problème de point de selle est l'équation de Helmholtz

- \nabla \cdot (une \nabla u) - k^{2} u = F

$-\nabla\cdot \big( a \nabla u \big) - k^2 u = f$

$a(x)$ $k$

Jed Brown
la source

1

Pour être juste, alors que les préconditionneurs de balayage sont certainement techniques à mettre en œuvre efficacement en parallèle, l'idée n'est pas spécifique à Helmholtz; l'exigence principale est une condition aux limites absorbantes (par exemple, des couches parfaitement adaptées).

Jack Poulson

3

Une question connexe qui pourrait être intéressante est: Quelles directives dois-je suivre lors du choix d'un solveur de système linéaire clairsemé? , bien que dans ce cas, vous ne serez intéressé que par les méthodes itératives. Ma compréhension des méthodes itératives est que la convergence pour une méthode donnée dépend fortement du spectre de votre matrice. Même si vous ne pouvez pas utiliser la méthode d'Uzawa, vous pouvez toujours essayer GMRES, le gradient stabilisé biconjugué, MINRES, la méthode résiduelle quasi-minimale et d'autres méthodes itératives qui s'appliquent aux matrices indéfinies.

Si le codage des différentes méthodes est un problème, vous pouvez appeler des solveurs dans votre algorithme en utilisant une bibliothèque comme PETSc , qui implémente une variété de solveurs linéaires itératifs.

Geoff Oxberry
la source

1

MINRES est le meilleur choix pour ce type de problème.

Kees Vuik
la source

1

Veuillez ne pas lier votre site personnel de cette façon. N'hésitez pas à lier des ressources spécifiques pertinentes pour votre réponse, mais ne liez pas votre site personnel de cette façon. Je l'ai supprimé de cette réponse. Ces liens appartiennent à votre profil d'utilisateur.

Jed Brown

Pourriez-vous expliquer pourquoi MINRES est le meilleur choix pour ce type de problème? Ajouter plus de détails aidera à rendre votre réponse plus utile à la communauté et vous aidera à obtenir plus de votes.

Geoff Oxberry

Méthodes itératives pour les systèmes indéfinis sans structure de blocs

Réponses: