An official website of the United States government
We investigate the state-of-the-art Lanczos eigensolvers available in the Grid and QUDA libraries. They include Implicitly Restarted Lanczos, Thick-Restart Lanczos, and Block Lanczos. We measure and analyze their performance for the Highly Improved Staggered Quark (HISQ) Dirac operator. We also discuss optimization of Chebyshev acceleration.
more »
« less
Iterative Methods for the Computation of the Perron Vector of Adjacency Matrices
The power method is commonly applied to compute the Perron vector of large adjacency matrices. Blondel et al. [SIAM Rev. 46, 2004] investigated its performance when the adjacency matrix has multiple eigenvalues of the same magnitude. It is well known that the Lanczos method typically requires fewer iterations than the power method to determine eigenvectors with the desired accuracy. However, the Lanczos method demands more computer storage, which may make it impractical to apply to very large problems. The present paper adapts the analysis by Blondel et al. to the Lanczos and restarted Lanczos methods. The restarted methods are found to yield fast convergence and to require less computer storage than the Lanczos method. Computed examples illustrate the theory presented. Applications of the Arnoldi method are also discussed.
more »
« less
- Award ID(s):
- 1720259
- PAR ID:
- 10299785
- Date Published:
- Journal Name:
- Mathematics
- Volume:
- 9
- Issue:
- 13
- ISSN:
- 2227-7390
- Page Range / eLocation ID:
- 1522
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Approximating the action of a matrix function $$f(\vec{A})$$ on a vector $$\vec{b}$$ is an increasingly important primitive in machine learning, data science, and statistics, with applications such as sampling high dimensional Gaussians, Gaussian process regression and Bayesian inference, principle component analysis, and approximating Hessian spectral densities. Over the past decade, a number of algorithms enjoying strong theoretical guarantees have been proposed for this task. Many of the most successful belong to a family of algorithms called \emph{Krylov subspace methods}. Remarkably, a classic Krylov subspace method, called the Lanczos method for matrix functions (Lanczos-FA), frequently outperforms newer methods in practice. Our main result is a theoretical justification for this finding: we show that, for a natural class of \emph{rational functions}, Lanczos-FA matches the error of the best possible Krylov subspace method up to a multiplicative approximation factor. The approximation factor depends on the degree of $f(x)$'s denominator and the condition number of $$\vec{A}$$, but not on the number of iterations $$k$$. Our result provides a strong justification for the excellent performance of Lanczos-FA, especially on functions that are well approximated by rationals, such as the matrix square root.more » « less
-
Abstract Quantum chemistry is a key application area for noisy‐intermediate scale quantum (NISQ) devices, and therefore serves as an important benchmark for current and future quantum computer performance. Previous benchmarks in this field have focused on variational methods for computing ground and excited states of various molecules, including a benchmarking suite focused on the performance of computing ground states for alkali‐hydrides under an array of error mitigation methods. State‐of‐the‐art methods to reach chemical accuracy in hybrid quantum‐classical electronic structure calculations of alkali hydride molecules on NISQ devices from IBM are outlined here. It is demonstrated how to extend the reach of variational eigensolvers with symmetry preserving Ansätze. Next, it is outlined how to use quantum imaginary time evolution and Lanczos as a complementary method to variational techniques, highlighting the advantages of each approach. Finally, a new error mitigation method is demonstrated which uses systematic error cancellation via hidden inverse gate constructions, improving the performance of typical variational algorithms. These results show that electronic structure calculations have advanced rapidly, to routine chemical accuracy for simple molecules, from their inception on quantum computers a few short years ago, and they point to further rapid progress to larger molecules as the power of NISQ devices grows.more » « less
-
We consider the problem of estimating the spectral density of the normalized adjacency matrix of an $$n$$-node undirected graph. We provide a randomized algorithm that, with $$O(n\epsilon^{-2})$$ queries to a degree and neighbor oracle and in $$O(n\epsilon^{-3})$$ time, estimates the spectrum up to $$\epsilon$$ accuracy in the Wasserstein-1 metric. This improves on previous state-of-the-art methods, including an $$O(n\epsilon^{-7})$$ time algorithm from [Braverman et al., STOC 2022] and, for sufficiently small $$\epsilon$$, a $$2^{O(\epsilon^{-1})}$$ time method from [Cohen-Steiner et al., KDD 2018]. To achieve this result, we introduce a new notion of graph sparsification, which we call \emph{nuclear sparsification}. We provide an $$O(n\epsilon^{-2})$$-query and $$O(n\epsilon^{-2})$$-time algorithm for computing $$O(n\epsilon^{-2})$$-sparse nuclear sparsifiers. We show that this bound is optimal in both its sparsity and query complexity, and we separate our results from the related notion of additive spectral sparsification. Of independent interest, we show that our sparsification method also yields the first \emph{deterministic} algorithm for spectral density estimation that scales linearly with $$n$$ (sublinear in the representation size of the graph).more » « less
-
Santhanam, Rahul (Ed.)The class MIP^* of quantum multiprover interactive proof systems with entanglement is much more powerful than its classical counterpart MIP [Babai et al., 1991; Zhengfeng Ji et al., 2020; Zhengfeng Ji et al., 2020]: while MIP = NEXP, the quantum class MIP^* is equal to RE, a class including the halting problem. This is because the provers in MIP^* can share unbounded quantum entanglement. However, recent works [Qin and Yao, 2021; Qin and Yao, 2023] have shown that this advantage is significantly reduced if the provers' shared state contains noise. This paper attempts to exactly characterize the effect of noise on the computational power of quantum multiprover interactive proof systems. We investigate the quantum two-prover one-round interactive system MIP^*[poly,O(1)], where the verifier sends polynomially many bits to the provers and the provers send back constantly many bits. We show noise completely destroys the computational advantage given by shared entanglement in this model. Specifically, we show that if the provers are allowed to share arbitrarily many EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to NEXP = MIP. This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time) [Qin and Yao, 2021]. We also show that this collapse in power is due to the noise, rather than the O(1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP^*[poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fréchet derivatives or which are Lipschitz continuous.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.3390/math9131522
