|
First proposed by von Neumann and Ulam, Monte Carlo methods (MCMs) for solving
linear algebra problems have been known since the middle of the last century.
They give statistical estimates for the elements of the inverse of a matrix
or for components of the solution vector of a linear system by performing
random sampling of a certain chance variable whose expected value is the
desired solution. Perhaps the first application of MCMs in linear algebra
appeared in a paper by Forsythe and Leibler in 1950. In the following years
significant contributions were made, especially by Wasow, Curtiss, Halton,
Hammersley and Handscomb and Sobol'. These methods were recognized as useful
in the following situations: when obtaining a quick rough estimate of
solution, which will then be refined by other methods; when the problem is
too large or too intricate for any other treatment; when just one component
of the solution vector or one element of the inverse matrix is desired.
There has been renewed interest in MCMs in recent times, the primary reason for this is the efficiency of parallel MCMs in the presence of high communication costs. The second reason for the recent interest in MCMs is that the methods have evolved significantly since the early days. Much of the effort in the development of Monte Carlo methods has been in the construction of variance reduction techniques which speed up the computation by reducing the the rate of convergence of crude MCM, which is $O(N^{-1/2})$. An alternative approach to acceleration is to change the type of random sequence, and hence improve the behavior with N. Quasi-Monte Carlo methods (QMCMs) use quasirandom (also known as low-discrepancy) sequences instead of pseudorandom sequences, with the resulting convergence rate for numerical integration being as good as $O((logN)^k N^{-1})$. The first results of using QMCMs for linear algebra problems were presented by Mascagni and Karaivanova in 2001. Quasi-Monte Carlo methods often include standard approaches for variance reduction. The fundamental feature underlying all QMCMs, however, is the use of a quasirandom sequence. In this paper the convergence and the complexity of quasi-Monte Carlo methods for estimating the solution of systems of linear algebraic equations (SLAE), inverting of matrices and finding extremal eigenvalues are studied when quasirandom sequences are used. Numerical experiments with test sparse matrices are performed using different quasirandom number (QRN) sequences. The results indicate that for all of the considered problems improvements in both the magnitude of the error and the convergence rate can be achieved using QRNs in place of pseudorandom numbers. Moreover, the excellent parallel efficiency of MCMs is well preserved using QRNs. |