Low-rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices

We consider the problem of choosing low-rank factorizations in data sparse matrix approximations for preconditioning large scale symmetric positive definite matrices. These approximations are memory efficient schemes that rely on hierarchical matrix partitioning andcompression of certain sub-blocks of the matrix. Typically, these matrix approximations can be constructed very fast, and their matrix product can be applied rapidly as well. The common practice is to express the compressed sub-blocks by low-rank factorizations, and the main contribution of this work is the numerical and spectral analysis of SPD preconditioning schemes represented by 2×2 block matrices, whose off-diagonal sub-blocks are low-rank approximations of the original matrix off-diagonal sub-blocks. We propose an optimal choice of low-rank approximations which minimizes the condition number of the preconditioned system, and demonstrate that the analysis can be applied to the class of hierarchically off-diagonal low-rank matrix approximations. Spectral estimates that take into account the error propagation through levels of the hierarchy which quantify the impact of the choice of low-rank compression on the global condition number are provided. The numerical results indicate that the properties of the preconditioning scheme using proper low-rank compression are superior to employing standard choices for low-rank compression. A major goal of this work is to provide an insight into how proper reweighted prior to low-rank compression influences the condition number for a simple case, which would lead to an extended analysis for more general and more efficient hierarchical matrix approximation techniques.Nous étudions un préconditionnement “data sparse” pour matrices symétriques définies positives provenant de problèmes aux limites elliptiques du second ordre. Pour des problèmes de grandes tailles, des conditions aux limites quasi-singulières ou des géométries complexes, les matrices de discrétisation associées sont très mal conditionnées. Le recours à des méthodes multi-niveaux sont souvent une nécessité pour obtenir une solution efficace. Nous proposons un nouveau préconditionneur hiérarchique qui, dans le cas deux-niveaux, minimise le conditionnement du système préconditionné. Dans le cas multi-niveaux le préconditionneur tente de conserver cette propriété qui n’est plus prouvée ; en revanche nous établissons que les valeurs propres extrémales sont regroupées dans un intervalle autour de 1. Finalement, à travers des expérimentations numériques, nous illustrons l’efficacité du nouveau schéma proposé qui surpasse les techniques plus classiques basées sur une SVD régulière pour approximer les blocs hors-diagonaux ou une SVD filtrée