Abstract
In this paper we consider bilinear forms of matrix polynomials and show that these polynomials can be used to construct solutions for the problems of solving systems of linear algebraic equations, matrix inversion and finding extremal eigenvalues. An almost Optimal Monte Carlo (MAO) algorithm for computing bilinear forms of matrix polynomials is presented.
Results for the computational costs of a balanced algorithm for computing the bilinear form of a matrix power is presented, i.e., an algorithm for which probability and systematic errors are of the same order, and this is compared with the computational cost for a corresponding deterministic method.
Chapter PDF
Similar content being viewed by others
Keywords
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., Alexandrov, V., Karaivanova, A.: Parallel resolvent Monte Carlo algorithms for linear algebra problems. J. Mathematics and Computers in Simulation 55, 25–35 (2001)
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)
Dimov, I., Karaivanova, A.: A Power Method with Monte Carlo Iterations. In: Iliev, O., Kaschiev, M., Sendov, B.l., Vassilevski, P. (eds.) Recent Advances in Numerical Methods and Applications, pp. 239–247. World Scientific, Singapore (1999)
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)
Dimov, I., Tonev, O.: Monte Carlo Algorithms: Performance Analysis for Some Computer Architectures. Journal of Computational and Applied Mathematics 48, 253–277 (1993)
Dimov, I.: Monte Carlo Algorithms for Linear Problems. Pliska (Studia Mathematica Bulgarica) 13 (2000); Proceedings of the 9th International Summer School on Probability Theory and Mathematical Statistics, Sozopol, pp. 57-77 (1997)
Dimov, I., Karaivanova, A., Yordanova, P.: Monte Carlo Algorithms for calculating eigenvalues. In: Second International Conference on Monte Carlo and Quasi-Monte Carlo methods in scientific computing, University of Salzburg, July 8-12 (1996); Niederreiter, H., Hellekalek, P., Larcher, G., Zinterhof, P. (eds.): Proceedings of MC & QMC 1996. Springer Notes in Statistics, pp. 205–220 (1997)
Knuth, D.: The Art of Computer Programming, 3rd edn. Sorting and Searching, vol. 3. Addison-Wesley, Reading (1997)
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
Weihrauch, C., Dimov, I., Branford, S., Alexandrov, V. (2006). Comparison of the Computational Cost of a Monte Carlo and Deterministic 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_84
Download citation
DOI: https://doi.org/10.1007/11758532_84
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)