A Blockwise Algorithm for Parallel Incomplete Cholesky Factorization

Pascal Hénon 1 Pierre Ramet 1, 2 Jean Roman 1, 2
1 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : Solving large sparse linear systems by iterative methods has often been quite unsatisfactory when dealing with pratical "industrial" problems. The main difficulty encountered by such methods is their lack of robustness and, generally, the unpredictability and unconsistency of their performance over a wide sample of different problems; certain methods work quite well for certain types of problems but can fail completely on other problems. Over the past few years, direct methods have made significant progress thanks to either the combinatorial analysis of the Gaussian elimination process and the parallel algorithmic of blockwise solvers optimized for modern parallel supercomputers. Its is now possible to solve practical three-dimensional problems in the order of several millions of equations in a very powerful way with the direct solvers that efficiently use the superscalar effects of modern processors. However, direct methods may fail to solve very large three-dimensional problems, due to the large amount of memory needed for these cases. In our work, we consider an approach which, we hope, will bridge the gap between the two classes of methods. The goal is to provide a method which exploits the parallel blockwise algorithmic used in the framework of the high performance sparse direct solvers for developping robust parallel incomplete factorization based preconditioners for iterative solvers. The idea is then to define an adaptive blockwise incomplete factorization that is much more accurate (and numerically more robust) than the scalar incomplete factorizations commonly used to precondition iterative solvers. Our approach consists in computing symbolically the block structure of the factors that would have been obtained with a complete factorization, and then deciding to drop off some blocks of this structure according to relevant criterions. Such incomplete factorization can take advantage of the latest breakthroughts in sparse direct methods and therefore be very competitive in CPU time while avoiding the memory limitation encountered by direct methods. By this way, we expect to be able to solve systems in the order of hundred millions of unknowns.
keyword : Sparse
Type de document :
Communication dans un congrès
PMAA'04, 2004, Marseille, France. 2004
Liste complète des métadonnées

Contributeur : Pierre Ramet <>
Soumis le : jeudi 11 décembre 2008 - 19:34:26
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12


  • HAL Id : inria-00346616, version 1



Pascal Hénon, Pierre Ramet, Jean Roman. A Blockwise Algorithm for Parallel Incomplete Cholesky Factorization. PMAA'04, 2004, Marseille, France. 2004. 〈inria-00346616〉



Consultations de la notice