On the Optimal Solution of Large Linear Systems,

Abstract

We investigate the minimal number of matrix-vector multiplications to approximately solve a linear system. The minimal number of multiplications depends on the properties of a class of problems such as symmetry, positive definiteness, and bound on condition number. For different classes of problems we obtain the minimum exactly or almost exactly and establish with algorithms are optimal, that is, attain the minimum. Furthermore, we obtain quantitative results on how the lack of certain properties increases the minimum. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1980
Accession Number
ADA086349

Entities

People

  • H. Wozniakowski
  • Joseph F. Traub

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Chebyshev Polynomials
  • Coefficients
  • Computations
  • Computer Science
  • Computers
  • Differential Equations
  • Eigenvalues
  • Elimination
  • Equations
  • Linear Algebra
  • Linear Systems
  • New York
  • Polynomials
  • Sparse Matrix
  • Symmetry

Fields of Study

  • Mathematics

Readers

  • Approximation Theory.
  • Operations Research