Publication: Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR)  

Authors:
Merchant, F. ,  Chattopadhyay, A. ,  Garga, G. ,  Nandy, S. K. ,  Narajan, R.
Book Title:
27th International Conference on VLSI Design, IIT Bombay, Mumbai India January 7-9
Pages:
p.p. 258 - 263
Date:
2014
ISSN:
1063-9667
DOI:
10.1109/VLSID.2014.51
Language:
English

Abstract

QR decomposition (QRD) is a widely used Numerical Linear Algebra (NLA) kernel with applications ranging from SONAR beamforming to wireless MIMO receivers. In this paper, we propose a novel Givens Rotation (GR) based QRD (GR-QRD) where we reduce the computational complexity of GR and exploit higher degree of parallelism. This low complexity Column-wise GR (CGR) can annihilate multiple elements of a column of a matrix simultaneously. The algorithm is first realized on a Two-Dimensional (2D) systolic array and then implemented on REDEFINE which is a Coarse Grained run-time Reconfigurable Architecture (CGRA). We benchmark the proposed implementation against state-of-the-art implementations to report better throughput, convergence and scalability.

Download

BibTeX