Multigrille sur grille «pas parfaitement rectangulaire»

Les introductions multigrilles utilisent normalement une grille rectangulaire. L'interpolation des valeurs est alors simple: il suffit d'interpoler linéairement sur le bord entre deux nœuds adjacents de la grille grossière pour trouver la valeur du nœud de grille fine sur ce bord.

Pour une application FEM, j'ai une grille qui est "topologiquement" rectangulaire de sorte que les connexions des nœuds sont comme sur une grille rectangulaire. Cependant, les nœuds ne sont pas parfaitement alignés sur une grille mais peuvent parcourir de petites distances afin de mieux s'adapter à la géométrie, tout en conservant les connexions comme dans une grille rectangulaire parfaite.

Le maillage ressemble à ça: exemple de maillage . Vous voyez: les connexions sont "rectangulaires régulières", mais pas les positions des nœuds.

Je peux imaginer plusieurs schémas d'interpolation géométrique "raisonnables" pour un tel réglage.

La question générale est la suivante: le multigrille nécessite-t-il une grille rectangulaire parfaitement alignée, ou fonctionnera-t-il également avec la situation décrite ci-dessus, tant que l'interpolation est "bonne"? Ou est-il préférable d'utiliser le multigrille algébrique dans ce cas? (Ce que je ne préfère pas car ce n'est pas aussi intuitif que multigrille géométrique.)

multigrid Michael
la source

Je ne suis pas sûr de comprendre ce que vous entendez par la grille étant topologiquement rectangulaire, mais où les nœuds ne sont pas alignés comme dans une grille rectangulaire. La grille est-elle une grille rectangulaire structurée? Pourriez-vous clarifier cela, peut-être avec un dessin? Le problème est que vous utilisez des éléments rectangulaires qui ne s'alignent pas comme cela se produirait lors de l'utilisation d'une grille cartésienne structurée?

James

@James, j'ai interprété la question de OP comme suit: "Que se passe-t-il si j'ai une grille" cartésienne "à l'intérieur d'un trapèze?".

Bill Barth

Réponses:

Multigrid n'a pas besoin d'une grille cartésienne (rectangulaire) et uniforme. Ce qu'il faut, c'est que vous puissiez définir un niveau fin et un niveau grossier (éventuellement récursivement, si vous voulez passer d'un schéma à deux niveaux à un schéma à plusieurs niveaux), et que vous pouvez définir des opérateurs d'interpolation entre ces niveaux. La façon la plus simple d'expliquer cela est si vous avez en effet une grille cartésienne, mais vous pouvez en fait commencer avec n'importe quel maillage grossier, l'affiner une fois, et juste comme ceci: vous avez un maillage plus fin.

En d'autres termes, il est plus facile de penser aux maillages adaptés à plusieurs grilles non pas comme un maillage fin et comment trouver les maillages les plus grossiers, mais pour commencer avec un maillage grossier à partir duquel vous obtenez les niveaux les plus fins par un raffinement uniforme (c'est-à-dire que chaque quadrilatère est subdivisés en quatre plus petits). Comme un raffinement uniforme est toujours possible, cela vous donne facilement une hiérarchie. Cela s'oppose au grossissement, ce qui n'est pas toujours possible si l'on ne vous donne qu'un maillage particulier, ce qui rend la définition d'une hiérarchie de maillage beaucoup plus compliquée. (C'est pourquoi les gens ont mis au point des méthodes algébriques multigrilles pour définir les niveaux grossiers basés uniquement sur la matrice, sans penser au maillage sous-jacent à partir duquel il a été créé.)

Wolfgang Bangerth
la source

J'ai édité un exemple d'image dans la question. Je suppose que le grossissement est extrêmement facile dans mon cas en ne prenant que tous les 2 nœuds (par dimension) et en recalculant FEM pour cette grille pour obtenir la matrice / l'opérateur grossier. Le vecteur de données grossier peut être obtenu en prenant simplement chaque deuxième valeur de nœud.

Michael

Cela peut ou non fonctionner aussi bien que vous le souhaitez (je suppose que ce sera probablement le cas, mais je ne suis pas complètement sûr). Le fait est que dans votre exemple, les cellules de maillage grossier ne couvrent pas la même zone que les enfants, et donc il n'y a pas de propriété d'imbrication des espaces d'éléments finis: les fonctions que vous pouvez représenter sur le maillage grossier ne sont pas un sous-ensemble de les fonctions que vous pouvez représenter sur le maillage fin. Joe Pasciak et Jim Bramble ont écrit des articles sur de tels cas, et je pense que je me souviens qu'ils peuvent être mis au travail. Mais ce n'est pas immédiatement évident pour moi.

Wolfgang Bangerth

Disons que vous avez la grille suivante composée d'éléments rectangulaires:

Maintenant, si vous effectuez votre interpolation en supposant une grille rectangulaire structurée normale, vous introduirez des erreurs associées à cette interpolation inexacte. En d'autres termes, lorsque vous limitez votre vecteur résiduel et que vous prolongez votre vecteur d'erreur, il y aura des erreurs d'interpolation.

