Extraction des capacités par méthode multipolaire rapide à multi-niveaux adaptatifs

Extraction des capacités par méthode multipolaire rapide à multi-niveaux adaptatifs

Dans ce troisième chapitre, on présentera une méthode numérique d’approximation d’in- teractions lointaines, la méthode multipolaire rapide à multi-niveaux adaptatifs (Adap-tive Mutli-Level Fast Multipole Method ou AMLFMM). Elle permet d’accélérer le calcul du potentiel et du champ normal pour des interactions lointaines par le biais d’approximations en fonction de la distance entre chaque élément. Par conséquent, cela permet de gagner énormément en temps de calcul et en place mémoire tout en maîtrisant la précision des cal- culs. L’adaptation de la méthode originale à notre problème et l’utilisation du solveur itératif GMRES(m) permettent de traiter des grands problèmes en très peu de temps et avec très peu de place mémoire. Grâce aux travaux de Greengard et al. [47, 48], la méthode multipolaire rapide – Fast Multipole Method (FMM) – apparaît dans les années 80 pour évaluer plus rapidement le potentiel électrique créé par des nuages de charges ponctuelles. Par la suite, White et Naibors au MIT ont appliqué cette méthode au calcul des capacités parasites des micro-processeurs dans les années 90 [32, 33, 49]. Enfin, cette méthode est très largement utilisée dans la communauté des hautes fréquences par les antennistes. Effectivement, dans ces applications l’air est prédominant et rend quasiment impossible l’utilisation de méthodes comme la méthode des éléments finis à cause du maillage de l’air. Le coût de calcul des interactions passe d’une loi en O(N 2) pour la méthode en interaction totale présentée précédemment à une loi en O(N log N ). Ce résultat est visuel comme le montre la figure III.1.

Dans cette figure, on a considéré 4 conducteurs surfaciques, chacun est maillé en 75 éléments. Au milieu de la figure sont représentés toutes les interactions lointaines. Chaque élément interagit avec tous les autres. On rappelle que pour chaque interaction, un coefficient sera calculé est placé dans la matrice d’interaction.A droite, sont représentés les interactions lointaines avec la FMM. On remarque que certains chemins d’interaction sont communs à plusieurs éléments. Ces chemins sont créés en fonction de l’éloignement des éléments à l’aide d’un découpage en cube de différents niveaux (appelé par- titionnement). A chacun des chemins d’interaction correspond cette-fois ci un développement multipolaire tronqué à un certain degré (défini dans la section suivante) permettant d’approximer le potentiel (ou le champ). Ce choix de décomposition (ou de degré de troncature) dépend de la distance entre le point de calcul du potentiel et la source. La Fast Multipole Method permet de contrôler cette notion d’éloignement à l’aide du partitionnement.

En réalité, on ne construit pas de matrice d’interaction avec la FMM comme dans le chapitre précédent II. Un ensemble de matrices d’interaction proches et de vecteurs d’interactions lointaines est intégré et directement utilisé pour évaluer le potentiel et le champ normal. On n’obtient plus de vraie matrice, c’est pourquoi il est nécessaire d’utiliser un solveur itératif pour résoudre le problème électrostatique. Ce solveur présenté plus loin (section 5.3) cherche une solution approchée du problème en faisant des produits ”[P/En]”.q (on rappelle que [P/En] est la matrice d’interaction de la méthode intégrale en interaction totale).D’un point de vue plus théorique, la FMM repose sur des décompositions en harmoniques sphé- riques du potentiel qui sont solutions de l’équation de Laplace. Une fonction est dite harmonique si son laplacien est nul. En physique, on retrouve ces fonctions en acoustique, en géophysique, en cristallographie , en physique quantique et dans notre cas, théorie du potentiel newtonien…On verra dans la section suivante que les coefficients des harmoniques sphériques, exprimés en coordonnées sphériques, utilisent ces fonctions propres avec pour variable cos θ. Dans ce cas par- ticulier, ces fonctions propres peuvent être également obtenues par une récurrence d’ordre 2.

Dans cette partie, on présentera la décomposition du potentiel en un point P quelconque de l’espace, de coordonnées sphériques (r, θ, φ), dû à un ensemble de N charges ponctuelles qi de coordonnées Qi = (ρi, αi, βi) (Fig. III.3). Le théorème suivant est issu de la théorie des harmoniques sphériques [47] :L. Greengard et V. Rokhlin ont poussé plus loin cette théorie en établissant d’autres théorèmes sur les propriétés des harmoniques sphériques. Les démonstrations de ces théorèmes, détaillés dans l’article [47], ne seront pas présentés ici. Ces théorèmes fondamentaux sont la base de la FMM.