SIIA Público

Título del libro: On Monte Carlo Hybrid Methods For Linear Algebra

Autores UNAM:
OSCAR ALEJANDRO ESQUIVEL FLORES;

Autores externos:

Idioma:

Año de publicación:
2016

Palabras clave:

Algebra; Inverse problems; Iterative methods; Large scale systems; Linear algebra; Linear equations; Markov processes; Monte Carlo methods; Stochastic systems, Computational resources; Hybrid method; Markov chain Monte Carlo method; Matrix inversions; Parallelizations; Preconditioners; System of linear algebraic equations; Systems of linear algebraic equations, Matrix algebra

Resumen:

This paper presents an enhanced hybrid (e.g. stochastic/deterministic) method for Linear Algebra based on bulding an efficient stochastic s and then solving the corresponding System of Linear Algebraic Equations (SLAE) by applying an iterative method. This is a Monte Carlo preconditioner based on Markov Chain Monte Carlo (MCMC) methods to compute a rough approximate matrix inverse first. The above Monte Carlo preconditioner is further used to solve systems of linear algebraic equations thus delivering hybrid stochastic/deterministic algorithms. The advantage of the proposed approach is that the sparse Monte Carlo matrix inversion has a computational complexity linear of the size of the matrix, it is inherently parallel and thus can be obtained very efficiently for large matrices and can be used also as an efficient preconditioner while solving systems of linear algebraic equations. Several improvements, as well as the mixed MPI/OpenMP implementation, are carried out that enhance the scalability of the method and the efficient use of computational resources. A set of different test matrices from several matrix market collections were used to show the consistency of these improvements. © 2016 IEEE.

Entidades citadas de la UNAM: