Research On New Krylov Subspace Algorithm And Its Application

Solving the large-scale sparse linear system is deeply involved in various scientific and engineering fields, such as QCD, fluid mechanics, full waveform inversion, computational electromagnetics, reservoir modeling and so on. With the rapid development and application of science and technology, the requirements to the speed and accuracy become more and more important. The numerical simulation ability and storage performance continue to be improved, but so far there is not a common and efficient approach for various forms of linear systems. Therefore, how to solve one or a series of systems of linear equations efficiently and time-saving has become one of focuses in modern scientific computing. Thus, it needs that we endeavor to pursue and explore stabilized and more efficient iterative algorithms. This thesis aims at improving and constructing Krylov subspace method of high performance for solving the series of systems in depth, especially linear systems with multiple righthand sides or shifts. The main contents are as follows:1. This study is mainly focused on iterative solutions to the shifted linear system. For solving such system efficiently, we explore the shifted QMRBiCGstab method and the shifted QMRBiCGstab2 method, which is derived by extending BiCGstab method. The new algorithm can mitigate the irregular convergence behavior of the shifted BiCGstab method and exhibit rather smooth convergence behavior. In addition, the new algorithms take advantage of the special structure, so that the number of matrix-vector products and the number of inner products is the same as for a single linear system. Numerical experiments demonstrate the effectiveness of these methods.2. The convergence of the Krylov method is closely related to the spectral distribution. In order to improve the convergence of the algorithm, we attempts to extend the recycling BiCG(RBiCG) algorithm to solve shifted linear systems. However, the shift-invariant property could no longer hold over the augmented Krylov subspace due to adding the recycling spaces. To remedy this situation, a strategy to enforce the collinearity condition on the shifted system is adopted and then a short term recurrence for the solution update of the shifted system is derived when the seed system is solving. The new method not only improves the convergence but also has a potential to simultaneously compute approximate solutions for shifted linear systems using only as many matrix vector multiplications as the solution of a single system requires. In addition, some numerical experiments also confirm the efficiency of our method.3. To solve linear systems with multiple righthand sides efficiently, we first present a flexible version of BGMRES-DR and then apply a modified block Arnoldi vector deflation technique to accelerate the convergence of this new flexible version. Incorporating this deflation technique, the new algorithm can address the possible linear dependence at each iteration during the block Arnoldi procedure and reduce computational expense.In addition, the new approach also inherits the property of deflating small eigenvalues to mitigate convergence slowdown. Finally, the effectiveness of the proposed method is illustrated by some numerical experiments.4. Aiming at solution to linear systems with multiple righthand sides, we explore a new block GCROT(m, k)(BGCROT(m, k)) method. It is proved that under the condition of full rank of block residual, the Frobenius norm of the block residual generated by the proposed method is always nonincreasing. Moreover, we also present its block flexible version, BFGCROT(m, k). In order to avoid the possible linear dependence during the iterative procedure, the modified block Arnoldi deflation technique is introduced, which can avoid “serious breakdown” effectively. Finally, numerical examples demonstrate that the BGCROT(m, k) method, its flexible variant and deflated variant work well and can be more competitive than some other block solvers.