Keywords: domain decomposition, FETI, Total FETI, TFETI, conjugate gradient, deflated conjugate gradient, DCG, FLLOP, PETSc, parallel direct solver, pseudoinverse, natural coarse space matrix, coarse problem.

Parallelization of the solution of a system of linear equations can be implemented mostly using the single program multiple data technique: for data distribution of the matrix and vector portions among the processing units. This allows algorithms to be almost the same for sequential and parallel case; only the data structure implementation differs. In domain decomposition (DD), data distribution of the primal matrices can be quite straightforward as every subblock reflects a subdomain. The matrices then possess a well structured block-diagonal layout and can be implemented using a block-diagonal matrix composite type where sub-blocks are ordinary sequential matrices. This paper deals with the applications of DD techniques for the iterative solution of the systems of linear equations using the conjugate gradient method (CG) and their comparison. The resulting problem based on the DD method can be solved by using the CG with primal variables or can be transformed into a dual problem with Lagrange multipliers: the class of these methods is called FETI (finite element tearing and interconnecting). Grouping of the nodes based on DD can be even used to generate the subspace for the deflated conjugate gradient method (DCG) applied to the undecomposed problem.

Matrices and vectors for numerical experiments were obtained from a regular decomposition and discretization of a model problem of an elastic cube. To illustrate the efficiency of various methods we used a discretization of the cube into 4,096,000 elements, the number of primal variables was approx. 17,000,000. The strong parallel scalability for all methods is demonstrated for 512, 1,000, 4,096 and 8,000 cores.

The results of the comparison are maybe surprising. For our model static cube benchmark, the best solution times are reached when the CG is applied to the dual TFETI method, but some not negligible preprocessing time is always needed. The best total times are reached by when the CG is applied to the un-decomposed primal problem distributed into horizontal blocks with no preprocessing phase. For dynamic time-dependent problems the situation is then different, the best choice is TFETI as we need one preprocessing and thousands of runs of the solver.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £40 +P&P)