Share Email Print

Proceedings Paper

Matrix Triangularization By Systolic Arrays
Author(s): W. M. Gentleman; H. T. Kung
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Given an n x p matrix X with p < n, matrix triangularization, or triangularization in short, is to determine an n x n nonsingular matrix Al such that MX = [ R 0 where R is p x p upper triangular, and furthermore to compute the entries in R. By triangularization, many matrix problems are reduced to the simpler problem of solving triangular- linear systems (see for example, Stewart). When X is a square matrix, triangularization is the major step in almost all direct methods for solving general linear systems. When M is restricted to be an orthogonal matrix Q, triangularization is also the key step in computing least squares solutions by the QR decomposition, and in computing eigenvalues by the QR algorithm. Triangularization is computationally expensive, however. Algorithms for performing it typically require n3 operations on general n x n matrices. As a result, triangularization has become a bottleneck in some real-time applications.11 This paper sketches unified concepts of using systolic arrays to perform real-time triangularization for both general and band matrices. (Examples and general discussions of systolic architectures can be found in other papers.6.7) Under the same framework systolic triangularization arrays arc derived for the solution of linear systems with pivoting and for least squares computations. More detailed descriptions of the suggested systolic arrays will appear in the final version of the paper.

Paper Details

Date Published: 30 July 1982
PDF: 8 pages
Proc. SPIE 0298, Real-Time Signal Processing IV, (30 July 1982); doi: 10.1117/12.932507
Show Author Affiliations
W. M. Gentleman, University of Waterloo (United States)
H. T. Kung, Carnegie-Mellon University (United States)

Published in SPIE Proceedings Vol. 0298:
Real-Time Signal Processing IV
Tien F. Tao, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?