Abstract
In this paper we present error analysis for a Monte Carlo algorithm for evaluating bilinear forms of matrix powers. An almost Optimal Monte Carlo (MAO) algorithm for solving this problem is formulated. Results for the structure of the probability error are presented and the construction of robust and interpolation Monte Carlo algorithms are discussed.
Results are presented comparing the performance of the Monte Carlo algorithm with that of a corresponding deterministic algorithm. The two algorithms are tested on a well balanced matrix and then the effects of perturbing this matrix, by small and large amounts, is studied.
Partially supported by the Bulgarian Ministry of Education and Science, under grant I-1405/2004.
Chapter PDF
Similar content being viewed by others
References
Alexandrov, V., Atanassov, E., Dimov, I.: Parallel Quasi-Monte Carlo Methods for Linear Algebra Problems. Monte Carlo Methods and Applications 10(3-4), 213–219 (2004)
Dimov, I.: Minimization of the Probable Error for Some Monte Carlo methods. In: Proc. Int. Conf. on Mathematical Modeling and Scientific Computation, Albena, Bulgaria, Sofia, pp. 159–170. Publ. House of the Bulgarian Academy of Sciences (1991)
Dimov, I.: Monte Carlo Algorithms for Linear Problems. Pliska (Studia Mathematica Bulgarica) 13, 57–77 (2000)
Dimov, I., Dimov, T., Gurov, T.: A New Iterative Monte Carlo Approach for Inverse Matrix Problem. Journal of Computational and Applied Mathematics 92, 15–35 (1997)
Dimov, I.T., Alexandrov, V.: A New Highly Convergent Monte Carlo Method for Matrix Computations. Mathematics and Computers in Simulation 47, 165–181 (1998)
Dimov, I., Karaivanova, A.: Parallel computations of eigenvalues based on a Monte Carlo approach. Journal of Monte Carlo Method and Applications 4(1), 33–52 (1998)
Golub, G.V., Van Loon, C.F.: Matrix computations, 3rd edn. Johns Hopkins Univ. Press, Baltimore (1996)
Sobol, I.M.: Monte Carlo numerical methods, Nauka, Moscow (1973)
Westlake, J.R.: A Handbook of Numerical matrix Inversion and Solution of Linear Equations. John Wiley & Sons, Inc., New York (1968)
Mascagni, M., Karaivanova, A.: A Parallel Quasi-Monte Carlo Method for Computing Extremal Eigenvalues. In: Monte Carlo and Quasi-Monte Carlo Methods, pp. 369–380. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dimov, I., Alexandrov, V., Branford, S., Weihrauch, C. (2006). Error Analysis of a Monte Carlo Algorithm for Computing Bilinear Forms of Matrix Powers. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds) Computational Science – ICCS 2006. ICCS 2006. Lecture Notes in Computer Science, vol 3993. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758532_83
Download citation
DOI: https://doi.org/10.1007/11758532_83
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34383-7
Online ISBN: 978-3-540-34384-4
eBook Packages: Computer ScienceComputer Science (R0)