La résolution de problèmes de diffraction d'ondes en régime harmonique par des méthodes intégrales de frontière conduit à des systèmes linéaires pleins dont le stockage et la résolution efficaces sont encore des sujets d'actualité malgré les avancées significatives apportées par les méthodes FMM (Fast Multipole Method) et H-matrix.
Cette thèse a pour objectif d'étudier un algorithme de compression matricielle encore peu utilisé dans ce contexte : la décomposition Quantized Tensor Train (QTT). Les matrices sont exprimées dans un format tensoriel, c'est-à-dire sous la forme d'un tableau multidimensionnel, et comprimées à l'aide d'une généralisation de la séparation des variables permettant un stockage parcimonieux et hiérarchique. Près de 2 à 3 ordres de grandeur de différence en mémoire peuvent être observés par rapport aux H-matrices et dans certains cas le stockage peut être estimé en O(N) ou en O(log N) (N étant le nombre de degrés de liberté).
À travers des expériences numériques 2D et 3D en acoustique et en électromagnétisme, nous mettons en lumière les avantages et les limites de cette méthode. Son évaluation nous permet de proposer des techniques d'utilisation de QTT au service de l'accélération des solveurs H-matrix et FMM. En particulier nous montrons que, grâce à l'algorithme QTT, il est possible de construire des préconditionneurs efficaces et originaux pour traiter des problèmes de diffraction par des objets non canoniques telles des surfaces ouvertes exfoliées, rugueuses ou résonnantes. |
Solution of wave scattering problems in the harmonic regime by boundary integral methods leads to dense linear systems whose efficient storage and resolution are still a topic of interest despite the significant inroads brought by the FMM (Fast Multipole Method) and H-matrix.
This thesis aims to study a matrix compression algorithm that is still not widely used in this context: the Quantized Tensor Train (QTT) decomposition. The matrices are expressed in a tensor format, i.e. as a multidimensional array, and compressed using a generalisation of the separation of variables allowing parsimonious and hierarchical storage. Nearly 2 to 3 orders of magnitude difference in memory can be observed compared to H-matrices and in some cases the storage can be estimated in O(N) or O(log N) (N being the number of degrees of freedom).
Through 2D and 3D numerical experiments in acoustics and electromagnetism, we highlight the advantages and limitations of this method. Its evaluation allows us to propose techniques for using QTT to accelerate the solvers H-matrix and FMM. In particular, we show that, with the help of the QTT algorithm, it is possible to build efficient and original preconditioners to deal with scattering problems by non-canonical objects such as exfoliated, rough or resonant open surfaces. |