Parallel GPBiCG(m,l) Algorithm And Preconditioning Techniques

The numerical simulation of many large scale scientific computing problems is always leading to the solution of large sparse linear and nonlinear algebraic systems. Solving the algebraic systems consumes so much of the time in the entire simulation time that it always becomes the bottleneck of the simulation. Hence, the key for solving such problems is to design high performance algebra solvers, which settles the foundation for developing relative high performance software. Currently, there are two ways to reduce solution time of large scale al-gebraic systems—one is parallel computing and the other is using preconditioning techniques.Three problems are studied in this work:the design and analysis of one of parallel Krylov subspace iterative method; a novel preconditioning techniques based on stencil elimination and a class of inverse eigenvalue problems met in the research of the theory of preconditioning technique.Firstly, We focus on how to design a parallel Krylov subspace iterative method based on GPBiCG(m, l) method come forth in the literature recently, which aims at solving bottleneck problem—global communications—in the parallel computation of Krylov iterative methods. The idea in designing is to reduce the three inner synchronization points required per iteration of the original method to one. We call the novel method improved GPBiCG(m,l) (IGPBiCG(m,l) in brief) method. We proved that the scalability of the improved methods is 3 times better than that of the original one. The save in solution time of IGPBiCG(m, l) method compared with GPBiCG(m,l) tended to 66%. Numer-ical experiments gave results meeting with our theoretical analysis. Furthermore, although GPBiCG(1,0) method is equivalent with BiCGSTAB mathematically, numerical experiments shown that the convergence of IGPBiCG(1,0) method is better than that of IBiCGSTAB method in [92].Secondly, we proposed a new preconditioning technique based on stencil elimination. Mathematical stencil elimination was proposed in [96] for the con- struction of parallel difference scheme. We developed it to a stencil elimination preconditioning technique. For the linear systems arising from the discretiza-tion of PDEs in 2D or 3D with five-point or seven-point difference scheme, we prove that the Krylov subspace iterative method with such preconditioning is twice faster than that of method without preconditioning. Our preconditioning is easy implemented and combined with other preconditioning. Numerical exper-iments show that the convergent rate of Krylov subspace iterative method can be improved largely by using our preconditioning with ILU(0). Furthermore, we develop an algebraic stencil elimination to find the inverse of a matrix and give some theoretical analysis on its computational complexity.Finally, in order to keeping some properties of the inverse of special matri-ces, a brief and practical algorithm is introduced to solve nonnegative matrices inverse eigenvalue problem and M-matrices inverse eigenvalue problem. We an-alyzed the stability, sensitivity and computational count of our new algorithm. Some sufficient condition and necessary condition for the solvability of nonneg-ative matrices and M-matrices inverse problems were given. Based on our new algorithm, we developed a multilevel adaptive algorithm. The efficiency of our algorithms were validated by large amount of numerical examples.