Time Complexity of In-Memory Solution of Linear Systems
| Autor: | Giacomo Pedretti, Elia Ambrosi, Daniele Ielmini, Piergiulio Mannocci, Zhong Sun, Alessandro Bricalli |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
MathematicsofComputing_NUMERICALANALYSIS Computer Science - Emerging Technologies Computational Complexity (cs.CC) Topology 01 natural sciences law.invention Matrix (mathematics) law 0103 physical sciences FOS: Mathematics Mathematics - Numerical Analysis Electrical and Electronic Engineering Coefficient matrix Time complexity Eigenvalues and eigenvectors Mathematics Sparse matrix 010302 applied physics Covariance matrix Linear system Numerical Analysis (math.NA) Electronic Optical and Magnetic Materials Computer Science - Computational Complexity Emerging Technologies (cs.ET) Electrical network |
| Zdroj: | IEEE Transactions on Electron Devices |
| Popis: | In-memory computing with crosspoint resistive memory arrays has been shown to accelerate data-centric computations such as the training and inference of deep neural networks, thanks to the high parallelism endowed by physical rules in the electrical circuits. By connecting crosspoint arrays with negative feedback amplifiers, it is possible to solve linear algebraic problems such as linear systems and matrix eigenvectors in just one step. Based on the theory of feedback circuits, we study the dynamics of the solution of linear systems within a memory array, showing that the time complexity of the solution is free of any direct dependence on the problem size N, rather it is governed by the minimal eigenvalue of an associated matrix of the coefficient matrix. We show that, when the linear system is modeled by a covariance matrix, the time complexity is O(logN) or O(1). In the case of sparse positive-definite linear systems, the time complexity is solely determined by the minimal eigenvalue of the coefficient matrix. These results demonstrate the high speed of the circuit for solving linear systems in a wide range of applications, thus supporting in-memory computing as a strong candidate for future big data and machine learning accelerators. Comment: Accepted by IEEE Trans. Electron Devices. The authors thank Scott Aaronson for helpful discussion about time complexity |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|