More Like this

1. A Fast and Effective Memristor-Based Method for Finding Approximate Eigenvalues and Eigenvectors of Non-negative Matrices

   https://doi.org/10.1109/ISVLSI.2018.00108  

   Wang, Chenghong ; Jalali, Zeinab S. ; Ding, Caiwen ; Wang, Yanzhi ; Soundarajan, Sucheta ( July 2018 , 2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI))

   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(N^3) 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 memristor-based 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(N^2 /Δ) (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. 

   more » « less
2. A universal variational quantum eigensolver for non-Hermitian systems

   https://doi.org/10.1038/s41598-023-49662-5  

   Zhao, Huanfeng ; Zhang, Peng ; Wei, Tzu-Chieh ( December 2023 , Scientific Reports)

   Many quantum algorithms are developed to evaluate eigenvalues for Hermitian matrices. However, few practical approach exists for the eigenanalysis of non-Hermintian ones, such as arising from modern power systems. The main difficulty lies in the fact that, as the eigenvector matrix of a general matrix can be non-unitary, solving a general eigenvalue problem is inherently incompatible with existing unitary-gate-based quantum methods. To fill this gap, this paper introduces a Variational Quantum Universal Eigensolver (VQUE), which is deployable on noisy intermediate scale quantum computers. Our new contributions include: (1) The first universal variational quantum algorithm capable of evaluating the eigenvalues of non-Hermitian matrices—Inspired by Schur’s triangularization theory, VQUE unitarizes the eigenvalue problem to a procedure of searching unitary transformation matrices via quantum devices; (2) A Quantum Process Snapshot technique is devised to make VQUE maintain the potential quantum advantage inherited from the original variational quantum eigensolver—With additional$$O(log_{2}{N})$$$O\left(lo{g}_{2}N\right)$quantum gates, this method efficiently identifies whether a unitary operator is triangular with respect to a given basis; (3) Successful deployment and validation of VQUE on a real noisy quantum computer, which demonstrates the algorithm’s feasibility. We also undertake a comprehensive parametric study to validate VQUE’s scalability, generality, and performance in realistic applications.

    

   more » « less
3. Domain decomposition approaches for accelerating contour integration eigenvalue solvers for symmetric eigenvalue problems

   https://doi.org/10.1002/nla.2154  

   Kalantzis, Vassilis ; Kestyn, James ; Polizzi, Eric ; Saad, Yousef ( February 2018 , Numerical Linear Algebra with Applications)

   This paper discusses techniques for computing a few selected eigenvalue–eigenvector pairs of large and sparse symmetric matrices. A recently developed class of techniques to solve this type of problems is based on integrating the matrix resolvent operator along a complex contour that encloses the interval containing the eigenvalues of interest. This paper considers such contour integration techniques from a domain decomposition viewpoint and proposes two schemes. The first scheme can be seen as an extension of domain decomposition linear system solvers in the framework of contour integration methods for eigenvalue problems, such as FEAST. The second scheme focuses on integrating the resolvent operator primarily along the interface region defined by adjacent subdomains. A parallel implementation of the proposed schemes is described, and results on distributed computing environments are reported. These results show that domain decomposition approaches can lead to reduced run times and improved scalability.

    

   more » « less
4. The random component-wise power method

   https://doi.org/10.1117/12.2530511  

   Teke, Oguzhan ; Vaidyanathan, P. P. ; Lu, Yue M. ; Papadakis, Manos ; Van De Ville, Dimitri ( September 2019 , Proc. SPIE 11138, Wavelets and Sparsity XVIII)

   This paper considers a random component-wise variant of the unnormalized power method, which is similar to the regular power iteration except that only a random subset of indices is updated in each iteration. For the case of normal matrices, it was previously shown that random component-wise updates converge in the mean-squared sense to an eigenvector of eigenvalue 1 of the underlying matrix even in the case of the matrix having spectral radius larger than unity. In addition to the enlarged convergence regions, this study shows that the eigenvalue gap does not directly aect the convergence rate of the randomized updates unlike the regular power method. In particular, it is shown that the rate of convergence is aected by the phase of the eigenvalues in the case of random component-wise updates, and the randomized updates favor negative eigenvalues over positive ones. As an application, this study considers a reformulation of the component-wise updates revealing a randomized algorithm that is proven to converge to the dominant left and right singular vectors of a normalized data matrix. The algorithm is also extended to handle large-scale distributed data when computing an arbitrary rank approximation of an arbitrary data matrix. Numerical simulations verify the convergence of the proposed algorithms under dierent parameter settings. 

   more » « less
5. STABILITY OF GRAPH NEURAL NETWORKS TO RELATIVE PERTURBATIONS

   Gama, F ; Ribeiro, A ; Bruna, J ( July 2020 , Proceedings)

   null (Ed.)

   Graph neural networks (GNNs), consisting of a cascade of layers ap- plying a graph convolution followed by a pointwise nonlinearity, have become a powerful architecture to process signals supported on graphs. Graph convolutions (and thus, GNNs), rely heavily on knowledge of the graph for operation. However, in many practical cases the graph shift operator (GSO) is not known and needs to be estimated, or might change from training time to testing time. In this paper, we are set to study the effect that a change in the underlying graph topology that supports the signal has on the output of a GNN. We prove that graph convolutions with integral Lipschitz filters lead to GNNs whose output change is bounded by the size of the relative change in the topology. Furthermore, we leverage this result to show that the main reason for the success of GNNs is that they are stable architectures capable of dis- criminating features on high eigenvalues, which is a feat that cannot be achieved by linear graph filters (which are either stable or discrimina- tive, but cannot be both). Finally, we comment on the use of this result to train GNNs with increased stability and run experiments on movie recommendation systems. 

   more » « less