The Study Of Parallel Algorithms For The Solution Of Special Structured Large Linear System Of Equations Under Distributed Memory Environment

Solving the special structured large systems of linear equations is essential in many application areas. For a long time, accompanied by the development of computer architectures, people have never stopped trying to find out new methods for solving various large systems of linear equations under new computing environments. Today the distributed-memory multicomputers have become the computing environments of many scientific and engineering applications and the first tools for solving grand challenge problems. Thus, as one of the most important and integral problem, it is deserved to study and design the high performance parallel algorithms for solving the special structured large system of linear equations under distributed-memory environments and this is meaningful in theory and practice.The parallel solvers for the special structured large systems of linear equations under distributed-memory environments were systematically studied in this dissertation. The main results of this research are as follows:1. A parallel solver for cyclic tridiagonal systems on distributed-memory multicomputers is presented. The algorithm is based on the principle of 'divide-and-conquer1 in designing parallel algorithms. The reduction systems' coefficient matrix keeps the structure of the original systems' coefficient matrix. And if the cyclic tridiagonal systems' coefficient matrix is strictly diagonally dominant then the reduction systems will keep this property. The algorithm's speedup satisfy:2. A parallel algorithm for solving tridiagonal linear systems on distributed-memory multicomputers is presented. This algorithm avoids unnecessary redundancy computation. The loads of solving the system are evenly distributed among the processors. This algorithm makes full use of overlapping between computation and communication to decreasing the amount of processors' idle time. The algorithm's absolute speedup satisfy: Sp(n)→(p+2y2, (n→+∞). Its absolute efficiency satisfy:3. A high performance parallel algorithm for Toeplitz cyclic tridiagonal systems ondistributed-memory multicomputer is presented. The algorithm is based on the factorization of the coefficient matrix. The algorithm's absolute speedup satisfy: Sp(n)→p(n→+∞). This is the idea result a parallel algorithm can reach.4. A high performance parallel algorithm for Toeplitz tridiagonal systems on distributed-memory multicomputers is presented. The algorithm is also based on the factorization of the coefficient matrix. It makes full use of the special structure of the coefficient matrix. Its redundancy computation caused by parallelization is less. The algorithm's absolute speedup satisfy: Sp(n) →(n→+∞). This is also the idea result a parallel algorithm can reach.5. A parallel solver for cyclic block-tridiagonal systems on distributed-memory multicomputers is developed hi this paper. The algorithm is based on matrix block operations. The implementation of this algorithm invokes BLAS3 subroutines. The efficiency of this algorithm is much higher than that of the algorithm presented by K.L.Chung et al[38]. The algorithm's absolute speedup satisfy:S M→ (n→+∞), where s is the block size. 6. A parallel algorithm for block-tridiagonal linear systems on distributed-memory multicomputers is presented. This algorithm is also based on matrix block operations. The implementation of this algorithm invokes BLAS3 subroutines. On account of carefully estimating the computation task, the load of solving the system is evenly distributed among the processors. The algorithm's absolutespeedup satisfy. Sp(n) → (n→+∞), where s is the block size.7. A parallel algorithm for certain real symmetric block-tridiagonal linear systems on distributed-memory multicomputers is proposed. This algorithm is based on the block factorization of the coefficient matrix. This algorithm is used to solving the block-tridiagonal linear systems resulted from the finite difference approximation to Poisson's equation with Dirichlet boundary conditi...