Résumé: We are interested here in solving the Helmholtz equation using a
second kind integral formulation. We are lead to compute very
expensive matrix vector products when applying an iterative method
to compute the solution. V. Rokhlin first introduced the fast
multipole method in 3D. Its purpose is to reduce this complexity to
$n^{\frac{3}{2}}$ where $n$ is the number of points on the
interface. Using those ideas one can as well construct a multistep
algorithm, where one gathers the points on the surface of the
scatterer in a recursive way, building a tree. With such an
algorithm, we believe that a fairly simple and efficient solver can
be constructed with an asymptotic complexity of $n \log^2 n$.
We here give a precise construction of that algorithm and all the
necessary theorems to estimate the error and the complexity of the
computation.

On s'intéresse ici à la résolution de
l'équation de Helmholtz par une formulation intégrale de deuxième
genre. On est conduit au calcul de produits matrice-vecteur très
coÃteux, lorsqu'on utilise une méthode itérative d'inversion de
matrice. V. Rokhlin a été le premier à présenter une méthode
multipÂle rapide en 3D. Son but est de réduire la complexité à
$n^{\frac{3}{2}}$ oË $n$ est le nombre de points sur l'interface. En
utilisant ces idées on peut construire un algorithme multistep, dans
lequel les points sur la surface sont regroupés en paquets de manière
récursive. On aboutit alors à la création d'un arbre des points de
la surface. Avec un tel algorithme, on est en mesure de construire
un solveur simple et efficace avec une complexité asymptotique en $n
\log^2 n$.
On donne ici la construction précise de cet algorithme et tous les
théorèmes nécessaires à l'estimation de l'erreur et de la complexité
CPU du calcul.

Mots Clés: Helmholtz 3D; Iterative methods; Approximation of kernel; Multipole expansion