A fast and effective memristor-based method for finding approximate eigenvalues and eigenvectors of non-negative matrices

Chenghong Wang, Zeinab S. Jalali, Caiwen Ding, Yanzhi Wang, Sucheta Soundarajan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Throughout many scientific and engineering fields, including control theory, quantum mechanics, advanced dynamics, and network theory, a great many important applications rely on the spectral decomposition of matrices. Traditional methods such as the power iteration method, Jacobi eigenvalue method, and QR decomposition are commonly used to compute the eigenvalues and eigenvectors of a square and symmetric matrix. However, these methods suffer from certain drawbacks: in particular, the power iteration method can only find the leading eigen-pair (i.e., the largest eigenvalue and its corresponding eigenvector), while the Jacobi and QR decomposition methods face significant performance limitations when facing with large scale matrices. Typically, even producing approximate eigenpairs of a general square matrix requires at least O(N3) time complexity, where N is the number of rows of the matrix. In this work, we exploit the newly developed memristor technology to propose a low-complexity, scalable memristorbased method for deriving a set of dominant eigenvalues and eigenvectors for real symmetric non-negative matrices. The time complexity for our proposed algorithm is O(N2/Δ) (where Δ governs the accuracy). We present experimental studies to simulate the memristor-supporting algorithm, with results demonstrating that the average error for our method is within 4%, while its performance is up to 1.78X better than traditional methods.

Original languageEnglish (US)
Title of host publicationProceedings - 2018 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018
PublisherIEEE Computer Society
Pages563-568
Number of pages6
Volume2018-July
ISBN (Print)9781538670996
DOIs
StatePublished - Aug 7 2018
Event17th IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018 - Hong Kong, Hong Kong
Duration: Jul 9 2018Jul 11 2018

Other

Other17th IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018
CountryHong Kong
CityHong Kong
Period7/9/187/11/18

Fingerprint

Memristors
Eigenvalues and eigenfunctions
Decomposition
Quantum theory
Circuit theory
Control theory

Keywords

  • Eigen value
  • Memristor
  • Non negative marices

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Cite this

Wang, C., Jalali, Z. S., Ding, C., Wang, Y., & Soundarajan, S. (2018). A fast and effective memristor-based method for finding approximate eigenvalues and eigenvectors of non-negative matrices. In Proceedings - 2018 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018 (Vol. 2018-July, pp. 563-568). [8429429] IEEE Computer Society. https://doi.org/10.1109/ISVLSI.2018.00108

A fast and effective memristor-based method for finding approximate eigenvalues and eigenvectors of non-negative matrices. / Wang, Chenghong; Jalali, Zeinab S.; Ding, Caiwen; Wang, Yanzhi; Soundarajan, Sucheta.

Proceedings - 2018 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018. Vol. 2018-July IEEE Computer Society, 2018. p. 563-568 8429429.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Wang, C, Jalali, ZS, Ding, C, Wang, Y & Soundarajan, S 2018, A fast and effective memristor-based method for finding approximate eigenvalues and eigenvectors of non-negative matrices. in Proceedings - 2018 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018. vol. 2018-July, 8429429, IEEE Computer Society, pp. 563-568, 17th IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018, Hong Kong, Hong Kong, 7/9/18. https://doi.org/10.1109/ISVLSI.2018.00108
Wang C, Jalali ZS, Ding C, Wang Y, Soundarajan S. A fast and effective memristor-based method for finding approximate eigenvalues and eigenvectors of non-negative matrices. In Proceedings - 2018 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018. Vol. 2018-July. IEEE Computer Society. 2018. p. 563-568. 8429429 https://doi.org/10.1109/ISVLSI.2018.00108
Wang, Chenghong ; Jalali, Zeinab S. ; Ding, Caiwen ; Wang, Yanzhi ; Soundarajan, Sucheta. / A fast and effective memristor-based method for finding approximate eigenvalues and eigenvectors of non-negative matrices. Proceedings - 2018 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018. Vol. 2018-July IEEE Computer Society, 2018. pp. 563-568
@inproceedings{6ea8d8eccdcf4ffe8f8e626e59562d42,
title = "A fast and effective memristor-based method for finding approximate eigenvalues and eigenvectors of non-negative matrices",
abstract = "Throughout many scientific and engineering fields, including control theory, quantum mechanics, advanced dynamics, and network theory, a great many important applications rely on the spectral decomposition of matrices. Traditional methods such as the power iteration method, Jacobi eigenvalue method, and QR decomposition are commonly used to compute the eigenvalues and eigenvectors of a square and symmetric matrix. However, these methods suffer from certain drawbacks: in particular, the power iteration method can only find the leading eigen-pair (i.e., the largest eigenvalue and its corresponding eigenvector), while the Jacobi and QR decomposition methods face significant performance limitations when facing with large scale matrices. Typically, even producing approximate eigenpairs of a general square matrix requires at least O(N3) time complexity, where N is the number of rows of the matrix. In this work, we exploit the newly developed memristor technology to propose a low-complexity, scalable memristorbased method for deriving a set of dominant eigenvalues and eigenvectors for real symmetric non-negative matrices. The time complexity for our proposed algorithm is O(N2/Δ) (where Δ governs the accuracy). We present experimental studies to simulate the memristor-supporting algorithm, with results demonstrating that the average error for our method is within 4{\%}, while its performance is up to 1.78X better than traditional methods.",
keywords = "Eigen value, Memristor, Non negative marices",
author = "Chenghong Wang and Jalali, {Zeinab S.} and Caiwen Ding and Yanzhi Wang and Sucheta Soundarajan",
year = "2018",
month = "8",
day = "7",
doi = "10.1109/ISVLSI.2018.00108",
language = "English (US)",
isbn = "9781538670996",
volume = "2018-July",
pages = "563--568",
booktitle = "Proceedings - 2018 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018",
publisher = "IEEE Computer Society",
address = "United States",

}

