Parallel algebraic domain decomposition solver for the solution of augmented systems

We consider the parallel iterative solution of indefinite linear systems given as augmented systems where the $(1,1)$ block is symmetric positive definite and the $(2,2)$ block is zero. 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 way for parallelization. The direct part provides favorable 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 in 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 term 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