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 computer architectures are considered: a multiprocessor ring, a grid array and a hypercube, This complexity analysis fully accounts for communication delays by using simple mathematical models where both latency and actual transfert 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. Additional keywords: Parallel computers; Scientific computing. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1985
Accession Number
ADA160148

Entities

People

  • Martin H. Schultz
  • Y. Saad

Organizations

  • Yale University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Bandwidth
  • Computations
  • Computer Science
  • Data Transmission
  • Differential Equations
  • Digital Communications
  • Elimination
  • Equations
  • Linear Systems
  • Multiprocessors
  • Partial Differential Equations
  • Real Variables
  • Three Dimensional
  • Two Dimensional

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.
  • Phased Array Antenna Design.