Accession Number : ADA182633

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

Descriptive Note : Research rept.,

Corporate Author : YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Personal Author(s) : Ipsen,Ilse C

PDF Url : ADA182633

Report Date : May 1987

Pagination or Media Count : 24

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.

Descriptors :   *COMPUTER ARCHITECTURE, ALGORITHMS, INVERSION, PARALLEL PROCESSING, SOLUTIONS(GENERAL), EQUATIONS, LINEAR SYSTEMS, MATRICES(MATHEMATICS), DATA PROCESSING EQUIPMENT

Subject Categories : Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE