Systolic rank revealing QR algorithm

F. Lorenzelli*, Kexin Yao, Tony Chan, P. C. Hansen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

In many fields of signal and image processing, control, and telecommunication there is much interest today in the numerical techniques offered by linear algebra. The singular value decomposition (SVD) is one of the techniques which have proven useful in many engineering applications, but unfortunately its computation is a costly procedure. The QR Factorization (QRF) requires much less computational effort, but rank and null-space estimates are not necessarily reliable. T. F. Chan and L. V. Foster developed an algorithm which guarantees the QRF to reveal the rank of a matrix. The main purpose of this paper is to present a version of this Rank Revealing QR (RRQR) algorithm which is suited for implementation on a VLSI systolic array. The implementation of the RRQRF that we propose in this paper requires n(n+1)/2 processors and O(n) external buffers, for a problem of order n. The execution time for the algorithm is O(nr), where r is A's numerical rank.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Application
PublisherPubl by IEEE
Pages430-444
Number of pages15
ISBN (Print)0818629673
StatePublished - Dec 1 1992
EventProceedings of the International Conference on Application Specific Array Processors - Berkeley, CA, USA
Duration: Aug 4 1992Aug 7 1992

Publication series

NameProceedings of the International Conference on Application

Conference

ConferenceProceedings of the International Conference on Application Specific Array Processors
CityBerkeley, CA, USA
Period08/4/9208/7/92

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Systolic rank revealing QR algorithm'. Together they form a unique fingerprint.

Cite this