[image] [image] Ressource protégée - Archive ouverte HAL Accéder directement au contenu

*[image] [image]*

• [Documentation](#)

• FR
Français (FR)

• Anglais (EN)
Se connecter

• [HAL science ouverte](#)

• Recherche
Loading...

## Recherche avancée

Information de documents

Titres

○ [Titres](#)

○ [Sous-titre](#)

○ Titre de l'ouvrage

○ Titre du volume (Série)

○ Champ de recherche par défaut (multicritères) + texte intégral des PDF

○ [Résumé](#)

○ Texte intégral indexé des documents PDF

○ [Mots-clés](#)

○ Type de document

○ Sous-type de document

○ Tous les identifiants du document

○ Identifiant HAL du dépôt

○ Langue du document (texte)

○ Pays (Texte)

○ Ville

○ À paraître (true ou false)

Ajouter

Auteur
<figure><img src="image_1.png" /></figure>

HAL
open science

# Using the Fast Multipole Method to Accelerate Matrix-Vector Product: Application to the Magnetostatic Moment Method

Antoine Gicquel, Olivier Coulaud

► To cite this version:

Antoine Gicquel, Olivier Coulaud. Using the Fast Multipole Method to Accelerate Matrix-Vector Product: Application to the Magnetostatic Moment Method. LA24 - SIAM Conference on Applied Linear Algebra, May 2024, Paris, France. pp.19. hal-04588314

HAL Id: hal-04588314

https://inria.hal.science/hal-04588314v1

Submitted on 26 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
## Auteur (multicritères)

○ Auteur (multicritères)

○ Auteur : Nom complet

○ Auteur : Nom de famille

○ Auteur : Prénom

○ Auteur : Complément de nom, deuxième prénom

○ Auteur : Organisme payeur

○ Auteur : IdHal (chaîne de caractères)

○ Auteur : Fonction

○ Auteur : personID (entier)

○ Auteur : Identifiant de l'organisme payeur

○ Auteur : Identifiant de la structure

○ Directeur de thèse

○ Éditeur

○ Éditeur scientifique

○ Éditeur de la série

## Ajouter

### Structure

### Structure (multicritères)

○ Structure (multicritères)

○ Structure : Acronyme

○ Structure : Nom

○ Structure : Code

○ Structure : Pays

○ Structure : Type

○ Structure : État dans le référentiel

○ Structure : Identifiant HAL de la structure

○ Structure/équipe de recherche : Pays

○ Structure/regroupement d'équipes : Pays

○ Structure/laboratoire : Pays

○ Structure/regroupement de laboratoires : Pays

○ Structure/institution : Pays

○ Structure/regroupement d'institutions : Pays

## Ajouter

## Autres
# Using the Fast Multipole Method to Accelerate Matrix-Vector Products

- Application to the Magnetostatic Moment Method -

Antoine GICQUEL & Olivier COULAUD

INRIA Bordeaux (Concace team)

SIAM LA24, May 2024
Champ de recherche par défaut (multicritères)

○ <u>Champ de recherche par défaut (multicritères)</u>

○

○ <u>Revues (multicritères)</u>

○ <u>Revue : Éditeur</u>

○ <u>Revue : Titre abrégé</u>

○ <u>Revue : Titre</u>

○ <u>Revue : Identifiant interne</u>

○ <u>Revue : Date de début de publication</u>

○ <u>Revue : ISSN électronique</u>

○ <u>Revue : ISSN</u>

○ <u>Revue : Éditeur</u>

○ <u>Revue : Couleur dans SHERPA/RoMEO</u>

○ <u>Revue : État dans le référentiel</u>

○

○ <u>Colloque (multicritères)</u>

○ <u>Colloque : Titre</u>

○ <u>Colloque : Organisateur</u>

○ <u>Colloque : date de début (Année)</u>

○ <u>Colloque : date de fin (Année)</u>

○ <u>Conférence invitée (oui/non)</u>

○

○ <u>Projets ANR (multicritères)</u>

○ <u>Projet ANR : Acronyme</u>

○ <u>Projet ANR : Acronyme du programme</u>

○ <u>Projet ANR : Code décision (référence)</u>

○ <u>Projet ANR : Nom</u>

○ <u>Projet ANR : Identifiant interne</u>

○ <u>Projet ANR : État dans le référentiel</u>

○

○ <u>Projets européens (multicritères)</u>

○ <u>Projet européen : Acronyme</u>

○ <u>Projet européen : Identifiant de l'appel à projet</u>

○ <u>Projet européen : Référence</u>

○ <u>Projet européen : Nom</u>

○ <u>Projet européen : Date de fin</u>

○ <u>Projet européen : Financement</u>

○ <u>Projet européen : Date de début</u>

○ <u>Projet européen : État dans le référentiel</u>
# Introduction

## Context

### Electrical engineering

* **Importance of numerical modeling methods**

* Small electrical devices (electric motors, printed circuit boards ...)

* Rapid prototyping

* Shape optimization

* Parametric study

### TensorVim ANR (French National Research Agency) project

* **Objective:** Developing efficient iterative methods for Magnetostatic problems

* Compression techniques (FMM, H-matrix...)

* GMRES preconditioners (tensor decomposition...)

* **Joint work**

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>
○ Projet européen : Identifiant interne

O

○ Date de production : année

○ Date de mise en ligne : année

○ Date de publication : année

○ Date d'écriture : année

○ Date de modification du dépôt : année

○ Date de dépôt : année

○ Date de publication électronique : année

O

○ Collection HAL (multicritères)

Collection HAL : catégorie

○ Collection HAL : Code

○ Collection HAL : Nom

○ Collection HAL : Identifiant interne

O

○ Identifiant interne du contributeur/déposant

○ Nom complet du contributeur/déposant

O

○ Domaines

○ Domaine primaire

○ Domaine racine

○ Sous-domaine niveau 1

○ Sous-domaine niveau 2

○ Sous-domaine niveau 3

O

○ Statut du document

○ Version du document

○ Type de dépôt

○ Type de document

○ ISBN

○ Numéro - référence

○ Identifiant DOI

O

○ Classification

○ Audience

○ Vulgarisation

○ Comité de lecture - texte (oui ou non)

○ Actes de colloque

○ Référence interne
# Introduction

## Problem statement

### Magnetostatic problem

* Goal: Find **H** in $\Omega$

* Static Maxwell's equations (magnetism only):

$$ egin{cases} \nabla \cdot \mathbf{B}(x) = 0 \\ \nabla \times \mathbf{H}(x) = \mathbf{J}_S(x) \quad \forall x \in \Omega \end{cases} $$

* Constitutive law: $M = (\mu_r - 1)H$

<figure><img src="image_5.png" /></figure>

### Model magnetostatic problem

$$ \Omega = \Omega_0 \cup \Omega_F \cup \Omega_S $$

### Solving approaches

* Finite Element Method
  $\leftrightarrow$ artificial boundary, $\Omega$ is entirely meshed, large sparse matrix

* Volume Integral Methods (e.g., the Magnetostatic Moment Method (MMM))
  $\leftrightarrow$ only the magnetic material $\Omega_F$ is meshed, less unknowns, small dense matrix

### Magnetic vector formulation [Chadebec et al. 2006]

$$ \mathbf{M}(x) + \int_{\Omega_F} \frac{1 - \mu_r(y)}{4\pi} \left( \nabla_y \frac{(y-x) \cdot \mathbf{M}(y)}{\|y-x\|^3} \right) dy = (\mu_r(x) - 1) \mathbf{H}_S(x) \quad \forall x \in \Omega_F. $$
○ Financement

○ Collaborations

Ajouter

Lancer la recherche

Recherche experte (SolR)

Recherche experte (SolR)

Lancer la recherche
Vers la recherche avancée

• Déposer

X

X

X

Loading...

X

Le document avec l'identifiant n'est pas visible actuellement !

Retourner à l'accueil

[image]

[image]

[image]

[image]

Contact

• Support

Ressources

• Documentation

• FAQ

• API

• OAI-PMH

• AuréHAL
# Introduction

## Magnetostatic Moment Method (MMM)

### Discretization

The magnetic material $\Omega_F$ is meshed with $N$ elements $\Omega_{Fh} = \cup_{i=1}^N V_i$

* $P_0$ approximation of $M = (M_x, M_y, M_z)^T$

* Collocation formulation $(M^i = M(x_i))$ with $x_i$ the barycenter of $V_i$ ($i = 1, \dots, N$)

$$ (\mathbf{AM})(x_i) = (\mathbf{AM})_i = \mathbf{M}^i + \sum_{j=1}^{N} (1 - \mu_{rj}) \int_{V_j} \frac{1}{4\pi} \nabla_y \left( \frac{(y - x_i) \cdot \mathbf{M}^j}{\|x_i - y\|^3} \right) dy = \frac{(\mu_{r_i} - 1) \mathbf{H}_S(x_i)}{b_i} $$

* Dense nonsymmetric $3N \times 3N$ linear system (3 degrees of freedom / element)

$$ \begin{pmatrix} [\mathbf{A}_{xx}] & [\mathbf{A}_{xy}] & [\mathbf{A}_{xz}] \\ [\mathbf{A}_{yx}] & [\mathbf{A}_{yy}] & [\mathbf{A}_{vz}] \\ [\mathbf{A}_{zx}] & [\mathbf{A}_{zy}] & [\mathbf{A}_{zz}] \end{pmatrix} \begin{pmatrix} [\mathbf{M}_x] \\ [\mathbf{M}_y] \\ [\mathbf{M}_z] \end{pmatrix} = \begin{pmatrix} [b_x] \\ [b_y] \\ [b_z] \end{pmatrix} $$

### Goal and Contribution

* Acceleration of the matrix-vector product (from $O(N^2)$ to $O(N)$)

* Coupling Fast Multipole Method (FMM) + Magnetostatic Moment Method (MMM)

* FMM algorithm: generic and flexible (versatile)
## Informations

* À propos

* Données personnelles

* Mentions légales

* Accessibilité

* Conformité RGAA

## Questions juridiques

* Je publie, quels sont mes droits ?

* Loi pour une République numérique

* Stratégie de non-cession des droits

* SHERPA/ROMEO

## Portails

* Portails institutionnels

* HAL

* HAL SHS

* HAL Thèses

* MédiHAL

## CCSD

* CCSD

* Episciences

* Sciencesconf
1. Introduction

2. Combining the interpolation-based FMM with the MMM

3. Some numerical results

4. Conclusion
### Matrix-vector product

$$ \forall i \in \{1, \dots, N\}, \quad (AM)_i = M^i + \sum_{j=1}^{N} (1 - \mu_{rj}) \int_{V_j} \frac{1}{4\pi} \left( \nabla_y \frac{(y-x_i)}{\|y-x_i\|^3} \right) dy M^j \quad (\text{magnetostatic kernel } k_0) $$

$$ \text{with } k_0(x, y) = \frac{1}{4\pi} \left( 3 \frac{(x-y) \otimes (x-y)}{\|x-y\|^5} - \frac{1}{\|x-y\|^3} l_3 \times l_3 \right) \quad \left\{ \begin{array}{l} \text{singularity when } x \approx y \\ \text{smooth if } \|x-y\| > a \\ \text{decay} \sim \|x-y\|^{-3} \end{array} \right. $$

### Fast Multipole Method (FMM) [Greengard and Rokhlin 1987]

<figure><img src="image_6.png" /></figure>

* Spatial recursive subdivision into cells $C$ (octree)

* Separation of the **near field** from the **far field**

* Hierarchical approximation of the **far field**

$$ x_i \in C_t, \quad (AM)_i = M^i + \sum_{C_s} \sum_{V_j \in C_s} (1 - \mu_{rj}) \int_{V_j} k_0(x_i, y) dy M^j = (A_{\text{near}} M)_i + (A_{\text{far}} M)_i $$
# Combining the interpolation-based FMM with the MMM

## Far-field computation

$\mathcal{N}(C_t)$: neighboring cells of $C_t$

$$ \forall i \in \{1, \dots, N\} \quad x_i \in C_t, \quad (A_{far} M)_i = \sum_{C_s \notin \mathcal{N}(C_t)} \sum_{V_j \in C_s} (1 - \mu_{rj}) \int_{V_j} k_0(x_i, y) dy M^j $$

### Interpolation-based approximation [Fong and Darve 2009]

* 3D grid of $(p+1)^3$ points $(\xi_n^s)_{|n| \le p}$ inside cell $C_s$ (Uniform or Chebyshev points)

* Lagrange polynomials $S_n$ (s.t. $S_n(\xi_m^s) = \delta_{n,m}$)

$$ k_0(x, y) \approx \sum_{|m| \le p} \sum_{|n| \le p} S_m(x) k_0(\xi_m^t, \xi_n^s) S_n(y) \quad \begin{array}{c} \text{source cell } C_s \\ \xrightarrow{\text{dist}(C_s, C_t) > \gamma} \\ \text{target cell } C_t \end{array} \quad \begin{array}{c} (\xi_n^s)_{|n| \le p} \\ \text{X} \\ \text{Y} \end{array} $$

### Resulting far-field approximation

$$ x_i \in C_t, \quad (A_{far} M)_i \approx \sum_{|m| \le p} S_m(x_i) \sum_{C_s \notin \mathcal{N}(C_t)} \sum_{|n| \le p} k_0(\xi_m^t, \xi_n^s) \sum_{V_j \in C_s} (1 - \mu_{rj}) \int_{V_j} S_n(y) dy M^j \quad \begin{array}{c} \text{P2M/M2M} \\ \text{M2L} \\ \hline L2P/L2L \end{array} $$
# Combining the interpolation-based FMM with the MMM

## Far-field computation

### ● Focus on the P2M pass

$$ x_i \in C_t, \quad (A_{far} M)_i \approx \sum_{|m| \le p} S_m(x_i) \sum_{C_s \not\subset N(C_t)} \sum_{|n| \le p} k_0(\xi_m^t, \xi_n^s) \underbrace{\sum_{V_j \in C_s} (1 - \mu_{rj}) \int_{V_j} S_n(y) \, dy}_{\text{FMM}} M^j \\ \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \mathcal{M}_n(C_s) = \sum_{V_j \in C_s} (1 - \mu_{rj}) \int_{V_j} S_n(y) \, dy \quad \forall |n| \le p \quad \text{\textbf{M}}^j \quad \text{\textbf{cell}} C_s $$

<figure><img src="image_7.png" /></figure>

$\int_{V_j} S_n(y) \, dy$ (Gauss-Legendre quadrature rule)
"Exact computation"
# Combining the interpolation-based FMM with the MMM

## Far-field computation

* New expression of the magnetostatic kernel

$$k_0(x, y) = -\nabla_y k_1(x, y) = \nabla_x k_1(x, y) \quad \text{with} \quad k_1(x, y) = \frac{1}{4\pi} \frac{x-y}{\|x-y\|^3}$$

* New kernel interpolation (2nd approach)

$$k_0(x, y) \approx \sum_{|m| \le p} \sum_{|n| \le p} (\nabla_x S_m)(x) k_1(\xi_m^t, \xi_n^s) S_n(y) \quad (\xi_n^s)_{|n| \le p} \xrightarrow{\text{dist}(C_s, C_t) > \gamma} \quad \text{source cell } C_s \quad \text{target cell } C_t$$

* New far-field approximation (2nd approach)

$$x_i \in C_t, \quad (A_{far} M)_i \approx \sum_{|m| \le p} (\nabla_x S_m)(x_i) \sum_{C_s \notin \mathcal{N}(C_t)} \sum_{|n| \le p} k_1(\xi_m^t, \xi_n^s) \underbrace{\sum_{V_j \in C_s} (1 - \mu_{rj}) \int_{V_j} S_n(y) \, dy}_{\text{P2M}/\text{M2M}} \cdot \underbrace{\sum_{M2L}}_{L2P/L2}$$
# Combining the interpolation-based FMM with the MMM

## Comparison of the two approaches

### 1st approximation approach

$$ (A_{far} M)_i \approx \sum_{|m| \le p} S_m(x_i) \sum_{C_s \notin \mathcal{N}(C_t)} \sum_{|n| \le p} k_0(\xi_m^t, \xi_n^s) \sum_{V_j \in C_s} (1 - \mu_{rj}) \int_{V_j} S_n(y) \, dy \, M^j $$

### 2nd approximation approach

$$ (A_{far} M)_i \approx \sum_{|m| \le p} (\nabla \times S_m)(x_i) \sum_{C_s \notin \mathcal{N}(C_t)} \sum_{|n| \le p} k_1(\xi_m^t, \xi_n^s) \sum_{V_j \in C_s} (1 - \mu_{rj}) \int_{V_j} S_n(y) \, dy \, M^j $$

<table><thead><tr><th>1st approach</th><th>2nd approach</th></tr></thead><tbody><tr><td>k<sub>0</sub>(x, y) = <sup>1</sup>&frasl;<sub>4&pi;</sub> (3(<sup>x &minus; y</sup>&frasl;<sub>||x &minus; y||<sup>5</sup></sub> &otimes; (<sup>x &minus; y</sup>&frasl;<sub>||x &minus; y||<sup>3</sup></sub> <b>I</b><sub>3&times;3</sub>))</td><td>k<sub>1</sub>(x, y) = <sup>1</sup>&frasl;<sub>4&pi;</sub> (<sup>x &minus; y</sup>&frasl;<sub>||x &minus; y||<sup>3</sup></sub>)</td></tr><tr><td>K = [<sup>k<sub>0</sub>(ξ<sub>m</sub><sup>t</sup>, ξ<sub>n</sub><sup>s</sup>)</sup>&frasl;<sub>n,m</sub> ∈ ℝ<sup>3p<sup>3</sup>&times;3p<sup>3</sup></sup></td><td>K = [<sup>k<sub>1</sub>(ξ<sub>m</sub><sup>t</sup>, ξ<sub>n</sub><sup>s</sup>)</sup>&frasl;<sub>n,m</sub> ∈ ℝ<sup>3p<sup>3</sup>&times;3p<sup>3</sup></sup></td></tr><tr><td>3 inputs, 3 outputs</td><td>3 inputs, 1 output</td></tr><tr><td>More accurate</td><td>Faster + less memory required (M2L pass)</td></tr></tbody></table>
# Combining the interpolation-based FMM with the MMM

## Summary

$$A = \begin{pmatrix} [A_{xx}] & [A_{xy}] & [A_{xz}] \\ [A_{yx}] & [A_{yy}] & [A_{yz}] \\ [A_{zx}] & [A_{zy}] & [A_{zz}] \end{pmatrix} \in \mathbb{R}^{3N \times 3N} \qquad [A_{xx}] = \begin{pmatrix} A_{xx}^{11} & \dots & A_{xx}^{1N} \\ \vdots & \ddots & \vdots \\ A_{xx}^{N1} & \dots & A_{xx}^{NN} \end{pmatrix} \in \mathbb{R}^{N \times N}$$

## Simplified" representation of the matrix partitioning

<figure><img src="image_8.png" /></figure>
# Some numerical results

## Configuration of the experiments

### Experimental setup

* **Near-field computation**

* Fortran 90 implementation of the MMM (Laplace, Toulouse) [Oubaid 2014]

* **Far-field computation**

* `ScalFMM` C++ library: multi-dim, kernel-independent, interpolation support

* Acceleration: FFT (Uniform) [Blanchard 2017]

* Compression: low-rank $K \sim UV^T$ (Chebyshev) [Messner et al. 2012]

* **Plafrim**: experimental platform

<figure><img src="image_9.png" /><figcaption>(a) Antenna geometry ($1,000 < N < 15,000$)</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(b) U-shaped geometry ($15,000 < N$)</figcaption></figure>
# Some numerical results

## Accuracy: error vs. order p

(Antenna geometry)

<figure><img src="image_11.png" /></figure>

Relative 2-norm error $E_2$ vs. order p

$$ \mu_r = 3000, \text{ tree height} = 4 $$

Machine: plaform/bora 2x 18-core Cascade Lake Intel Xeon Skylake Gold 6240 @ 2.6 GHz RAM 192 GB

## Accuracy

* Relative 2-norm error $E_2$:

$$ E_2 := \frac{\|\mathbf{A}^{\text{FMM}}\mathbf{x} - \mathbf{A}\mathbf{x}\|_2}{\|\mathbf{A}\mathbf{x}\|_2}, \quad \mathbf{x} \in \mathbb{R}^{3N} $$

* $k_0$ more accurate than $k_1$

* Chebyshev interpolation more accurate than Uniform interpolation

* All errors stabilize around $10^{-6} \sim \text{error of the near-field computation}$
# Some numerical results

## Performance: elapsed time vs. number of elements *N* (sequential)

<figure><img src="image_12.png" /></figure>

### Elapsed time (s) vs. number of elements *N*

$\mu_r = 3000$, target accuracy = $10^{-3}$

Machine: plafrim/bora 2x 18-core Cascade Lake Intel
Xeon Skylake Gold 6240 @ 2.6 GHz RAM 192 GB

<figure><img src="image_13.png" /></figure>

### Elapsed time (s) and memory consumption (MB) for the 2 approaches on larger meshes

Uniform interpolation (FFT), $\mu_r = 3000$, order $p = 5$, Memory consumption = multipoles and local expansions

Machine: plafrim/bora 2x 18-core Cascade Lake Intel
Xeon Skylake Gold 6240 @ 2.6 GHz RAM 192 GB
# Some numerical results

## Performance: elapsed time vs. number of elements *N* (parallel)

### Parallel implementation of the FMM

► Task-based approach [Agullo et al. 2014] [Agullo et al. 2016] (via OpenMP)

<figure><img src="image_14.png" /><figcaption>Elapsed time (s) vs. number of threads (OpenMP) for the parallel task-based FMM algorithm</figcaption></figure>

Uniform interpolation (FFT), $\mu_r = 3000$, group size = 5 (granularity), order $p = 5$

Machine: plafrim/bora 2x 18-core Cascade Lake Intel Xeon Skylake Gold 6240 @ 2.6 GHz RAM 192 GB
# Conclusion

## Summary

* Development of an FMM-based matrix-vector product coupled with the MMM

* Focus on the far-field computation using an interpolation approach

* Emphasis on genericity and flexibility, allowing the algorithm to be adapted to two kernel functions ($k_0$ and $k_1$)

* Implementation using the ScaIFMM library (kernel-independent framework)

## Perspective and possible future work

* Scalar potential formulation (less unknowns)

* Comparison between the FMM and approaches based on H-matrices

* Coupling GMRES algorithm with the FMM-based matrix-vector product (requires a suitable preconditioning method)
<figure><img src="image_15.png" /></figure>

Agullo, Emmanuel, Berenger Bramas, Olivier Coulaud, Eric Darve, Matthias Messner, and Toru Takahashi (2016).

"Task-based FMM for heterogeneous architectures". In: *Concurrency and Computation: Practice and Experience* 28.9, pp. 2608-2629.

<figure><img src="image_16.png" /></figure>

Agullo, Emmanuel, Bérenger Bramas, Olivier Coulaud, Eric Darve, Matthias Messner, and Toru Takahashi (2014).

"Task-based FMM for multicore architectures". In: *SIAM Journal on Scientific Computing* 36.1, pp. C66-C93.

<figure><img src="image_17.png" /></figure>

Blanchard, Pierre (2017). "Fast hierarchical algorithms for the low-rank approximation of matrices, with applications to materials physics, geostatistics and data analysis". PhD thesis. Université de Bordeaux.

<figure><img src="image_18.png" /></figure>

Chadebec, Olivier, J-L Coulomb, and Fleur Janet (2006). "A review of magnetostatic moment method". In: *IEEE*

*Transactions on magnetics* 42.4, pp. 515-520.

<figure><img src="image_19.png" /></figure>

Fong, William and Eric Darve (2009). "The black-box fast multipole method". In: *Journal of Computational Physics*

228.23, pp. 8712-8725.

<figure><img src="image_20.png" /></figure>

Greengard, Leslie and Vladimir Rokhlin (1987). "A fast algorithm for particle simulations". In: *Journal of computational*

*physics* 73.2, pp. 325-348.

<figure><img src="image_21.png" /></figure>

Messner, Matthias, Bérenger Bramas, Olivier Coulaud, and Eric Darve (2012). "Optimized M2L kernels for the Chebyshev

interpolation based fast multipole method". In: *arXiv preprint arXiv:1210.7292*.

<figure><img src="image_22.png" /></figure>

Oubaid, Rania (2014). "Contribution à la modélisation du champ électromagnétique dans les dispositifs basses fréquences par la méthode des moments". PhD thesis.
# Appendices

## Near-field computation

$$ \forall i \in \{1, \dots, N\} \quad x_i \in \mathcal{C}_t, \quad (A_{\text{near}} \mathbf{M})_i = \mathbf{M}^i + \sum_{C_s \in \mathcal{N}(C_i)} \sum_{V_j \in C_s} (1 - \mu_{rj}) \int_{V_j} k_0(x_i, y) dy \mathbf{M}^j $$

* **Volume integral computation**

→ Gauss-Legendre quadrature rule ($n_g^3$ points)

* **Singularity [Chadebec et al. 2006]**

→ when $V_i$ interacts with itself

→ need a complex analytical expression

* **Adaptive strategy [Oubaid 2014]**

→ choice of the order $n_g$

→ targeted accuracy: $\sim 10^{-6}$

$n_g \downarrow$ as $\operatorname{dist}(V_i, V_j) \nearrow$

<figure><img src="image_23.png" /></figure>
# Appendices

## Cell width extension

$$ \mathcal{M}_n(\mathcal{C}_s) = \sum_{V_j \in \mathcal{C}_s} (1 - \mu_{rj}) \int_{V_j} S_n(y) \, dy \quad \mathbf{M}^j \quad |n| \le p \quad \forall \text{ cell } \mathcal{C}_s $$

<figure><img src="image_24.png" /><figcaption>Illustration of the cell width extension principle [Blanchard 2017]</figcaption></figure>