Rank Revealing QR Methods for Sparse Block Low Rank Solvers

Esragul Korkmaz (1, 2) , Mathieu Faverge (1, 2) , Grégoire Pichon (1, 2) , Pierre Ramet (1, 2)

1 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Solving linear equations of type Ax=b for large sparse systems frequently emerges in science and engineering applications, which creates 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. Therefore, when solving these linear equations, memory reduction becomes as important as time reduction. For this purpose, compression methods of dense blocks appearing inside sparse matrix solvers have been introduced to reduce the memory consumption, as well as the time to solution. While looking for the lowest possible compression rank, Singular Value Decomposition (SVD) gives the best result. It is however too costly as the whole factorization is computed to find the resulting rank. In this respect, rank revealing QR decomposition variants are less costly, but 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 classical QR decomposition with column pivoting, blocking versions with randomization are suggested as an alternative solution to find the pivots. In these randomized variants, the matrix A is projected on a much lower dimensional matrix by using an independent and identically distributed 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 and shown to be more efficient for larger matrix sizes. Thanks to these methods, closer results to SVD can be obtained and the cost of compression can be reduced. In this presentation, a comparison of all these methods in terms of complexity, numerical stability and performance will be presented.

Mots clés: sparse direct solver; low-rank compression; randomized methods; SVD; rank revealing QR

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Esragul Korkmaz, Mathieu Faverge, Grégoire Pichon, Pierre Ramet. Rank Revealing QR Methods for Sparse Block Low Rank Solvers. Sparse Days 2019, Jul 2019, Toulouse, France. ⟨hal-02326070⟩