A Triangular Systolic Array Based Digital Architecture for Computing Eigenvalues of Asymmetric Matrix

Elif Ozturk; Ilayda Koseoglu; Mustak E. Yalcin

doi:10.1109/CNNA49188.2021.9610808

A Triangular Systolic Array Based Digital Architecture for Computing Eigenvalues of Asymmetric Matrix

Elif Ozturk, Ilayda Koseoglu, Mustak E. Yalcin

Department of Electronics and Communication Engineering

Istanbul Technical University

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

1 Citation (Scopus)

Abstract

This paper proposes a time-efficient parallel architecture for computing eigenvalues of asymmetric matrix with real values. The QR algorithm is used to compute the eigenvalues of asymmetric matrices. The QR decomposition process is required for the QR algorithm. The Modified Gram Schmidt (MGS) Orthogonalization is structurally suitable for parallel implementation by creating a triangular systolic array architecture. This architecture is created by placing boundary cell (BC) and internal cell (IC) modules in a triangle. In each iteration, Q column vector and R diagonal element are produced within the BC module, R upper diagonal elements are produced in IC modules. In the TSA model created for the next matrix, n diagonal (BC) modules, (n (n-l))/2 off-diagonal (IC) modules were used. Diagonal elements are produced, 4 BC, 6 ICs are used for the 4×4 matrix input in the implemented structure. The intended time efficiency is achieved thanks to the parallel IC modules.

Original language	English
Title of host publication	2021 17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021
Publisher	IEEE Computer Society
ISBN (Electronic)	9781665439480
DOIs	https://doi.org/10.1109/CNNA49188.2021.9610808
Publication status	Published - 2021
Event	17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021 - Catania, Italy Duration: 29 Sept 2021 → 1 Oct 2021

Publication series

Name	International Workshop on Cellular Nanoscale Networks and their Applications
Volume	2021-September
ISSN (Print)	2165-0160
ISSN (Electronic)	2165-0179

Conference

Conference	17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021
Country/Territory	Italy
City	Catania
Period	29/09/21 → 1/10/21

Bibliographical note

Publisher Copyright:
© 2021 IEEE.

Keywords

asymmetric matrix
eigenvalue
Modified Gram Schmidt (MGS)
QR algorithm
QR decomposition (QRD)
systolic array

Access to Document

10.1109/CNNA49188.2021.9610808

Cite this

Ozturk, E., Koseoglu, I., & Yalcin, M. E. (2021). A Triangular Systolic Array Based Digital Architecture for Computing Eigenvalues of Asymmetric Matrix. In 2021 17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021 (International Workshop on Cellular Nanoscale Networks and their Applications; Vol. 2021-September). IEEE Computer Society. https://doi.org/10.1109/CNNA49188.2021.9610808

@inproceedings{f25ef766495f4cf48e5569bc7195f1cc,

title = "A Triangular Systolic Array Based Digital Architecture for Computing Eigenvalues of Asymmetric Matrix",

abstract = "This paper proposes a time-efficient parallel architecture for computing eigenvalues of asymmetric matrix with real values. The QR algorithm is used to compute the eigenvalues of asymmetric matrices. The QR decomposition process is required for the QR algorithm. The Modified Gram Schmidt (MGS) Orthogonalization is structurally suitable for parallel implementation by creating a triangular systolic array architecture. This architecture is created by placing boundary cell (BC) and internal cell (IC) modules in a triangle. In each iteration, Q column vector and R diagonal element are produced within the BC module, R upper diagonal elements are produced in IC modules. In the TSA model created for the next matrix, n diagonal (BC) modules, (n (n-l))/2 off-diagonal (IC) modules were used. Diagonal elements are produced, 4 BC, 6 ICs are used for the 4×4 matrix input in the implemented structure. The intended time efficiency is achieved thanks to the parallel IC modules.",

keywords = "asymmetric matrix, eigenvalue, Modified Gram Schmidt (MGS), QR algorithm, QR decomposition (QRD), systolic array",

author = "Elif Ozturk and Ilayda Koseoglu and Yalcin, {Mustak E.}",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE.; 17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021 ; Conference date: 29-09-2021 Through 01-10-2021",

year = "2021",

doi = "10.1109/CNNA49188.2021.9610808",

language = "English",

series = "International Workshop on Cellular Nanoscale Networks and their Applications",

publisher = "IEEE Computer Society",

booktitle = "2021 17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021",

address = "United States",

}

