Complexity of Dense Linear System Solution on a Multiprocessor Ring.

Abstract

Different algorithms, based on Gaussian elimination, for the solution of dense linar systems of equations, are discussed for a multiprocessor ring. The number of processors is assumed not to exceed the problem size. A fairly general model for data transfer is proposed and the algorithms are analysed with respect to their requirements of arithmetic as well as communication times. This paper lays no claims to being either exhaustive or complete. Its objective is to compare a variety of algorithms, which are fairly reasonable to program and to analyse, for the solution of a single problem on a certain class of parallel architectures, thereby leading to a more realistic approach to future algorithm development on multiprocessor machines.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1985
Accession Number
ADA151970

Entities

People

  • I. C. F. Ipsen
  • Martin H. Schultz
  • Y. Saad

Organizations

  • Yale University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Broadcasting
  • Coefficients
  • Communication Networks
  • Computations
  • Computer Science
  • Data Transmission
  • Digital Communications
  • Elimination
  • Linear Systems
  • Multiprocessors
  • Pipes
  • Probabilistic Models
  • Scattering

Fields of Study

  • Engineering

Readers

  • Operations Research
  • Parallel and Distributed Computing.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms