On the Stochastic Power Algorithms for Estimating the Maximum Eigenvalue of Symmetric Matrices
Open Access
- 29 September 2025
- journal article
- Published by Universal Wiser Publisher Pte. Ltd in Contemporary Mathematics
- p. 7223-7249
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.Keywords
This publication has 36 references indexed in Scilit:
- On Monte Carlo and Quasi-Monte Carlo for Matrix Computations2018
- Construction and Comparison of High-Dimensional Sobol' GeneratorsWilmott, 2011
- A Parallel Quasi-Monte Carlo Method for Computing Extremal Eigenvalues2002
- Scrambling Sobol' and Niederreiter–Xing PointsJournal of Complexity, 1998
- On theL2-Discrepancy for Anchored BoxesJournal of Complexity, 1998
- Quasi-Monte Carlo IntegrationJournal of Computational Physics, 1995
- Uniform random number generationAnnals of Operations Research, 1994
- Sequential monte carlo techniques for the solution of linear systemsJournal of Scientific Computing, 1994
- Low-discrepancy and low-dispersion sequencesJournal of Number Theory, 1988
- On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integralsNumerische Mathematik, 1960