Computational & Technology Resources
an online resource for computational,
engineering & technology publications
PROCEEDINGS OF THE SECOND INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED, GRID AND CLOUD COMPUTING FOR ENGINEERING
Edited by: P. Iványi and B.H.V. Topping
Parallel Algebraic Domain Decomposition Solver for the Solution of Augmented Systems
E. Agullo1, L. Giraud1, A. Guermouche1, A. Haidar2 and J. Roman1
1INRIA Bordeaux Sud-Ouest, HiePACS Project, INRIA-CERFACS Joint Laboratory on High Performance Computing, France
E. Agullo, L. Giraud, A. Guermouche, A. Haidar, J. Roman, "Parallel Algebraic Domain Decomposition Solver for the Solution of Augmented Systems", in P. Iványi, B.H.V. Topping, (Editors), "Proceedings of the Second International Conference on Parallel, Distributed, Grid and Cloud Computing for Engineering", Civil-Comp Press, Stirlingshire, UK, Paper 40, 2011. doi:10.4203/ccp.95.40
Keywords: augmented-indefinite linear systems, sparse linear systems, direct-iterative hybrid methods, high-performance computing.
Our numerical technique is based on an algebraic non-overlapping domain decomposition technique that only exploits the graph of the sparse matrix. This approach to high-performance, scalable solution of large sparse linear systems in parallel scientific computing is to combine direct and iterative methods. Such a hybrid approach exploits the advantages of both direct and iterative methods. The iterative component allows us to use a small amount of memory and provides a natural approach to parallelization. The direct part provides favourable numerical properties. The graph of the sparse matrix is split into sub-graphs and a condensed linear system, namely the Schur complement system, is solved iteratively for the unknowns associated with the interface between the sub-graphs; a sparse direct solver is used for the variables associated with the internal parts of the sub-graphs. For augmented systems a special attention should be paid to ensure the non singularity of the local sub-problems so that the Schur complement is defined. For augmented systems, where the 2,2 block is small compared to the 1,1 block, we design a special technique that enforces the Lagrange multiplier variables (associated with the 2,2 block) to be within the interface unknowns. This technique has two main advantages. First, it ensures that none of the local sub-systems is structurally singular and for symmetric positive definite 1,1 block, it even ensures that those sub-matrices are also symmetric positive definite. This latter property enables us to use a Cholesky factorization for the internal sub-problems which reduces the computational complexity (in terms of floating point operation counts and memory consumption) compared to a more general LU decomposition. In this paper, we describe how the graph partitioning problem is formulated to comply with the above mentioned constraints. We report numerical and parallel performance of the scheme on large matrices arsing from the finite element discretization of linear elasticity in structural mechanic problems. For those problems some boundary conditions are modeled through the use of Lagrange multipliers.
purchase the full-text of this paper (price £20)