A Fan-In Algorithm for Distributed Sparse Numerical Factorization

Abstract

We present a column-oriented distributed algorithm for factoring a large sparse symmetric positive definite matrix on a local-memory parallel processor. Processors co-operate in computing each column of the Cholesky factor by calculating independent updates to the corresponding column of the original matrix. These updates are sent in a fan- in manner to the processor assigned to the column, which then completes the computation. Experimental results on an Intel iPSC/2 hypercube demonstrate that the method is effective and achieves good speedups.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 15, 1989
Accession Number
ADA211569

Entities

People

  • Cleve Ashcraft
  • Joseph W. Liu
  • Stanley C. Eisenstat

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Connecticut
  • Contracts
  • Linear Systems
  • Military Research
  • Parallel Processors
  • Sparse Matrix
  • Triangles
  • Universities

Fields of Study

  • Computer science

Readers

  • Linear Algebra
  • Parallel and Distributed Computing.