Controlled precision QUBO-based algorithm to compute eigenvectors of symmetric matrices

Benjamin Krakoff; Susan M Mniszewski; Christian F A Negre

doi:10.1371/journal.pone.0267954

Controlled precision QUBO-based algorithm to compute eigenvectors of symmetric matrices

PLoS One. 2022 May 9;17(5):e0267954. doi: 10.1371/journal.pone.0267954. eCollection 2022.

Authors

Benjamin Krakoff¹, Susan M Mniszewski², Christian F A Negre³

Affiliations

¹ Department of Mathematics, University of Michigan, Ann Arbor, Michigan, United States of America.
² Computer, Computational, and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, New Mexico, United States of America.
³ Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico, United States of America.

Abstract

We describe an algorithm to compute the extremal eigenvalues and corresponding eigenvectors of a symmetric matrix which is based on solving a sequence of Quadratic Binary Optimization problems. This algorithm is robust across many different classes of symmetric matrices; It can compute the eigenvector/eigenvalue pair to essentially any arbitrary precision, and with minor modifications, can also solve the generalized eigenvalue problem. Performance is analyzed on small random matrices and selected larger matrices from practical applications.

Publication types

Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

Algorithms*

Grants and funding

The study was supported by National Science Foundation. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.