Parallel Direct Methods for Solving Banded Linear Systems.
Abstract
This paper proposes several implementations of Gaussian elimination for solving banded linear systems on multiprocessors. Three simple architectures are considered: a multiprocessor ring, a grid array and a hypercube. The complexity analysis fully accounts for communication delays by using simple models where both latency and actual transfer times are incorporated. When the number of processors is small relative to the bandwidth of the system a row interleaved implementation of Gaussian elimination algorithm is attractive. Otherwise, a two-dimensional grid is essential for achieving higher speed-up. The hypercube architecture gives the smallest communication latency times. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1985
- Accession Number
- ADA159354
Entities
People
- Martin H. Schultz
- Y. Saad
Organizations
- Yale University