Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity

Karaivanova, Aneta. "Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity." Serdica Journal of Computing 4.1 (2010): 57-72. <http://eudml.org/doc/11375>.

@article{Karaivanova2010,
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.* This work is supported by the National Science Fund of Bulgaria under Grant No. D002-146/16.12.2008.},
author = {Karaivanova, Aneta},
journal = {Serdica Journal of Computing},
keywords = {Quasi-Monte Carlo Methods; Matrix Computations; Markov Chains; Quasirandom Sequences; quasi-Monte Carlo methods; matrix computations; Markov chains; quasirandom sequences; numerical examples; systems of linear equations; eigenvalues; matrix inversion; integral equations; convergence; complexity},
language = {eng},
number = {1},
pages = {57-72},
publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},
title = {Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity},
url = {http://eudml.org/doc/11375},
volume = {4},
year = {2010},
}

TY - JOUR
AU - Karaivanova, Aneta
TI - Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity
JO - Serdica Journal of Computing
PY - 2010
PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences
VL - 4
IS - 1
SP - 57
EP - 72
AB - 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.* This work is supported by the National Science Fund of Bulgaria under Grant No. D002-146/16.12.2008.
LA - eng
KW - Quasi-Monte Carlo Methods; Matrix Computations; Markov Chains; Quasirandom Sequences; quasi-Monte Carlo methods; matrix computations; Markov chains; quasirandom sequences; numerical examples; systems of linear equations; eigenvalues; matrix inversion; integral equations; convergence; complexity
UR - http://eudml.org/doc/11375
ER -