In‐Memory Eigenvector Computation in Time O(1). (20th May 2020)

• Record Type: Journal Article
• Authors: Sun, Zhong; Pedretti, Giacomo; Ambrosi, Elia; Bricalli, Alessandro; Ielmini, Daniele
• Is Part Of: Advanced intelligent systems. Volume 2:Number 8(2020)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-05-20
• Subjects: eigenvector -- in-memory computing -- O(1) -- resistive memory -- time complexity; Artificial intelligence -- Periodicals; Robotics -- Periodicals; Control theory -- Periodicals; 006.3
• DOI: 10.1002/aisy.202000042
• Languages: English
• ISSNs: 2640-4567

Abstract

Abstract : In‐memory computing with cross‐point resistive memory arrays has gained enormous attention to accelerate the matrix‐vector multiplication in the computation of data‐centric applications. By combining a cross‐point array and feedback amplifiers, it is possible to compute matrix eigenvectors in one step without algorithmic iterations. Herein, time complexity of the eigenvector computation is investigated, based on the feedback analysis of the cross‐point circuit. The results show that the computing time of the circuit is determined by the mismatch degree of the eigenvalues implemented in the circuit, which controls the rising speed of output voltages. For a dataset of random matrices, the time for computing the dominant eigenvector in the circuit is constant for various matrix sizes; namely, the time complexity is O (1). The O (1) time complexity is also supported by simulations of PageRank of real‐world datasets. This work paves the way for fast, energy‐efficient accelerators for eigenvector computation in a wide range of practical applications. Abstract : The time complexity of eigenvector computation with a cross‐point resistive memory array is investigated, based on the feedback analysis of the cross‐point circuit. The results show that the time for computing the dominant eigenvector in the circuit is constant for various matrix sizes; namely, the time complexity is O (1), which is supported by real‐world PageRank simulations as well.