Comment les modifications de bas rang affectent-elles la convergence de la méthode Krylov?

14

Disons que j'ai un système linéaire , qui converge rapidement en utilisant une méthode de Krylov appropriée (comme CG ou GMRES) pour tout . Si est une matrice de faible rang , la même méthode de Krylov sur le système convergera-t-elle également rapidement (idéalement avec un nombre supplémentaire d'itérations qui dépend à peu près uniquement de )?b B r ( A + B ) x = b rAx=bbBr(A+B)x=br

Un exemple d'un tel système serait une élasticité et une flexion de membrane bien préconditionnées ainsi que des termes de pression d'air non conditionnés avec une structure de produit externe dense.

Notez que la question est la même avec ou sans préconditionnement, car est une modification de rang de .r P A QP(A+B)Q=PAQ+PBQrPAQ

Geoffrey Irving
la source

Réponses:

7

Si votre sous-espace Krylov est basé sur les puissances de , la convergence sera retardée par un certain nombre d'itérations au plus le rang de la correction. S'il est basé sur les puissances de A T A, alors au plus le double de ce nombre.UNEUNETUNE

Je n'ai pas vu une telle déclaration dans la littérature. Mais pour voir la validité dans le premier cas, il suffit de montrer que le ème espace Krylov de la matrice A + U S V TU , V ont r colonnes est contenu dans l'espace correspondant sans corrections de bas rang mais avec un indice k + r correspondant plus élevé . C'est simple à vérifier.kUNE+USVTU,Vrk+r

Arnold Neumaier
la source
Pouvez-vous expliquer ce que vous entendez par "sur la base des pouvoirs de "? Le solveur Krylov reçoit uniquement des informations sur A + B , pas directement sur A. UNEUNE+BUNE
Geoffrey Irving,
Peu importe: vous parlez probablement des pouvoirs de la matrice en question, donc dans ce cas. UNE+B
Geoffrey Irving
Oui. Le procédé comporte une matrice en tant que paramètre, et cette matrice est généralement désigné par . UNE
Arnold Neumaier
Peut-être que pour plus d'intérêt, vous pourriez réécrire votre équation (ou la solution) avec quelques exigences sur à x = ( E + k = 1 ( A - 1 B ) k ) A - 1 b qui pourrait aider si B est nilpotent ou A - 1 B de petite norme. On reconnaît également la dépendance à l'égard de la solution du problème. BX=(E+k=1(UNE-1B)k)UNE-1bBUNE-1Bundisturbed
Bastian Ebeling