The next meeting of the INFORMATION MODELING Seminar
will be held on October 4, 2018, at 14:00 in Room 578 of IMI. A talk on:
A New Monte Carlo Algorithm for Linear Algebraic Systems Based on the “Walk on Equations” Algorithm
will be delivered by Assist. Prof. Dr. Venelin Todorov, IMI – BAS.
Everybody is invited.
Abstract. Many scientific and engineering applications are based on the problems of solving systems of linear algebraic equations. The computation time for very large problems, or for finding solutions in real-time, can be prohibitive and this prevents the use of many established algorithms. Monte Carlo algorithms give statistical estimates of the required solution, by performing random sampling of a random variable, whose mathematical expectation is the desired solution.
A new Monte Carlo algorithm for solving systems of Linear Algebraic equations is presented and studied. The algorithm is based on the recently developed “Walk on Equations” Monte Carlo method based on a non-discounted sum of an absorbed random walk. Several techniques like simultaneous scoring or the sequential Monte Carlo method are applied to improve the basic algorithm. The algorithm is optimized by choosing the appropriate values for the relaxation parameters which leads to dramatic reduction in time and lower relative errors for a given number of iterations. The algorithm is used for evaluating all the components of the solution of real valued systems.
Numerical tests are performed for examples with sparse and dense matrices of different size and on a system coming from a finite element approximation of a problem describing a beam structure in constructive mechanics. Comparisons with standard deterministic or Monte Carlo algorithms are also done. The prior behavior of the proposed Monte Carlo algorithm does not depend on the matrix density. The advantages of the algorithm can be observed especially for larger matrix size.
Due to the optimization techniques it gives superior results to the standard “Walk on Equations” method and it is established as one of the fastest and accurate Monte Carlo algorithms for solving systems of linear algebraic equations.