Résoudre un système clairsemé et très mal conditionné

J'ai l'intention de résoudre Ax = b où A est une matrice carrée ou rectangulaire complexe, clairsemée, asymétrique et très mal conditionnée (nombre de conditions ~ 1E + 20). J'ai pu résoudre le système avec ZGELSS dans LAPACK avec précision. Mais à mesure que les degrés de liberté dans mon système augmentent, il faut beaucoup de temps pour résoudre le système sur un PC avec ZGELSS car la rareté n'est pas exploitée. Récemment, j'ai essayé SuperLU (en utilisant le stockage Harwell-Boeing) pour le même système, mais les résultats étaient inexacts pour le numéro de condition> 1E + 12 (je ne suis pas sûr que ce soit un problème numérique avec le pivotement).

Je suis plus enclin à utiliser des solveurs déjà développés. Existe-t-il un solveur robuste qui peut résoudre le système que j'ai mentionné rapidement (c'est-à-dire en exploitant la rareté) et de manière fiable (au vu des nombres de conditions)?

linear-solver sparse-matrix lapack condition-number user1234
la source

Pouvez-vous le préconditionner? Si c'est le cas, les méthodes du sous-espace de Krylov pourraient être efficaces. Même si vous insistez sur des méthodes directes, le préconditionnement aidera à contrôler les erreurs numériques.

Geoff Oxberry

J'ai également fait une bonne expérience du préconditionnement à peu près comme il est décrit ici: en.wikipedia.org/wiki/… Vous pouvez effectuer le préconditionnement en arithmétique exacte. Mes matrices sont cependant toutes denses, donc je ne peux pas vous indiquer ici des méthodes / routines plus spécifiques.

AlexE

Pourquoi le numéro de condition est-il si grand? Peut-être que la formulation peut être améliorée pour rendre le système mieux conditionné? En général, vous ne pouvez pas vous attendre à être en mesure d'évaluer un résidu avec plus de précision que , ce qui rend Krylov de peu de valeur une fois que vous n'avez plus de bits. Si le numéro de condition est vraiment , vous devez utiliser la précision quadruple ( avec GCC, pris en charge par quelques packages dont PETSc).

(machine precision) \cdot (condition number)

$(\text{machine precision})\cdot(\text{condition number})$

10^{20}

$10^{20}$ __float128

Jed Brown

D'où obtenez-vous cette estimation du nombre de conditions? Si vous demandez à Matlab d'estimer le nombre de conditions d'une matrice avec un espace nul, cela pourrait vous donner une infinité ou parfois cela pourrait simplement vous donner un nombre vraiment énorme (comme ce que vous avez). Si le système que vous regardez a un espace nul et que vous savez de quoi il s'agit, vous pouvez le projeter et ce qui vous reste peut avoir un meilleur numéro de condition. Ensuite, vous pouvez utiliser PETSc ou Trilinos ou ce que vous avez.

Daniel Shapero

Daniel - la méthode SVD tronquée utilisée par ZGELSS détermine l'espace nul (les vecteurs singuliers associés à de minuscules valeurs singulières dans le SVD sont une base pour N (A)) et trouve la solution des moindres carrés àsur .

min ‖ A x - b ‖

$\min \| Ax-b \|$

p e r p (N (A))

$perp(N(A))$

Brian Borchers

Réponses:

Lorsque vous utilisez ZGELSS pour résoudre ce problème, vous utilisez la décomposition de valeurs singulières tronquées pour régulariser ce problème extrêmement mal conditionné. il est important de comprendre que cette routine de bibliothèque n'essaie pas de trouver une solution des moindres carrés à , mais plutôt d'essayer d'équilibrer la recherche d'une solution qui minimisecontre la minimisation. $Ax=b$ $\| x \|$ $\| Ax-b \|$

Notez que le paramètre RCOND passé à ZGELSS peut être utilisé pour spécifier quelles valeurs singulières doivent être incluses et exclues du calcul de la solution. Toute valeur singulière inférieure à RCOND * S (1) (S (1) est la plus grande valeur singulière) sera ignorée. Vous ne nous avez pas dit comment vous avez défini le paramètre RCOND dans ZGELSS, et nous ne savons rien du niveau de bruit des coefficients dans votre matrice ou dans le côté droit , il est donc difficile de dire si vous avez utilisé une régularisation appropriée. $A$ $b$

