Data Distribution and Communication Schemes for Solving Sparse Systems of Linear Equations from FE Applications by Parallel CG Methods

摘要

For the solution of discretized ordinary or partial differential equations it is necessary to solve systems of equations with coefficient matrices of different sparsity pattern, depending on the discretization method; using the finite element (FE) method results in largely unstructured systems of equations. Iterative solvers for equation systems mainly consist of matrix-vector products and vector-vector operations. A frequently used iterative solver is the method of conjugate gradients (CG) with different preconditioners. For parallelizing this method on a multiprocessor system with distributed memory, in particular the data distribution and the communication scheme depending on the used data structure for sparse matrices are of greatest importance for the efficient execution. These schemes can be determined before the execution of the solver by preprocessing the symbolic structure of the sparse matrix and can be exploited in each iteration. In this report, data distribution and communication schemes are presented which are based on the analysis of the column indices of the non-zero matrix elements. Performance tests of the developed parallel CG algorithms have been carried out on the distributed memory system INTEL iPSC/860 of the Research Centre Jülich with sparse matrices from FE models. These methods have performed well for matrices of very different sparsity pattern.