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

Merchant, F., Chattopadhyay, A., Garga, G., Nandy, S. K., Narayan, R., & Gopalan, N. (2014). Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR). In 2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems (pp. 258-263). Article 6733140 IEEE. https://doi.org/10.1109/VLSID.2014.51

Merchant, Farhad ; Chattopadhyay, Anupam ; Garga, Ganesh et al. / Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR). 2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems. IEEE, 2014. pp. 258-263

@inproceedings{8be6c826b6e6477f988339bd5256b034,

title = "Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR)",

abstract = "QR decomposition (QRD) is a widely used Numerical Linear Algebra (NLA) kernel with applications ranging from SONAR beam forming 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.",

keywords = "Arrays, Parallel processing, Clocks, Equations, Adders, Computational complexity",

author = "Farhad Merchant and Anupam Chattopadhyay and Ganesh Garga and S.K. Nandy and Ranjani Narayan and Nandhini Gopalan",

year = "2014",

month = jan,

day = "9",

doi = "10.1109/VLSID.2014.51",

language = "English",

isbn = "978-1-4799-2513-1",

pages = "258--263",

booktitle = "2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems",

publisher = "IEEE",

note = "2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems ; Conference date: 05-01-2014 Through 09-01-2014",

}

Merchant, F, Chattopadhyay, A, Garga, G, Nandy, SK, Narayan, R & Gopalan, N 2014, Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR). in 2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems., 6733140, IEEE, pp. 258-263, 2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems, 05/01/2014. https://doi.org/10.1109/VLSID.2014.51

Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR). / Merchant, Farhad; Chattopadhyay, Anupam; Garga, Ganesh et al.
2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems. IEEE, 2014. p. 258-263 6733140.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Merchant, Farhad

AU - Chattopadhyay, Anupam

AU - Garga, Ganesh

AU - Nandy, S.K.

AU - Narayan, Ranjani

AU - Gopalan, Nandhini

PY - 2014/1/9

Y1 - 2014/1/9

N2 - QR decomposition (QRD) is a widely used Numerical Linear Algebra (NLA) kernel with applications ranging from SONAR beam forming 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.

AB - QR decomposition (QRD) is a widely used Numerical Linear Algebra (NLA) kernel with applications ranging from SONAR beam forming 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.

KW - Arrays

KW - Parallel processing

KW - Clocks

KW - Equations

KW - Adders

KW - Computational complexity

U2 - 10.1109/VLSID.2014.51

DO - 10.1109/VLSID.2014.51

M3 - Conference contribution

SN - 978-1-4799-2513-1

SP - 258

EP - 263

BT - 2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems

PB - IEEE

T2 - 2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems

Y2 - 5 January 2014 through 9 January 2014

ER -

Merchant F, Chattopadhyay A, Garga G, Nandy SK, Narayan R, Gopalan N. Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR). In 2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems. IEEE. 2014. p. 258-263. 6733140 doi: 10.1109/VLSID.2014.51