Fast Algorithm For Solving Shifted Linear Systems

In scientific computing fields such as high-order implicit methods for solving timedependent partial differential equations,control theory,structural dynamics,and quantum chromodynamics(QCD),problems of solving largescale sparse shift linear systems will all be encountered.In numerical calculations,how to solve linear systems quickly and efficiently has become an important research direction.At present,the main method for solving shifted linear systems is the Krylov subspace method,because it has the advantages of less storage and calculation,and can use the shift invariance of the Krylov subspace to solve multiple linear systems at once.It has gradually become Research hotspots.The GMRES algorithm is a classic Krylov subspace method for solving largescale linear equations,and the Simpler GMRES algorithm(SGMRES)is an efficient variant implementation of the GMRES algorithm.The SGMRES algorithm converts the least squares problem of solving the upper Hessenberg matrix in the GMRES algorithm to solving the least squares problem of an upper triangular matrix.It not only reduces the amount of calculation,but also guarantees certain numerical stability.Therefore,the use of this algorithm variant to solve shifted linear systems has certain advantages.The research in this paper is based on the adaptive SGMRES-Sh algorithm(Ad-SGMRES-Sh),which is a stable variant of the SGMRES algorithm.Due to the limitation of computer storage and calculation,restarting technology is needed in actual calculations,but restarting technology may make the front and back subspaces lose the orthogonality,so the algorithm loses global optimality,resulting in slower or even slower convergence of the algorithm.Stagnation.Therefore,there are many strategies for improving the restarted SGMRES algorithm.Augmented method is one of them.Its main idea is to improve the convergence speed of the original algorithm by retaining the subspace information of the previous cycle.There are two types of commonly used augmentation strategies:one is to add the approximate feature vector corresponding to the internal feature value to the Krylov subspace when restarting? the other is to retain part of the correction vector generated in the previous loop.Therefore,in order to reduce the negative impact of restart,this article uses the augmented acceleration strategy based on the Ad-SGMRES-Sh algorithm,and proposes two variants of the Ad-SGMRES-Sh algorithm,one is to add at restart Part of the correction vector generated in the previous cycle is added to the Krylov approximation subspace,and the Ad-LSGMRES-Sh algorithm is proposed? the other is to use a double augmentation strategy,while adding part of the correction vector generated in the previous cycle and the harmonic Ritz vector to the Krylov approxima-tion In the subspace,the Ad-LSGMRESE-Sh algorithm is proposed.Finally,numerical experiments are used to verify the feasibility and effectiveness of these two algorithms.