Improved Arithmetic Intensity in Preconditioned Krylov Subspace Method by Multiple Search Vectors
Please login to view abstract download link
Krylov subspace methods are widely used to solve linear system with large sparse matrix and its main operations are multiplication of sparse matrix to vector (SpMV) and preconditioning operation. SpMV operation has similar arithmetic intensity as BLAS2 GEMV operation and in the preconditioning phase of the additive Schwarz method also consists of BLAS2 memory-bound operation, e.g. triangular solver for forward/backward substitution implemented as TRSV. It is required to introduce multiple search vectors to perform SpMM operation (multiplciation of sparse matrix to several vectors) and also to perform higher arithmetic intensity in the preconditioning procedure. From view point of overall complexity of the iteration, even for case where arithmetic intensity is improved, it is important to introduce multiple search vectors by keeping dimension of generated Krylov subspace as same as one from the standard single search vector setting. Deflation method is attractive when the A-orthogonal projection onto the subspace spanned by Ritz vectors from previous Arnoldi process is replaced as source of multiple search vectors. However, if we start new search vector from the previous residual, generated vectors are not optimal. Enlarged Krylov subspace method introduces several search vectors based on domain decomposition, but total iteration cost is more than original one due to increased dimension of the Kyrlov subspace. GenEO preconditioner consists of A-orthogonal projector onto the coarse space and the hybrid type GenEO preconditioner drops the information of the coarse space during iteration. The preconditioner forces the invariant dimension of the Krylov subspace from the coarse solution to be one. However, A-orthogonal projector requires substantial costs, which are proportional to dimension of the GenEO coarse space. We utilize this coarse space for decomposition of the initial residual and generate both Krylov subspaces from the one in the coarse space and from its complement to have similar invariant dimension.
