Matrix balancing and robust Monte Carlo algorithm for evaluating dominant eigenpair (Q717786)

The need to compute dominant eigenpairs (eigenvalues and eigenvectors) of matrices arises frequently in scientific and engineering applications. On the other side, the matrix balancing has a positive effect on the stability of the algorithms in matrix computations, and the accuracy of the computer solutions. There are many different algorithms used to obtain an eigenpair of a matrix. Many of these algorithms are inefficient when applied to very large structural systems. In the present paper, a new algorithm for obtaining a dominant eigenpair is proposed. Then, the Monte Carlo approach to obtain the dominant eigenpair of matrices with an emphasis on preconditioning implementation of the corresponding algorithm is used. In the Introduction, the problem for the eigenvalues and the eigenvectors of a matrix is put, and a short review of the methods for the work is presented. In Section 2 a concrete Markov chain with constructive and probabilistic details is developed. By using a recursive equation the sequences \(\{W_j\}_{j\geq 0}\) and \(\{\Gamma^i\}_{i\geq 0}\) of random variables are constructed. In Theorem 1, under given assumptions the expectation of the random variable \(\Gamma^{i}\) is calculated. A Monte Carlo method for evaluating the dominant eigenvalues and the corresponding eigenvectors is proposed. In Theorem 2 a sufficient condition, how to minimize the stochastic error for calculating the dominant eigenvalues of the given matrix, by using the Monte Carlo algorithm, is given. In Section 3, under conditions proposed in Theorem 2, the matrix balancing procedure is introduced. In Algorithm 1 the employed balancing algorithm is given. After that, the robust Monte Carlo algorithm, based on the balanced matrix, is developed and given as Algorithm 2. In Section 4 many numerical results, by using the new approach, are presented. It is shown, how to calculate the Monte Carlo relative error. The precision of the computed eigenvalues, without balancing and after applying balancing, are compared. In Section 5 short concluding remarks, that the proposed algorithm for dominant eigenvalues, can be implemented for a large scale of matrices, and that the stochastic error of the Monte Carlo method is reduced, are discussed.