Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A Computational Array for the QR-Method

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

Publishing Venue

Software Patent Institute

Related People

Lennart Johnsson: AUTHOR [+3]

Abstract

The QR-method is a method for the solution of linear system of equations. The matrix R is upper triangular and Q is a unitary matrix. In equation solving Q is not always computed explicitly. The matrix R can be obtained by applying a sequence of unitary transformations to the matrix defining the system of equations. Householder's method or Given's method can be used to determine unitary transformation matrices. This paper describes a concurrent algorithm and corresponding array for computing the triangular matrix R by Householder transformations. Particular attention is given to issues such as broadcasting and pipelining.

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

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Computational Array for the QR-Method

' Lennart Johnsson California Institute of Technology Pasadena, California 91125

5019: TM: 82

(Presented at the Conference on Advanced Research in VLSI, January 25 - 27, 1982, Massachusetts Institute of Technology) A COMPUTATIONAL ARRAY FOR THE QR-METHOD

LENNART JOHNSSON .

Computer Science California Institute of Technology Pasadena, CA.

ABSTRACT

The QR-method is a method for the solution of linear system of equations. The matrix R is upper triangular and Q is a unitary matrix. In equation solving Q is not always computed explicitly. The matrix R can be obtained by applying a sequence of unitary transformations to the matrix defining the system of equations. Householder's method or Given's method can be used to determine unitary transformation matrices. This paper describes a concurrent algorithm and corresponding array for computing the triangular matrix R by Householder transformations. Particular attention is given to issues such as broadcasting and pipelining.

INTRODUCTION

In, this paper algorithms for the solution of systems of linear equations by the QR-method are described. In particular algorithms for the computation of the factorization through, Householder transformations are investigated. Special attention is given to implementation issues in VLSI technology.

As the feature sizes are scaled down the electrical characteristics of the circuitry changes. These changes have many implications, also algorithmically.

The research presented in this paper is supported by the Defense Advanced Research Project Agency under contract N00014-79-C-0597 with the California Institute of Technology The switching speed of devices increases but wire delay does not decrease. For a wire the length of which scales down with the scaling factor, the delay stays constant under scaling, while for a wire of constant length the delay actually increases with the square of the sealing factor. Hence, it is of particular importance to study the communication needs of algorithms intended for implementation in a technology with feature sizes of one micron or less. Algorithms with a high degree of concurrency and which only requires communication with computational elements that can be arranged to be nearest neighbors in a plane are preferable.

Broadcasting typically implies- a performance penalty in VLSI technology. Pipelining can be used to eliminate broadcasting and in general improve the computational rate. If the data flow through the array is turbulent, i.e., the data flows through loops in the network, it is in general necessary to space the data out in time due to the pipelining, as demonstrated in [Johnsson 81]

California Institute of Technology Page 1 Dec 31, 1982

Page 2 of 10

A Computational Array for the QR-Method

for arrays for Gaussian elimination. Furthermore, pipelining and partial pivoting do not combine, nicely. Partial pivoting makes...