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

1 Scopus citations

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

Keywords

  • Eigen value
  • Memristor
  • Non negative marices

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'A fast and effective memristor-based method for finding approximate eigenvalues and eigenvectors of non-negative matrices'. Together they form a unique fingerprint.

Cite this