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

Serdica Journal of Computing (2010)

- Volume: 4, Issue: 1, page 57-72
- ISSN: 1312-6555

## Access Full Article

top## Abstract

top## How to cite

topKaraivanova, 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.