Quasi Monte Carlo algorithm for computing smallest and largest generalised eigenvalues

Abstract

The problem of obtaining the smallest and the largest generalised eigenvalues using quasi Monte Carlo algorithm is considered. We first study the results of Dimov and others using three algorithms based on the power method combined with Monte Carlo and quasi Monte Carlo methods for evaluating extremal eigenvalue of real matrices. We present a quasi Monte Carlo algorithm for computing both the smallest and the largest generalised eigenvalues using Sobol, Halton sequences and the rand function in Matlab. We finally compare the efficiency of three employed generators in our algorithm for different pencils. References

• Alexandrov V. N., Efficient parallel Monte Carlo Methods for Matrix Computation, Mathematics and computers in Simulation, Elsevier 47 (1998) 113--122, doi:10.1016/S0378-4754(98)00097-4
• Chi H., Mascagni M. and Warnock T., On the optimal Halton sequence, Mathematics and Computers in Simulation, 70 (2005) 9--21, doi:10.1016/j.matcom.2005.03.004
• Dimov I., Monte Carlo methods for applied scientists, World Scientific Publishing Co., 2008.
• Dimov I., Alexandrov V. and Karaivanova A., Implementation of Monte Carlo Algorithms for Eigenvalue Problem Using MPI, Recent Advances in Parallel Virtual Machine and Message Passing Interface, Springer, 1998.
• Fathi Vajargah B. and Mehrdoust F., New Monte Carlo algorithm for obtaining three dominant eigenvalues, Int. J. Appl. Math. 22 (2009), no. 4, 553--559.
• Kressner D., Numerical Methods for General and Structured Eigenvalue Problems, Springer--Verlag Berlin Heidelberg, 2005.
• Lemieux C., Monte Carlo and Quasi Monte Carlo Sampling, Springer Science, 2009.
• Mascagni M. and A. Karaivanova, A Parallel Quasi Monte Carlo Method for Computing Extremal Eigenvalues, Monte Carlo and Quasi Monte Carlo Methods, Springer, 12 (2002) 369--380.
• Sobol I. M., On quasi Monte Carlo integrations, Mathematics and Computers in Simulation, 47 (1998) 103--112. doi:10.1016/S0378-4754(98)00096-2
• Sobol I. M., Quasi Monte Carlo methods, Progress in Nuclear Energy, 24 (1990) 55--61.