Vous semblez être satisfait des solutions régularisées que vous obtenez avec ZGELSS, il semble donc que la régularisation effectuée par la méthode SVD tronquée (qui trouve une solution minimale parmi les solutions les moins carrées qui minimisent sur l'espace des solutions couvertes par les vecteurs singuliers associés aux valeurs singulières supérieures à RCOND * S (1)) vous satisfait. $\| x \|$ $\| Ax-b \|$

Votre question pourrait être reformulée comme "Comment puis-je obtenir efficacement des solutions de moindres carrés régularisés à ce problème de moindres carrés linéaires volumineux, clairsemé et très mal conditionné?"

Ma recommandation serait d'utiliser une méthode itérative (comme CGLS ou LSQR) pour minimiser le problème des moindres carrés explicitement régularisés

$\min \| Ax-b \|^{2} + \alpha^{2} \| x \|^{2}$

où le paramètre de régularisation est ajusté pour que le problème des moindres carrés amortis soit bien conditionné et que vous soyez satisfait des solutions régularisées résultantes. $\alpha$

Brian Borchers
la source

Je m'excuse de ne pas l'avoir mentionné au départ. Le problème résolu est l'équation de Helmholtz de l'acoustique utilisant FEM. Le système est mal conditionné en raison de la base d'onde plane utilisée pour approximer la solution.

user1234

D'où viennent les coefficients en et ? S'agit-il de données mesurées? des valeurs "exactes" de la conception d'un objet (qui en pratique ne peuvent pas être usinées à des tolérances de 15 chiffres ...)?

A

$A$

b

$b$

Brian Borchers

Les matrices A et b sont formées en utilisant la formulation faible de Helmholtz PDE, voir: asadl.org/jasa/resource/1/jasman/v119/i3/…

user1234

Jed Brown l'a déjà souligné dans les commentaires à la question, mais il n'y a vraiment pas grand-chose que vous puissiez faire en double précision habituelle si votre numéro de condition est grand: dans la plupart des cas, vous n'obtiendrez probablement pas un seul chiffre de précision dans votre solution et, pire, vous ne pouvez même pas le dire car vous ne pouvez pas évaluer avec précision le résidu correspondant à votre vecteur de solution. En d'autres termes: il ne s'agit pas de savoir quel solveur linéaire choisir - aucun solveur linéaire ne peut faire quelque chose d'utile pour de telles matrices.

Ce genre de situations se produit généralement parce que vous choisissez une base inappropriée. Par exemple, vous obtenez de telles matrices mal conditionnées si vous choisissez les fonctions comme base d'une méthode de Galerkin. (Cela conduit à la matrice de Hilbert, qui est notoirement mal conditionnée.) La solution dans de tels cas n'est pas de demander quel solveur peut résoudre le système linéaire, mais de demander s'il existe de meilleures bases qui peuvent être utilisées. Je vous encourage à faire de même: pensez à reformuler votre problème pour ne pas vous retrouver avec ce genre de matrices. $1,x,x^2,x^3,...$

Wolfgang Bangerth
la source

Lorsque nous discrétisons un problème mal posé pour une PDE, par exemple une équation de chaleur vers l'arrière, nous nous retrouverons certainement avec une équation matricielle mal conditionnée. Ce n'est pas le cas que nous pouvons résoudre en reformulant l'équation ou en choisissant un solveur matriciel efficace ou en améliorant la précision en nombre à virgule flottante. Dans ce cas [c.-à-d. Problèmes acoustiques inverses], une méthode de régularisation est requise.

tqviet

Le moyen le plus simple / le plus rapide de résoudre des problèmes mal conditionnés consiste à augmenter la précision des calculs (par force brute). Une autre manière (pas toujours possible) consiste à reformuler votre problème.

Vous devrez peut-être utiliser une précision quadruple (34 chiffres décimaux). Même si 20 chiffres seront perdus dans un cours (en raison du numéro de condition), vous obtiendrez toujours 14 chiffres corrects.

Si cela présente un intérêt, des solveurs clairsemés à quadruple précision sont également disponibles dans MATLAB.

(Je suis l'auteur de la boîte à outils mentionnée).

Pavel Holoborodko
la source