Application And Research Of Parallel Algorithms For Solving Large-scale Linear Equations

The problem of solving a linear system of equations is recognized as an important issue in computational mathematics and computer science. A large number of computation-intensive applications reduce to the solutions of large-scale linear systems. Many efficient numerical methods have been developed for solving linear systems on uniprocessor systems, and the source codes of high quality are available for different classes of linear systems.With the advances of Very Large Scale Integration (VLSI) and networking technology, solving a linear system on a multiprocessor system has received considerable research interest. In particular, a variety of parallel algorithms have been developed for this purpose. Before these parallel algorithms can be put into practical use, some issues related to their implementation on parallel computers must be solved.This thesis addresses the issue of implementation on the IBM x3500 server of some classical parallel algorithms for solving linear systems (such as Gauss elimination, Jordan elimination, LU decomposition, etc). The linear systems can be categorized into two subclasses, the dense linear equations and the sparse linear equations. The dense linear systems are usually cracked in a straight way, and the solutions of sparse linear equations are often obtained using iterative methods.The main work of this paper is presented as follows:(1) Parallel computing architecture and the MPI message-passing programming introduction, and the basics of MPI programming are reviewed.(2) Research direct method for solving linear equations. The Gauss and Jordan parallel elimination algorithms are reviewed. The performances of these two parallel algorithms, including both the computation costs and the communication costs, are analyzed. Finally, with the aid of the MPI programming environment, these two algorithms are implemented on the multiprocessor computer.(3) Research iterative method for solving linear equations. The Jacobi iteration, Seidel iteration and SOR are reviewed, and Jacobi and Seidel parallel algorithms are implemented on the multiprocessor computer.(4) To reflect the practical value of solving large-scale sparse linear equations, we have studied the two-dimensional Poisson equation based on discrete method. The MPI implementation of this solution process is reviewed. Finally, we improved the MPI program in many ways.