Data Traffic Reduction Schemes for Cholesky Factorization on Asynchronous Multiprocessor Systems

Abstract

Communication requirements of Cholesky factorization of defense and sparse symmetric, positive definite matrices are analyzed. The communication requirement is characterized by the data traffic generated on multiprocessor systems with local and shared memory. Lower bound proofs are given. Partitioning schemes that are variations of block assignment scheme are described and it is shown that the data traffic generated by these schemes are asymptotically optimal. Itis shown that the block based partitioning schemes allow a better utilization of the data accessed from shared memory and thus reduce the data traffic than those based on column-wise wrap around assignment scheme. Keywords: Data processing; Processors.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1989
Accession Number
ADA211655

Entities

People

  • Merrell L. Patrick
  • Vijay K. Naik

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Computing System Architectures
  • Decomposition
  • Elimination
  • Graph Theory
  • Load Distribution
  • Multiprocessors
  • Observation
  • Ring Networks
  • Separators
  • Sparse Matrix
  • Three Dimensional
  • Two Dimensional

Fields of Study

  • Computer science
  • Engineering

Readers

  • Linear Algebra
  • Parallel and Distributed Computing.
  • Radio communications and signal processing.