Bruno Carpentieri : April 23, 2002

Sparse preconditioners for dense complex linear systems in electromagnetic applications

Bruno CARPENTIERI
Tuesday April 23, 10h00 at CERFACS

 

Jury

• G. Meurant (Rapporteur)
• Y. Saad (Rapporteur)
• G. Alleon (Examinateur)
• M. Dayde (Examinateur)
• I. S. Duff (Examinateur)
• L. Giraud (Examinateur)
• S. Piperno (Examinateur)
  
  

Résumé

Dans cette these, nous etudions des preconditionneurs creux par inverse approche pour la resolution de systemes lineaires denses issus d'applications en electromagnetisme en formulation integrale.

L'objectif de ce travail etait le developpement de preconditionneurs robustes et paralleles pouvant etre integres ulterieurement dans des codes de simulation capables de traiter des geometries industrielles de tres grandes tailles.

Dans un premier temps, nous avons realise une etude comparative des divers preconditionneurs initialement developpes en algebre lineaire creuse en les adaptant au traitement de matrices denses. En particulier, nous avons propose une strategie efficace permettant de definir a priori la structure creuse d'un preconditionneur base sur un inverse approche minimisant la norme de Frobenius.

Cette approhe a ete implante par un autre doctorant dans un code parallele qui exploite une methode ``fast multipole'' pour le calcul de l'operation produit matrice-vecteur dans les methodes de Krylov. Ce code nous a permis d'evaluer l'evolutivite de notre preconditionneur lors de la resolution de systemes lineaires de taille croissante et d'en caracteriser les limitations. Afin de repousser ces limitations, nous avons proposer un schema numerique base sur des iterations embo{i}tees qui nous a permis d'ameliorer notablement la robustesse de notre preconditionneur sur des problemes de grande taille. Cette technique nous a permis de reduire les coups de calcul ainsi que de pouvoir traiter des geometries complexes telle que celle d'un avion avec plus d'un million de degres de liberte.

Enfin, nous avons egalement realise une etude preliminaire sur des preconditionneurs deux niveaux spectraux qui exploitent des proprietes spectrales du systeme preconditionne.

Abstract

In this work, we investigate the use of sparse approximate inverse preconditioners for the solution of large dense complex linear system arising from integral equations in electromagnetism applications.

The goal of this study is the development of robust and parallelizable preconditioners that can easily be integrated in simulation codes able to treat large configurations. We first adapt to the dense situation the preconditioners initialy developed for sparse linear systems. We compare their respective numerical behaviours and propose a robust pattern selection strategy for Frobenius-norm minimization preconditioners.

Our approach has been implemented by another PhD student in a large parallel code that exploits a fast multipole calculation for the matrix vector product in the Krylov iterations. This enables us to study the numerical scalability of our preconditioner on large academic and industrial test problems in order to identify its limitations. To remove these limitations we propose an embedded scheme. This inner-outer technique enables to significantly reduce the computational cost of the simulation and improve the robustness of the preconditioner. In particular, we were able to solve an linear system with more than a million unknowns arising from a simulation on a real aircraft. That solution was out of reach with our initial technique.

Finally we perform a preliminary study on spectral two-level preconditioner to enhance the robustness of our preconditioner. This numerical technique exploits spectral information of the preconditioned systems to build a low rank-update of the preconditioner.