Efficient Parallel Solution of Linear Systems.

Abstract

The most efficient known parallel algorithms for inversion of a nonsingular nxn matrix A or solving a linear system Ax=b over the rationals require O(log n) to the 2nd power time and M(n) square root of n processors (where M(n) is the number of processors required in order to multiply two nxn rational matrices in time O(log n)). Furthermore, all known polylog time algorithms for those problems are unstable: they require the calculations to be done with perfect precision; otherwise they give no results at all. This paper describes parallel algorithms that have good numerical stability and remain efficient as n grows large. Additional keywords: Iterations; Convergence; Newtons method; Computer architecture.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1985
Accession Number
ADA152663

Entities

People

  • J. Reif
  • V. Pan

Organizations

  • Harvard University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computational Science
  • Computations
  • Computer Science
  • Computers
  • Difference Equations
  • Differential Equations
  • Equations
  • Error Analysis
  • Fluid Mechanics
  • Inversion
  • New York
  • Numerical Analysis
  • Parallel Computing
  • Precision
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Linear Algebra