The speedup of distributed iterative solution of systems of linear equations

Abstract

The main objective of this research is to study the performance of distributed solvers for large sparse systems of linear equations. The relationship between the speedup and the number of processors is the main characteristic of distributed computing for this study. -- Systems of linear equations can be solved using either direct or iterative methods. For large and sparse systems of equations, iterative methods are often more attractive than direct methods. In distributed implementations of iterative solvers, the number of operations are equally divided among the available processors with the intention that all the sections are processed concurrently (i.e., by different processors). -- The iterative approach repeats the following sequence of steps until the required convergence condition is satisfied: -- 1. distribute the current approximation to all the processors, -- 2. determine a new approximation to the solution, -- 3. collect parts of the new approximation and check the convergence conditions. -- The implementation is based on the message passing paradigm, which is used widely on certain classes of multiprocessor machines, especially systems with distributed memory. It is expected that this study will determine the optimal number of processors for distributed linear solvers.