On the Stochastic Power Algorithms for Estimating the Maximum Eigenvalue of Symmetric Matrices

Abstract

Estimating the largest eigenvalue of large symmetric matrices is a critical problem in numerical linear algebra, with wide-ranging applications in science and engineering. Classical iterative methods, such as the Power method, are often computationally expensive or impractical for high-dimensional problems. To address this, we investigate two stochastic methods, Power Monte Carlo (PMC) and Power Quasi-Monte Carlo (PQMC), which integrate Markov chain-based simulations with classical Power iterations to estimate the maximum eigenvalue. These methods are designed to manage both systematic error (from iteration truncation) and stochastic error (from probabilistic sampling), enabling efficient eigenvalue computation even for large matrices. A main contribution of this study is the precise description of the methodology for constructing Almost Optimal PMC and PQMC algorithms, which can cover a broad class of symmetric matrices, including both sparse and dense structures. The algorithms employ a special choice of transition density matrices in constructing the Markov chain, which leads to a significantly reduced variance. Numerical experiments demonstrate that these algorithms outperform classical PMC/PQMC approaches in accuracy and computational complexity, particularly when using robust random number generators and low-discrepancy sequences. They demonstrate that it is vital to find the right balance between the number of steps in the Markov chain and the number of its simulations. Our findings provide new insights into the design of efficient stochastic algorithms for high-dimensional matrix problems and establish a foundation for further optimization and scalability.