Dans une méthode comme le gmres ou le bicgstab, il pourrait être intéressant d'utiliser une autre méthode krylov comme préconditionneur. Après tout, ils sont faciles à mettre en œuvre sans matrice et dans un environnement parallèle. Par exemple, on peut utiliser quelques (disons ~ 5) itérations de bigcstab non conditionné comme précontionneur de gmres, ou toute autre combinaison de méthodes de krylov. Je ne trouve pas beaucoup de référence à une telle approche dans la littérature, donc je m'attends à ce que ce soit parce qu'elle n'est pas très efficace. Je voudrais comprendre pourquoi ce n'est pas efficace. Y a-t-il des cas où c'est un bon choix?
Dans mes recherches je m'intéresse à la solution des problèmes elliptiques 3d dans un environnement parallèle (mpi).
la source
Réponses:
Il est intéressant de noter que cette question est venue hier, car je viens de terminer une mise en œuvre hier qui fait cela.
Mon parcours
Pour commencer, faites-moi savoir que même si mes études sont issues de l'informatique scientifique, tout le travail que j'ai accompli depuis l'obtention de mon diplôme, y compris mon doctorat actuel. travail, a été en électromagnétique de calcul. Donc, je suppose que nos antécédents sont quelque peu similaires, car vous semblez également regarder la physique (en fonction de votre profil).
FGMRES
Tout d'abord, ce que vous recherchez, comme Guido Kanschat l'a déjà mentionné dans un commentaire, s'appelle Flexible GMRES ou FGMRES. La référence, y compris le pseudocode, est dans [1]. Bien que je trouve parfois les articles numériques SIAM un peu difficiles à lire, [1] (et la plupart des autres travaux de Saad, y compris le brillant [B1], apparemment légalement disponible gratuitement en ligne) est différent; l'article est une lecture fascinante, très clairement écrite et avec quelques bons exemples et suggestions d'applications.
FGMRES est facile à implémenter, en particulier si vous avez déjà un GMRES préconditionné qui fonctionne. Notez le mot-clé DROIT ici - si vous avez un GMRES préconditionné GAUCHE, c'est-à-dire que vous avez l'habitude de résoudre MAx = Mb, alors vous devez faire quelques modifications. Comparez [B1, algorithme 9.4 à la p. 282] à [B1, algorithme 9.5, p. 284]. Vous pouvez également trouver le FGMRES dans [B1, algorithme 9.6, p. 287], mais je vous encourage vraiment à lire [1] car il est court, bien écrit et contient encore de nombreux détails intéressants.
Qu'est ce que ça fait
FGMRES vous permet essentiellement de changer de préconditionneur pour chaque itération, si vous le souhaitez. L'une des applications pour cela est que vous pouvez utiliser un préconditionneur qui fonctionne très bien lorsque vous êtes loin de la solution, puis passer à un autre lorsque vous vous rapprochez. [2], que je n'ai pas lu en détail, semble discuter de quelque chose de similaire à cela.
Cependant, l'application la plus intéressante dans mon cas était que vous pouviez utiliser un GMRES (préconditionné) comme préconditionneur pour votre FGMRES. C'est la raison derrière le nom typique de FGMRES, "GMRES intérieur-extérieur". Ici, "externe" fait référence au solveur FGMRES, qui (en tant que préconditionneur) utilise un solveur "interne".
Alors, comment est-ce bien dans la pratique?
Dans mon cas, cela a fonctionné absolument génial. Dans la boucle intérieure, je «résous» une formulation à complexité réduite de mon problème. À elle seule, cette solution est beaucoup trop imprécise pour notre utilisation, mais elle fonctionne très bien comme préconditionneur. Notez la résolution «autour» - il n'est pas nécessaire d'exécuter le solveur interne pour converger, car vous ne recherchez que des approximations approximatives. Dans mon cas, je suis passé de 151 itérations, chacune coûtant 64 secondes, à 72 itérations, chacune coûtant 79 secondes (j'ai utilisé 5 itérations fixes dans le GMRES interne). C'est une économie totale d'une heure, sans perte de précision et très peu de travail de codage puisque nous avions déjà un GMRES fonctionnel que nous venons de rendre récursif.
Pour certaines applications de ce genre, démontrant les performances potentielles, voir [3] (qui utilise en fait un FGMRES à trois niveaux, donc FGMRES, avec FGMRES comme interne, avec GMRES comme interne-interne) et [4], qui pourrait être trop application spécifique à votre utilisation, mais contient plusieurs cas de test intéressants.
Les références
[1] Y. Saad, «Un algorithme GMRES préconditionné intérieur-extérieur flexible», SIAM J. Sci. Comp., Vol. 14, non. 2, pp. 461–469, mars 1993. http://www-users.cs.umn.edu/~saad/PDF/umsi-91-279.pdf
[2] D.-Z. Ding, R.-S. Chen et Z. Fan, «Méthode GMRES flexible intérieure-extérieure préconditionnée SSOR pour l'analyse MLFMM de la diffusion d'objets ouverts», Progress In Electromagnetics Research, vol. 89, pp. 339–357, 2009. http://www.jpier.org/PIER/pier89/22.08112601.pdf
[3] TF Eibert, «Certains résultats de diffusion calculés par des techniques d'équation intégrale de surface et hybrides d'éléments finis intégrales, accélérés par la méthode multipolaire rapide à plusieurs niveaux», IEEE Antennas and Propagation Magazine, vol. 49, non. 2, p. 61–69, 2007.
[4] Ö. Ergül, T. Malas et L. Gürel, «Solutions of Large-Scale Electromagnetics Problems using an Iterative Inner-Outer Scheme with Ordinary and Approximate Multilevel Fast Multipole Algorithms,» Progress In Electromagnetics Research, vol. 106, p. 203–223, 2010. http://www.jpier.org/PIER/pier106/13.10061711.pdf
[B1] Y. Saad, Méthodes itératives pour les systèmes linéaires clairsemés. SIAM, 2003. http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf
la source
Une telle méthode de sous-espace Krylov imbriquée peut très bien fonctionner dans la pratique. Cela peut être intéressant pour les systèmes linéaires non symétriques pour lesquels GMRES redémarré stagne et GMRES non redémarré est trop cher ou utilise trop de mémoire. Quelques publications:
la source