Un algorithme basé sur les blocs de Householder pour la décomposition QR des matrices hiérarchiques

.Les matrices hiérarchiques sont des matrices denses mais peu denses en données, qui utilisent des factorizations de rang faible de sous-matrices appropriées pour réduire l'espace de stockage et le coût computationnel à une complexité linéaire-polylogarithmique. Dans cet article, nous proposons une nouvelle approche pour calculer efficacement les factorizations QR au format de matrices hiérarchiques, basée sur des transformations de Householder par blocs. Pour éviter des rangs inutilement élevés dans les facteurs résultants et pour augmenter la vitesse et la précision, l'algorithme suit de près pour quels résultats intermédiaires des factorizations de rang faible sont disponibles. Nous utilisons également un schéma de stockage spécial pour le réflecteur de Householder par blocs afin de réduire encore les coûts computationnels et de stockage. Des tests numériques pour des matrices élémentaires aux limites laplaciennes de deux et trois dimensions, différentes matrices de noyaux de fonctions de base radiales, ainsi que des matrices de structures matricielles hiérarchiques typiques mais remplies d'entrées aléatoires illustrent les performances du nouvel algorithme par rapport à d'autres algorithmes QR pour les matrices hiérarchiques de la littérature.Mots-clésFacteurisation QRblock Householdermatrices hiérarchiquescodes MSC15A2365F0565F2565Y20