Quasi-Monte Carlo Methods Matrix Computations Markov Chains Quasirandom Sequences
Issue Date:
2010
Publisher:
Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Journal of Computing, Vol. 4, No 1, (2010), 57p-72p
Abstract:
We present quasi-Monte Carlo analogs of Monte Carlo methods
for some linear algebra problems: solving systems of linear equations,
computing extreme eigenvalues, and matrix inversion. Reformulating the
problems as solving integral equations with a special kernels and domains
permits us to analyze the quasi-Monte Carlo methods with bounds from
numerical integration. Standard Monte Carlo methods for integration 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((logN)^k)N^(−1)). 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
considered Monte Carlo methods. We also analyze the complexity of considered
quasi-Monte Carlo algorithms and compare them to the complexity
of the analogous Monte Carlo and deterministic algorithms.