Browse Prior Art Database

VLSI ALGORITHMS FOR DOOLITTLE'S, CROUT'S, AND CHOLESKY'S METHODS

IP.com Disclosure Number: IPCOM000127921D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 6 page(s) / 26K

Publishing Venue

Software Patent Institute

Related People

Lennart Johnsson: AUTHOR [+3]

Abstract

In order to take full advantage of the emerging VLSI technology it is required to recognize its limited communication capability and structure algorithms accordingly. In this paper concurrent algorithms for the methods of Crout, Doolittle and Cholesky are described and compared with concurrent algorithms for Gauss', Given's and Householder's method. The effect of pipelining the computations in two dimensional arrays is given special attention.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 17% of the total text.

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

VLSI ALGORITHMS FOR DOOLITTLE'S, CROUT'S, AND CHOLESKY'S METHODS

Lennart Johnsson California Institute of Technology Pasadena, California 91125

TM 5030 this paper will appear in Proc. IEEE International Conference on Circuits and Computers, ICCC 82 New York, September 29 -- October 1,

ABSTRACT

In order to take full advantage of the emerging VLSI technology it is required to recognize its limited communication capability and structure algorithms accordingly. In this paper concurrent algorithms for the methods of Crout, Doolittle and Cholesky are described and compared with concurrent algorithms for Gauss', Given's and Householder's method. The effect of pipelining the computations in two dimensional arrays is given special attention.

INTRODUCTION

The need to solve linear systems of equations is frequent in engineering and science. The need occurs not only in traditional calculations but also in the area of signal processing. The interest in improved performance for engineering calcula-tions is most significant for large problems while in signal processing applications the problem size typically is orders of magnitude less but the need to perform computations in real time demands a concurrent algorithm that can be conveniently implemented in hardware.

A linear system of equations is often represented by where A is a matrix and x and y vectors. It is often the case that the matrix A has structural properties that can be used advantageously to reduce computations as well as the amount of hardware required. In the following the matrix A is assumed to have band structure. Algorithms developed for band matrices are, in general, also efficient for full matrices given the communication limitations imposed by VLSI technology.

By studying band matrices insight is gained into the relationship between problem characteristics and the organization of data flow and computations in a network of processing elements. Techniques for general sparse matrices have been developed extensively for sequential machines during the last decade. To devise efficient concurrent algorithms for a more general sparse matrix than a band matrix is a very complex task that is not treated here.

Many direct methods for the solution of linear systems of equations can be considered as consisting of two phases, one phase where the system matrix is factored into one upper triangular and one lower triangular matrix including forward substitution, and one phase for the back substitu- tion. Here only the triangulation opera ti for Cholesky's, Crout's and Doolittle's methods n will be considered. The forward and back substitution can be performed in the same way for Gauss', Givens', Doolittle's, Crout's and Cholesky's methods. For concurrent algorithms and computa- tional arrays 6or the 3forward ani back substitution see e.g., Kung , Kung , Johnsson .

California Institute of Technology Page 1 Dec 31, 1982

Page 2 of...