Abstract
There are iterative Monte Carlo (MC) methods that can be used for estimating the extreme eigenvalues of large dimensional matrices. The Power MC method allows for finding the approximate maximum eigenvalue of the considered matrix. In the case when we need to estimate the minimum eigenvalue, it is recommended to use the Resolvent MC method. The recent developments of quasi-random sequence generators and their successful application for solving large-scale problems motivate us to investigate the quasi-Monte Carlo (QMC) approaches for solving eigenvalue problems. In this work, we propose a Resolvent QMC algorithm to estimate the minimum eigenvalues of large-scale dimension symmetric matrices. To generate the quasi-random sequences we use BRODA’s Sobol Randomized Sequence Generator (RSG). Numerical experiments were done to investigate the balance between both errors - systematic and stochastic errors, which depend on the power of the resolvent matrix, the parameter controlling the convergence in the iteration process of the Resolvent MC/QMC method, and the number of realizations of the MC/QMC estimator. Numerical results show good scalability in the case of using Sobol sequences on GPU accelerators.
The work of the first author has been partially supported by the National Geoinformation Center (part of National Roadmap of RIs) under grants No. D01-164/28.07.2022 and has also been accomplished with partial support by Grant No. BG05M2OP001-1.001-0003, financed by the Science and Education for Smart Growth Operational Program (2014–2020) and co-financed by the European Union through the European Structural and Investment funds. The work of the other authors was accomplished with the financial support of the MES by Grant No D01-168/28.07.2022 for providing access to e-infrastructure of the NCHDC - part of the Bulgarian National Roadmap on RIs and as well as by grant No 30 from CAF America.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Rotter, I.: A non-Hermitian Hamilton operator and the physics of open quantum systems. J. Phys. A: Math. Theor. 42(No15), 153001 (2009). https://doi.org/10.1088/1751-8113/42/15/153001
Muminov, M.I., Rasulov, T.H.: Embedded eigenvalues of a Hamiltonian in bosonic fock space. Commun. Math. Anal. 17(1), 1–22 (2014)
Golub, G.H., Van Loon, C.F.: Matrix Computations. The Johns Hopkins University Press, Baltimore (1996)
Isaacson, E., Keller, H.B.: Analysis of Numerical Methods. Dover Publications, Mineola; Wiley, New York (1996). ISBN 0-486-68029-0
Alexandrov, V., et al.: On the preconditioned quasi-Monte Carlo algorithm for matrix computations. In: Lirkov, I., Margenov, S., Waśniewski, J. (eds.) LSSC 2015. LNCS, vol. 9374, pp. 163–171. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-26520-9_17
Dimov, I.T., et al.: Robustness and applicability of Markov chain Monte Carlo algorithms for eigenvalue problems. Appl. Math. Modelling 32(8), 1511–1529 (2008). https://doi.org/10.1016/j.apm.2007.04.012
Mascagni, M., Karaivanova, A.: A Monte Carlo approach for finding more than one eigenpair. In: Dimov, I., Lirkov, I., Margenov, S., Zlatev, Z. (eds.) NMA 2002. LNCS, vol. 2542, pp. 123–131. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36487-0_13
Mascagni, M., Karaivanova, A.: Matrix computations using quasirandom sequences. In: Vulkov, L., Yalamov, P., Waśniewski, J. (eds.) NAA 2000. LNCS, vol. 1988, pp. 552–559. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45262-165
Dimov, I., Karaivanova, A.: A power method with monte Carlo iterations. In: Proceeding Recent Advances in Numerical Methods and Applications II, World Scientific, pp. 239–247 (1999). https://doi.org/10.1142/9789814291071_0022
Dimov, I.: Monte Carlo Methods For Applied Scientists. World Scientific, Singapore (2008). ISBN:9812779892
Dimov, I.T., Dimov, T.T., Gurov, T.V.: A new iterative Monte Carlo approach for inverse matrix problem. JCAM 92(1), 15–36 (1998). https://doi.org/10.1016/S0377-0427(98)00043-0
Sobol, I.M., Shukhman, B.V.: Integration with quasirandom sequences: numerical experience. Int. J. Modern Phys. C 6(2), 263–275 (1995)
Sobol, I.M., Asotsky, D., Kreinin, A., Kucherenko, S.: Construction and comparison of high-dimensional Sobol’ generator. WILMOTT Mag. 64–79, 2012 (2011)
Sobol, I.M.: Uniformly distributed sequences with an additional property of uniformity. USSR Comput. Math. Math. Phys. 16(5), 236–242 (1976). https://doi.org/10.1016/0041-5553(76)90154-3
Gurova, S.-M., Karaivanova, A.: Monte Carlo method for estimating eigenvalues using error balancing. In: Lirkov, I., Margenov, S. (eds.) LSSC 2021. LNCS, vol. 13127, pp. 447–455. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-97549-4_51
Faure, H., Lemieux, C.H.: Generalized Halton sequences in 2008: a comparative study. ACM Trans. Model. Comp. Simul. 19(404), 1–31 (2009). https://doi.org/10.1145/1596519.1596520
Joe, S., Kuo, F.Y.: Constructing Sobol sequences with better two-dimensional projections. SIAM J. Sci. Comput. 30(5), 2635–54 (2008)
BRODA’s Sobol RSG. https://broda.co.uk/software.html. Accessed 15 Apr 2023
Basu, K., Owen, A.B.: Transformations and hardy-krause variation. SIAM J. Numer. Anal. 54(3), 1946–1966 (2016). https://doi.org/10.1137/15M1052184
HPC center at IICT: https://ict.acad.bg/?page_id=1229. Accessed 15 Apr 2023
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Gurova, SM., Atanassov, E., Karaivanova, A. (2024). A Resolvent Quasi-Monte Carlo Method for Estimating the Minimum Eigenvalues Using the Error Balancing. In: Lirkov, I., Margenov, S. (eds) Large-Scale Scientific Computations. LSSC 2023. Lecture Notes in Computer Science, vol 13952. Springer, Cham. https://doi.org/10.1007/978-3-031-56208-2_40
Download citation
DOI: https://doi.org/10.1007/978-3-031-56208-2_40
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-56207-5
Online ISBN: 978-3-031-56208-2
eBook Packages: Computer ScienceComputer Science (R0)