ON SOME VARIANTS OF DOMAIN DECOMPOSITION METHODS
DOI:
https://doi.org/10.14529/cmse140201Keywords:
domain decomposition methods, matrix graphs, parallel algorithms, grid equations, sparse linear algebraic systemsAbstract
The paper considers the algorithms for solving large sparse SLAEs arising from grid approximations of boundary value problems. The SLAEs and algorithms are not limited in a sense of number of unknowns, computational nodes, processors and/or cores. This problem is reduced to a distributed variant of algebraic 3D-domain decomposition, in which no excessive load of the root process is present, i.e. all MPI-processes, each of which corresponds to its own subdomain, are almost equal. The computational process consists of two main stages. The first stage is the automatic decomposition, based on the analysis of the matrix portrait and the formation of large-block representation of the original SLAE. The second stage implements a Krylov subspace iterative process with FGMRes (flexible generalized minimal residual method) using either exact or approximate inverse of diagonal blocks as a preconditioner. The methods described are implemented as a part of Krylov, a library of algebraic solvers. The paper presents some features of current parallel implementation and estimates of resource usage. Efficiency of the developed algorithms is illustrated by solving several typical model problems with different parameters and in different configurations of multiprocessor computer systems.
References
Domain Decomposition Methods. URL: http://ddm.org (accessed: 14.03.2012)
22nd International Conference on Domain Decomposition Methods (DD22). URL: http://dd22.ics.usi.ch/ (accessed: 31.11.2013)
Intel (R) Math Kernel Library from Intel. URL: http://software.intel.com/en-us/articles/intel-mkl/ (accessed: 08.04.2014)
Il’in V.P. Metody i tekhnologii konechnykh elementov [Methods and technologies of finite elements]. Novosibirsk, ICM&MG SBRAS Publishing, 2007.
Pissanetski S. Tekhnologiya razrezhennykh matrits [Sparse matrix technology]. Moscow, Mir Publishing, 1988.
Bramble J.H, Pasciak J., Wang J., Xu J. Convergence estimates for product iterative methods with applications to domain decomposition // Mathematics of Computation. 1991. Vol. 57, No. 195. P. 1-21.
Berzh K. Teoriya grafov i eye primeneniya [Graph theory and its applications]. Moscow: Foreign Literature Publishing, 1962.
Saad Y. Iterative Methods for Sparse Linear Systems, Second Edition / SIAM, 2003. 528 p.
NKS-30T cluster. URL: http://www2.sscc.ru/HKC-30T/HKC-30T.htm (accessed: 12.02.2013).
Andreeva M.Yu. , Il’in V.P., Itskovich E.A. Two solvers for nonsymmetric SLAE Bulletin NCC, Numerical Analysis¿ series. 2003. Iss. 12. P. 1–16.
Butyugin D.S., Ilin V.P., Perevozkin D.V. Metody parallelnogo resheniya SLAU na sistemakh s raspredelennoy pamyatju v biblioteke Krylov [Parallel SLAE solution methods for distributed memory systems in Krylov library] Vestnik Yuzho-Uralskogo gosudarstvennogo universiteta. Seriya "Vychislitelnaya matematika i informatika"[Bulletin of South Ural State University. Series: Computational Mathematics and Informatics]. 2012. No. 47(306). P. 5-19.
