BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2010 >
Volume 4 Number 1 >

Please use this identifier to cite or link to this item:

Title: Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity
Authors: Karaivanova, Aneta
Keywords: 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.
ISSN: 1312-6555
Appears in Collections:Volume 4 Number 1

Files in This Item:

File Description SizeFormat
sjc115-vol4-num1-2010.pdf173.21 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License DSpace Software Copyright © 2002-2009  The DSpace Foundation - Feedback