Atlas home || Conferences | Abstracts | about Atlas

Second Conference on Numerical Analysis and Applications
June 11-15, 2000
University of Rousse
Rousse, Bulgaria

Organizers
Plamen Yalamov, Marcin Paprzycki, Lubin Vulkov

View Abstracts
Conference Homepage

Matrix Computations Using Quasirandom Sequences
by
Aneta Karaivanova
Florida State University, Tallahassee, FL
Coauthors: Michael Mascagni (Florida State University)

Matrix Computations Using Quasirandom Sequences

Matrix Computations Using Quasirandom Sequences

Michael Mascagni, Aneta Karaivanova

Abstract

The convergence of Monte Carlo method for numerical integration can often be improved by replacing random numbers (PRN) with more uniformly distributed numbers known as quasi-random (QRN). Standart Monte Carlo methods use pseudo-random sequences and provide a convergence rate of O(N-1/2) using N samples. Quasi-Monte Carlo methods use quasi-random sequences and the resulting convergence rate for numerical integration is O((logN)k)N-1).

In this paper we study the possibility to use quasi-random numbers for computing matrix-vector products, solving systems of linear algebraic equations and calculating the extreme eigenvalues of matrices. Several algorithms using the same Markov chains with different random variables are described. We have shown, theoretically and through numerical tests, that the use of quasirandom sequences improves the convergence rate of the corresponding Monte Carlo methods.

However, the advantages for numerical integration hold for integrals over the unit cube depend on many factors, such as the dimension and smoothness of the integrand, and whether or not the support of the integrand coincides with the unit cube. The advantages for Linear Algebra problems depend on the number of nonzero elements per row and how the matrix elements are "balanced".

Numerical tests are performed on sparse matrices of size 128, 1024, 2000 using PRNs and Sobol, Halton and Faure quasirandom sequences.

Matrix Computations Using Quasirandom Sequences

Date received: January 31, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caeb-55.