Ozturk, E, Koseoglu, I & Yalcin, ME 2021, A Triangular Systolic Array Based Digital Architecture for Computing Eigenvalues of Asymmetric Matrix. in 2021 17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021. International Workshop on Cellular Nanoscale Networks and their Applications, vol. 2021-September, IEEE Computer Society, 17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021, Catania, Italy, 29/09/21. https://doi.org/10.1109/CNNA49188.2021.9610808

A Triangular Systolic Array Based Digital Architecture for Computing Eigenvalues of Asymmetric Matrix. / Ozturk, Elif; Koseoglu, Ilayda; Yalcin, Mustak E.
2021 17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021. IEEE Computer Society, 2021. (International Workshop on Cellular Nanoscale Networks and their Applications; Vol. 2021-September).

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

TY - GEN

T1 - A Triangular Systolic Array Based Digital Architecture for Computing Eigenvalues of Asymmetric Matrix

AU - Ozturk, Elif

AU - Koseoglu, Ilayda

AU - Yalcin, Mustak E.

PY - 2021

Y1 - 2021

N2 - This paper proposes a time-efficient parallel architecture for computing eigenvalues of asymmetric matrix with real values. The QR algorithm is used to compute the eigenvalues of asymmetric matrices. The QR decomposition process is required for the QR algorithm. The Modified Gram Schmidt (MGS) Orthogonalization is structurally suitable for parallel implementation by creating a triangular systolic array architecture. This architecture is created by placing boundary cell (BC) and internal cell (IC) modules in a triangle. In each iteration, Q column vector and R diagonal element are produced within the BC module, R upper diagonal elements are produced in IC modules. In the TSA model created for the next matrix, n diagonal (BC) modules, (n (n-l))/2 off-diagonal (IC) modules were used. Diagonal elements are produced, 4 BC, 6 ICs are used for the 4×4 matrix input in the implemented structure. The intended time efficiency is achieved thanks to the parallel IC modules.

AB - This paper proposes a time-efficient parallel architecture for computing eigenvalues of asymmetric matrix with real values. The QR algorithm is used to compute the eigenvalues of asymmetric matrices. The QR decomposition process is required for the QR algorithm. The Modified Gram Schmidt (MGS) Orthogonalization is structurally suitable for parallel implementation by creating a triangular systolic array architecture. This architecture is created by placing boundary cell (BC) and internal cell (IC) modules in a triangle. In each iteration, Q column vector and R diagonal element are produced within the BC module, R upper diagonal elements are produced in IC modules. In the TSA model created for the next matrix, n diagonal (BC) modules, (n (n-l))/2 off-diagonal (IC) modules were used. Diagonal elements are produced, 4 BC, 6 ICs are used for the 4×4 matrix input in the implemented structure. The intended time efficiency is achieved thanks to the parallel IC modules.

KW - asymmetric matrix

KW - eigenvalue

KW - Modified Gram Schmidt (MGS)

KW - QR algorithm

KW - QR decomposition (QRD)

KW - systolic array

UR - http://www.scopus.com/inward/record.url?scp=85122987241&partnerID=8YFLogxK

U2 - 10.1109/CNNA49188.2021.9610808

DO - 10.1109/CNNA49188.2021.9610808

M3 - Conference contribution

AN - SCOPUS:85122987241

T3 - International Workshop on Cellular Nanoscale Networks and their Applications

BT - 2021 17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021

PB - IEEE Computer Society

T2 - 17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021

Y2 - 29 September 2021 through 1 October 2021

ER -

Ozturk E, Koseoglu I, Yalcin ME. A Triangular Systolic Array Based Digital Architecture for Computing Eigenvalues of Asymmetric Matrix. In 2021 17th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2021. IEEE Computer Society. 2021. (International Workshop on Cellular Nanoscale Networks and their Applications). doi: 10.1109/CNNA49188.2021.9610808

A Triangular Systolic Array Based Digital Architecture for Computing Eigenvalues of Asymmetric Matrix

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this