Support graph preconditioning for elliptic finite element problems

A relatively new preconditioning technique called support graph preconditioning has many merits over the traditional incomplete factorization based methods. A major limitation of this technique is that it is applicable to symmetric diagonally dominant matrices only. This work presents a technique that can be used to transform the symmetric positive definite matrices arising from elliptic finite element problems into symmetric diagonally dominant M-matrices. The basic idea is to approximate the element gradient matrix by taking the gradients along chosen edges, whose unit vectors form a new coordinate system. For Lagrangian elements, the rows of the element gradient matrix in this new coordinate system are scaled edge vectors, thus a diagonally dominant symmetric semidefinite M-matrix can be generated to approximate the element stiffness matrix. Depending on the element type, one or more such coordinate systems are required to obtain a global nonsingular M-matrix. Since such approximation takes place at the element level, the degradation in the quality of the preconditioner is only a small constant factor independent of the size of the problem. This technique of element coordinate transformations applies to a variety of first order Lagrangian elements. Combination of this technique and other techniques enables us to construct an M-matrix preconditioner for a wide range of second order elliptic problems even with higher order elements. Another contribution of this work is the proposal of a new variant of Vaidya?s support graph preconditioning technique called modified domain partitioned support graph preconditioners. Numerical experiments are conducted for various second order elliptic finite element problems, along with performance comparison to the incomplete factorization based preconditioners. Results show that these support graph preconditioners are superior when solving ill-conditioned problems. In addition, the domain partition feature provides inherent parallelism, and initial experiments show a good potential of parallelization and scalability of these preconditioners.