×

Matrix computations using quasirandom sequences. (English) Zbl 0978.65030

Vulkov, Lubin (ed.) et al., Numerical analysis and its applications. 2nd international conference, NAA 2000, Rousse, Bulgaria, June 11-15, 2000. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 1988, 552-559 (2001).
Summary: The convergence of the Monte Carlo method for numerical integration can often be improved by replacing pseudorandom numbers (PRNs) with more uniformly distributed numbers known as quasirandom numbers (QRNs). Standard Monte Carlo methods use pseudorandom sequences and provide a convergence rate of \(O(N^{-1/2})\) using \(N\) samples. Quasi-Monte Carlo methods use quasirandom sequences with the resulting convergence rate for numerical integration as good as \(O((\log N)^kN^{-1})\).
In this paper we study the possibility of using QRNs for computing matrix-vector products, solving systems of linear algebraic equations and calculating the extreme eigenvalues of matrices. Several algorithms using the same Markov chains with different random variables are described. We have shown, theoretically and through numerical tests, that the use of quasirandom sequences improves both the magnitude of the error and the convergence rate of the corresponding Monte Carlo methods. Numerical tests are performed on sparse matrices using PRNs and Sobol, Halton, and Faure QRNs.
For the entire collection see [Zbl 0958.00035].

MSC:

65F30 Other matrix algorithms (MSC2010)
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
65C40 Numerical analysis or methods applied to Markov chains
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65C05 Monte Carlo methods
60J22 Computational methods in Markov chains
65C10 Random number generation in numerical analysis
PDFBibTeX XMLCite