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.
Keywords Monte Carlo algorithms - matrix computations - performance analysis - iterative process
Partially supported by the Bulgarian Ministry of Education and Science, under grant I-1405/2004.