Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/1580

 Title: Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity Authors: Karaivanova, Aneta Keywords: Quasi-Monte Carlo MethodsMatrix ComputationsMarkov ChainsQuasirandom 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. URI: http://hdl.handle.net/10525/1580 ISSN: 1312-6555 Appears in Collections: Volume 4 Number 1

Files in This Item:

File Description SizeFormat