CS 6404

Solutions to Linear Systems

Using Parallel Computers

Manoj Bhardwaj

Dan Haim

Debbie Pilkey

Spring 1996

Solution of a Linear System of Equations By Exploiting Parallel Computers

• Project Background and Motivation
  1. Problem Statement: Solution to a Linear system, Ax=b, using Parallael Comutational Methods
  2. Why did we choose a Linear System.
  3. Resources Used in the Project
• Method of solving Ax=b: Gaussian Elimination with Backward Substitution
  1. Summary of Gaussian Elimination
• Computer Resources
  1. IBM SP-2, Intel Paragon, MPI Standard
• Description of Program
  1. How the problem is split, and MPI calls used
  2. Size of problem and number of processors used
  3. Babbage versus Spider
• ScaLAPACK
  1. Overview and Installation
  2. LU Factorization Implementation
  3. Results on the SP-2
  4. Comparison With Benchmark Results
• Results of the MPI code
  1. Timing studies versus number of processors
  2. Load Balancing, scalability.
  3. MFLOPS computations
• Applicability of the code to real life problems
  1. Finite Element Solutions of Large, Grand Challenge problems
• Conclusions

  ---

• References:
  1. J. Choi et al., "ScaLAPACK: A Portable Linear Algebra Library for Distributed Memory Computers", Technical report, 1995.
  2. J. Choi et al., "The Design and Implementation of the ScaLAPACK LU, QR, and Cholesky Factorization Routines", Technical report, September 1994.
  3. MPI: A Message-Passing Interface Standard, Message Passing Interface Forum, May 5, 1994.