Report
Reaching the Quality of SVD for Low-Rank Compression Through QR Variants ; Atteindre la qualité d’une SVD avec une compression de rang faible pour différentes variantes de la factorisation QR
| العنوان: | Reaching the Quality of SVD for Low-Rank Compression Through QR Variants ; Atteindre la qualité d’une SVD avec une compression de rang faible pour différentes variantes de la factorisation QR |
|---|---|
| المؤلفون: | Korkmaz, Esragul, Faverge, Mathieu, Pichon, Grégoire, Ramet, Pierre |
| المساهمون: | High-End Parallel Algorithms for Challenging Numerical Simulations (HiePACS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Inria Bordeaux - Sud Ouest, ANR-18-CE46-0006,SaSHiMi,Solveur linéaire creux exploitant des matrices hierarchiques(2018) |
| المصدر: | https://inria.hal.science/hal-03718312 ; [Research Report] RR-9476, Inria Bordeaux - Sud Ouest. 2022, pp.43. |
| بيانات النشر: | HAL CCSD |
| سنة النشر: | 2022 |
| المجموعة: | HAL Lyon 1 (University Claude Bernard Lyon 1) |
| مصطلحات موضوعية: | Low-rank compression, randomization, Compression de rang faible, randomisation, [INFO]Computer Science [cs] |
| الوصف: | Solving linear equations of type $Ax=b$ for large sparse systems frequently emerges in science/engineering applications, which is the main bottleneck. In spite that the direct methods are costly in time and memory consumption, they are still the most robust way to solve these systems. Nowadays, increasing the amount of computational units for the supercomputers became trendy, while the memory available per core is reduced. Thus, when solving these linear equations, memory reduction becomes as important as time reduction. For this purpose, compression methods are introduced within sparse solvers to reduce both the memory and time consumption. In this respect, Singular Value Decomposition (SVD) is used to reach the smallest possible rank, but it is too costly in practice. Rank revealing QR decomposition variants are used as faster alternatives, which can introduce larger ranks. Among these variants, column pivoting or matrix rotation can be applied on the matrix $A$, such that the most important information in the matrix is gathered to the leftmost columns and the remaining unnecessary information can be omitted. For reducing the communication cost of the QR decomposition with column pivoting, blocking versions with randomization are suggested as an alternative to find the pivots. In these randomized variants, the matrix $A$ is projected on a lower dimensional matrix by using an i.i.d. Gaussian matrix so that the pivoting/rotational matrix can be computed on the lower dimensional matrix. In addition, to avoid unnecessary updates of the trailing matrix at each iteration, a truncated randomized method is suggested to be more efficient for larger matrix sizes. Thanks to these methods, closer results to SVD are obtained with reduced compression cost. In this report, we compare all these methods in terms of complexity, numerical stability, obtained rank, performance and accuracy. ; La résolution d'équations linéaires de type $Ax=b$ pour de grands systèmes creux apparaît fréquemment dans les applications scientifiques ... |
| نوع الوثيقة: | report |
| اللغة: | English |
| Relation: | Report N°: RR-9476; hal-03718312; https://inria.hal.science/hal-03718312; https://inria.hal.science/hal-03718312v4/document; https://inria.hal.science/hal-03718312v4/file/RR-9476.pdf |
| الاتاحة: | https://inria.hal.science/hal-03718312 https://inria.hal.science/hal-03718312v4/document https://inria.hal.science/hal-03718312v4/file/RR-9476.pdf |
| Rights: | info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.865419CE |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |