On coarse grid correction methods in Krylov subspaces (Q1662016)

The authors consider the numerical solution of large, sparse, and ill-conditioned systems of linear algebraic equations (SLAEs) originated from a boundary value problem with Dirichlet boundary conditions for a convection-diffusion equation based on a finite volume method of second order derived by the second author [J. Math. Sci., New York 224, No. 6, 900--910 (2017; Zbl 1373.65027); translation from Zap. Nauchn. Semin. POMI 453, 131--147 (2016)]. They emphasize that the method can be also applied to SLAEs arising from finite element approximations with sparse coefficient matrices. In the present paper, the authors propose an algorithm of coarse grid correction in two-level Krylov subspace processes with the aim to accelerate iterative domain decomposition methods (DDMs) with parallelization applied to the above mentioned problem. The two-level method consists of two processes, an outer process of block iterations over subdomains and an inner one for the synchronous solution of the relative small linear subsystems (SMLs) in the subdomains. Each of the SMLs is solved in an own multi-core processor using multithreaded computation on a shared memory. The inner Krylov iterations are traditionally carried out using an incomplete triangular factorization for preconditioning. That results in difficulties in the parallelization which is overcome by the proposed coarse-grid correction as a preconditioning method for the Krylov iterations with slow data exchanges. Applying the DDM, three types of basis functions are defined in the subdomains: the zeroth-order (so-called shelves), the second-order (caps), and the third-order basis functions. An approximate solution \(\vec{u}^n\) of the linear system is refined by the basis functions and the corrected approximate solution \(\vec{\tilde{u}}^n\) is calculated by minimizing the residual norm using the least squares method (LSM). The authors outline that also the singular value decomposition can be used instead of the LSM. The authors continue with the description of the choice of the initial vectors and the outer iteration with restarts. Every restart approximation is refined by a linear combination of the previous iterations. The paper is finished by numerical experiments for the above mentioned boundary value problem. Various number of nodes, of subdomains, and restart parameters are used for the solution of the corresponding SLAEs for moderate dimensions.