Multiplication rapide adaptative de ℋ²-matrices

Les matrices hiérarchiques approchent une matrice donnée par une décomposition en sous-matrices de faible rang qui peuvent être traitées efficacement sous forme factorisée. Les H²-matrices affinent cette représentation en suivant les idées des méthodes multipolaires rapides afin d'atteindre une complexité linéaire, c'est-à-dire optimale, pour une variété d'algorithmes importants. La multiplication de matrices, un élément clé de nombreux algorithmes numériques plus avancés, a été un défi : les seuls algorithmes connus à ce jour en temps linéaire nécessitent soit la structure très spéciale des HSS-matrices, soit la connaissance préalable d'une base appropriée pour toutes les sous-matrices. Dans cet article, un nouvel algorithme relativement général pour multiplier des H²-matrices avec des bases construites de manière adaptive en complexité linéaire est présenté. L'algorithme se compose de deux phases : d'abord, une représentation intermédiaire avec une structure de bloc généralisée est construite, puis cette représentation est recompressée afin de correspondre à la structure prescrite par l'application. La complexité et la précision sont analysées et des expériences numériques indiquent que le nouvel algorithme peut en effet être significativement plus rapide que les tentatives précédentes.