Honors Thesis

Evaluating Parallel Techniques for Solving Sparse Linear Systems

Andrew White '06

(:abstract:) It is known that solving linear systems in parallel can significantly improve performance, but under different solve methods, hardware, data partitioning,and other considerations it is difficult to know what type of performance to expect. In our evaluation of parallel techniques we seek to expand the understanding of how these factors affect performance.

In this paper parallel implementations of linear solvers are evaluated to see how their techniques perform on a range of linear systems designed to vary the communication requirements and the computational workload. First, linear systems are discussed including direct and indirect methods for solving them. Next, parallel computing is discussed and how it can be applied to solving linear systems. Several different data partitioning schemes are then considered to increase efficiency: uniform block, predictive weighted block, and weighted block. Parallel versions of back substitution, Jacobi iteration, and a Jacobi/Gauss-Seidel iteration hybrid are implemented in combination with the three partitioning schemes and evaluated on systems ranging in size from 50,000 equations to 250,000 and densities from one million non-zero entries to ten million. (:endabstract:)

<< Andrew West | Main List | Peter Djalaliev >>