Maintenant, si votre grille est "proche" d'être une grille cartésienne structurée normale, cela peut fonctionner, au moins au début, mais je soupçonne qu'une des deux choses se produira en fonction de la distance entre la grille et la forme rectangulaire:

1) Vous pourriez constater que la multigrille commence à converger au début. Après tout, au départ, votre erreur est importante et votre interpolation "approximative" signifie simplement que certains nœuds sont légèrement surreprésentés tandis que d'autres sont légèrement sous-représentés. Cependant, vous pouvez constater que la convergence stagne à mesure que la solution devient plus précise et que les erreurs d'interpolation deviennent plus importantes.

2) Une autre possibilité est que la multigrille finit par converger, mais pas aussi vite qu'elle le devrait si vous aviez utilisé l'interpolation correcte.

Fondamentalement, en étant déconnecté de votre interpolation, vous pondérez de manière inexacte l'importance de certains nœuds. Par exemple en 2D si vous pondérez un nœud donné comme:

[\begin{matrix} 0,25 & 0,5 & 0,25 \\ 0,5 & 1.0 & 0,5 \\ 0,25 & 0,5 & 0,25 \end{matrix}]

$\begin{bmatrix} 0.25 & 0.5 & 0.25 \\ 0.5 & 1.0 & 0.5 \\ 0.25 & 0.5 & 0.25 \end{bmatrix}$

alors qu'en vérité parce que votre grille n'est pas exactement cartésienne, elle devrait être:

[\begin{matrix} 0,25 & 0,55 & 0,25 \\ 0,55 & 1.0 & 0,49 \\ 0,28 & 0,52 & 0,30 \end{matrix}]

$\begin{bmatrix} 0.25 & 0.55 & 0.25 \\ 0.55 & 1.0 & 0.49 \\ 0.28 & 0.52 & 0.30 \end{bmatrix}$

alors cela entraînera une erreur. Que cette erreur empêche la convergence dépendra probablement de la distance à laquelle votre réseau est cartésien.

Bien que AMG soit plus difficile à comprendre / implémenter, il semble que ce soit la bonne méthode pour votre grille. L'application multigrille géométrique à une grille rectangulaire "approximative" peut fonctionner, mais je suppose que c'est au mieux une solution de pansement. J'espère que cela t'aides.

Mise à jour : Je pense qu'il y a peut-être eu une certaine confusion dans ma réponse. Je ne dis pas que la multigrille géométrique ne fonctionnera qu'avec les mailles cartésiennes, mais plutôt que la définition de l'interpolation (et donc de la restriction) sur les mailles cartésiennes est facile alors que sur les mailles non structurées cela peut être difficile. Par exemple, considérons le cas d'un domaine 2D même simple avec un maillage triangulaire. Affiner ce maillage est facile - au moins conceptuellement - mais comment définiriez-vous un opérateur d'interpolation entre le maillage grossier et le maillage fin? Je préfère AMG tout simplement parce qu'il fonctionne plus comme un solveur de "boîte noire", c'est-à-dire qu'il n'a pas besoin d'informations sur le maillage sous-jacent, mais ce n'est que le biais / bizarrerie de ma personne. La multigrille géométrique peut fonctionner tant que vous pouvez fournir des opérateurs d'interpolation précis.

James
la source

Je peux lire ceci comme "dépend de la qualité de votre interpolation", n'est-ce pas? Donc, si je peux trouver un schéma d'interpolation "parfait", alors ça devrait aller?

Michael

Je pense que cette réponse est vraie mais trompeuse - elle dit que si vous prétendez que votre grille est cartésienne régulière quand elle ne l'est pas, vous obtiendrez la mauvaise réponse. C'est vrai, mais on pourrait dire la même chose de n'importe quelle méthode numérique. Le fait est que la multigrille géométrique est précise sur des maillages plus généraux lorsqu'elle est implémentée correctement .

David Ketcheson

Je suis d'accord que le multigrille géométrique peut être utilisé avec des maillages non cartésiens tant qu'il est fait correctement. Je viens de prendre la question OP comme demandant si l'utilisation d'un maillage cartésien "approximativement", tout en utilisant une interpolation conçue pour un maillage cartésien réel, fonctionnerait.

James

@Michael Fondamentalement, vous avez besoin d'un moyen de définir des opérateurs d'interpolation entre différents niveaux de grille. Avec les maillages cartésiens, c'est facile. Avec les maillages non cartésiens, cela peut rapidement devenir plus difficile en fonction de la structure de vos maillages. Comme Wolfgang le dit dans sa réponse, vous pouvez toujours créer un maillage plus raffiné à partir d'un maillage grossier, mais définir des opérateurs d'interpolation significatifs peut être difficile. L'avantage d'AMG est qu'il se comporte plus comme un solveur "boîte noire" en ce que vous n'avez pas besoin de données de maillage pour définir les opérateurs d'interpolation. Tout ce dont vous avez besoin est la matrice

James

@MIchael Donc pour répondre à votre question. Oui, si vous pouvez trouver des opérateurs d'interpolation précis, la multigrille géométrique fonctionnera bien. J'espère que cela t'aides.

James