Large Cycle Block Tridiagonal With The Equations Of Parallel Algorithms

At present, a hotspot problem to be solved is to make the best use of the potential capability of parallel computers and investigates high efficient parallel methods for solving large sparse linear systems. The key point for designing of parallel algorithms and implementation of parallel programs is to reduce global communication and maintain load balance between processors according to architecture characters of different parallel computers.Based on the above idea, we study parallel algorithm for solving periodical block-tridiagonal linear systems on distributed memory multi-computers. The main results of this research are as follows:(1) An approximate direct parallel solver for periodical block-tridiagonal systems on distributed-memory multi-computers is presented. The algorithm is based on the principle of 'divide-and-conquer' and the factorization of the coefficient matrix. It makes full use of the special structure of the coefficient matrix. The communication is only twice between the adjacent processors. In theory, this paper gives an enough condition and the error analysis about this algorithm. Finally, some numerical results on HP rx2600 cluster show that this parallel algorithm is feasible and efficient.(2) An iterative parallel solver for periodical block-tridiagonal systems on distributed-memory multi-computers is developed by means of the first method. The algorithm is based on splitting the coefficient matrix. It can be computed under the conditions where the first method is unfeasible. The communication is only twice between the adjacent processors per iteration. In theory, we give a convergent conditions which the coefficient matrix is Hermite positive definite or M-matrix and give the error analysis about this algorithm. Finally, some numerical results on HP rx2600 cluster show that practice computing is consistent with theory.(3) We study a relaxed iterative parallel method. The goal of introducing relaxed factor is to accelerate the convergence rate. A difficulty is to investigate the algorithm's convergence, but some numerical results on HP rx2600 cluster show that both the iterative number and time are far small, the convergence rate is better, the efficiency is higher.(4) An accurate parallel algorithm for solving periodical block-tridiagonal systems on distributed-memory multi-computers is developed. Meanwhile, some relevant theory and numerical examples is proposed.(5) We proposed a parallel algorithm of Arnoldi method based on Galerkin formulation for solving block tridiagonal linear equations. By means of the choice of apt subspaces or multiple search directions, this algorithm only requires two communications between adjacent processors per iteration. We also give the convergence theory of this method and some relevant numerical examples. The results of some numerical experiments on HP rx2600 cluster show that speedup improves linearly and the efficiency of this method is up to 90%.