TY - GEN

T1 - A fast and effective memristor-based method for finding approximate eigenvalues and eigenvectors of non-negative matrices

AU - Wang, Chenghong

AU - Jalali, Zeinab S.

AU - Ding, Caiwen

AU - Wang, Yanzhi

AU - Soundarajan, Sucheta

PY - 2018/8/7

Y1 - 2018/8/7

N2 - Throughout many scientific and engineering fields, including control theory, quantum mechanics, advanced dynamics, and network theory, a great many important applications rely on the spectral decomposition of matrices. Traditional methods such as the power iteration method, Jacobi eigenvalue method, and QR decomposition are commonly used to compute the eigenvalues and eigenvectors of a square and symmetric matrix. However, these methods suffer from certain drawbacks: in particular, the power iteration method can only find the leading eigen-pair (i.e., the largest eigenvalue and its corresponding eigenvector), while the Jacobi and QR decomposition methods face significant performance limitations when facing with large scale matrices. Typically, even producing approximate eigenpairs of a general square matrix requires at least O(N3) time complexity, where N is the number of rows of the matrix. In this work, we exploit the newly developed memristor technology to propose a low-complexity, scalable memristorbased method for deriving a set of dominant eigenvalues and eigenvectors for real symmetric non-negative matrices. The time complexity for our proposed algorithm is O(N2/Δ) (where Δ governs the accuracy). We present experimental studies to simulate the memristor-supporting algorithm, with results demonstrating that the average error for our method is within 4%, while its performance is up to 1.78X better than traditional methods.

AB - Throughout many scientific and engineering fields, including control theory, quantum mechanics, advanced dynamics, and network theory, a great many important applications rely on the spectral decomposition of matrices. Traditional methods such as the power iteration method, Jacobi eigenvalue method, and QR decomposition are commonly used to compute the eigenvalues and eigenvectors of a square and symmetric matrix. However, these methods suffer from certain drawbacks: in particular, the power iteration method can only find the leading eigen-pair (i.e., the largest eigenvalue and its corresponding eigenvector), while the Jacobi and QR decomposition methods face significant performance limitations when facing with large scale matrices. Typically, even producing approximate eigenpairs of a general square matrix requires at least O(N3) time complexity, where N is the number of rows of the matrix. In this work, we exploit the newly developed memristor technology to propose a low-complexity, scalable memristorbased method for deriving a set of dominant eigenvalues and eigenvectors for real symmetric non-negative matrices. The time complexity for our proposed algorithm is O(N2/Δ) (where Δ governs the accuracy). We present experimental studies to simulate the memristor-supporting algorithm, with results demonstrating that the average error for our method is within 4%, while its performance is up to 1.78X better than traditional methods.

KW - Eigen value

KW - Memristor

KW - Non negative marices

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

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

U2 - 10.1109/ISVLSI.2018.00108

DO - 10.1109/ISVLSI.2018.00108

M3 - Conference contribution

AN - SCOPUS:85052135780

SN - 9781538670996

VL - 2018-July

SP - 563

EP - 568

BT - Proceedings - 2018 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2018

PB - IEEE Computer Society

ER -