Systolic Algorithms for the Parallel Solution of Dense Symmetric Positive-Definite Toeplitz Systems.

Abstract

The most popular method for the solution of linear systems of equations with Toeplitz coefficient matrix on a single processor is Levinson's algorithm, whose intermediate vectors form the Cholesky factor of the inverse of the Toeplitz matrix. However, Levinson's method is not amenable to efficient parallel implementation. In contrast, use of the Schur algorithm, whose intermediate vectors form the Cholesky factor of the Toeplitz matrix proper, makes it possible to perform the entire solution procedure on one processor array in time linear in the order of the matrix. By means of the Levinson recursions we will show that all three phases of the Toeplitz system solution process: factorisation, forward elimination and backsubstitution, can be based on Schur recursions. This increased exploitation of the Toeplitz structure then leads to more efficient parallel implementations on systolic arrays.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1987
Accession Number
ADA182633

Entities

People

  • Ilse C. Ipsen

Organizations

  • Yale University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Arrays
  • Computations
  • Computer Architecture
  • Computer Science
  • Computers
  • Computing System Architectures
  • Elimination
  • Equations
  • Global Communications
  • Linear Arrays
  • Linear Systems
  • Military Research
  • Signal Processing
  • Three Dimensional
  • Time Intervals

Fields of Study

  • Engineering

Readers

  • Linear Algebra
  • Parallel and Distributed Computing.