O(log2 n) Time Efficient Parallel Factorization of Dense, Sparse Separable, and Banded Matrices

Abstract

Known polylog parallel algorithms for the solution of linear systems and related problems require computation of the characteristic polynomial or related forms, which are known to be highly unstable in practice. However, matrix factorizations of various types, bypassing computation of the characteristic polynomial, are used extensively in sequential numerical computations and are essential in many applications.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 11, 1994
Accession Number
ADA280052

Entities

People

  • John Reif

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Iterations
  • Linear Systems
  • Numerical Analysis
  • Parallel Computing
  • Parallel Processing
  • Sparse Matrix
  • Theorems
  • Trees (Data Structures)
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Linear Algebra
  • Systems Analysis and Design