Diagonalisation Hermitienne Rapide avec Précision Quasi-Optimale

Les algorithmes pour des tâches numériques en précision finie cherchent simultanément à minimiser le nombre d'opérations en virgule flottante effectuées, ainsi que le nombre de bits de précision requis par chaque opération en virgule flottante. Cet article présente un algorithme pour la diagonalisation hermitienne nécessitant uniquement (1/) +O ( (n) + (1/) ) bits de précision où n est la taille de la matrice d'entrée et est l'erreur cible. De plus, il s'exécute dans un temps proche de celui de la multiplication matricielle. Dans le cadre général, la première analyse complète de la stabilité d'un algorithme en temps proche de la multiplication matricielle pour la diagonalisation est celle de Banks et al. BGVKS20. Ils exposent un algorithme pour diagonaliser une matrice arbitraire jusqu'à une erreur arrière en utilisant seulement O (⁴ (n/) (n) ) bits de précision. Ce travail se concentre sur le cadre hermitien, où nous déterminons une limite considérablement améliorée sur le nombre de bits nécessaires. En particulier, le résultat est proche de fournir une limite pratique. Le nombre exact de bits dépend de l'implémentation spécifique de la multiplication matricielle et de la décomposition QR que l'on souhaite utiliser, mais si l'on utilise des implémentations en O (n³) adaptées, alors pour =10^-15, n=4000, nous montrons que 92 bits de précision suffisent (et 59 sont nécessaires). En comparaison, les mêmes paramètres dans BGVKS20 ne montrent même pas que 682, 916, 525, 000 bits suffisent.