Truncated QR factorization with pivoting in mixed precision

Factorisation QR avec pivotage et troncature en précision mixte

Alfredo Buttari (1) , Théo Mary (2) , André Pacteau

1 IRIT-APO - Algorithmes Parallèles et Optimisation
2 PEQUAN - Performance et Qualité des Algorithmes Numériques

Low-rank approximations are widely used to reduce the memory footprint and operational complexity of numerous linear algebra algorithms in scientific computing and data analysis. In some of our recent work we have demonstrated that low-rank approximations can be stored using multiple arithmetic precisions to further reduce the storage and execution time. In this work we present a method that can produce this mixed-precision representation directly; this relies on a mixed-precision truncated rank-revealing QR (RRQR) factorization with pivoting. We present a floating-point error analysis and provide bounds on the error of the approximation demonstrating that the use of multiple precisions does not alter the overall accuracy. Finally, we present experimental results showing the execution time reduction for the cases where either classical or randomized pivoting are used.

Les approximations de rang faible sont couramment utilisées pour réduire la consommation de mémoire et la complexité calculatoire de nombreux algorithmes d’algèbre linéaire en calcul scientifique et analyse des données. Dans nos travaux récents, nous avons démontré que les approximations de rang faible peuvent etre stockées en utilisant de multiples précisions arithmétiques pour réduire d’avantage la mémoire et le temps d’exécution. Dans ce document, nous présentons une nouvelle méthode qui produit directement ces représentations; elle repose sur une factorisation QR en precision mixte tronquée et avec pivotage. Nous présentons une analyse des erreurs d’arrondi en virgule flottante ainsi que des bornes pour l’erreur d’approximation montrant que l’utilisation de plusieurs précisions ne dégrade pas la qualité de la solution finale. Finalement, nous présentons des résultats expérimentaux montrant la réduction du temps d’exécution obtenue avec les méthodes proposées.

Mots clés: Mixed-precision algorithms; QR factorization; low-rank approximations

Domaines: Analyse numérique [cs.NA]; Arithmétique des ordinateurs; Logiciel mathématique [cs.MS]

Alfredo Buttari, Théo Mary, André Pacteau. Truncated QR factorization with pivoting in mixed precision. 2024. ⟨hal-04490215⟩