®®®® SIIA Público

Título del libro: Proceedings Of Scala 2015: 6th Workshop On Latest Advances In Scalable Algorithms For Large-Scale Systems - Held In Conjunction With Sc 2015: The International Conference For High Performance Computing, Networking, Storage And Analysis
Título del capítulo: On efficient monte carlo preconditioners and hybrid Monte Carlo methods for linear algebra

Autores UNAM:
OSCAR ALEJANDRO ESQUIVEL FLORES;
Autores externos:

Idioma:
Inglés
Año de publicación:
2015
Palabras clave:

Algebra; Inverse problems; Iterative methods; Large scale systems; Linear algebra; Linear equations; Markov processes; Matrix algebra; Stochastic systems; Hybrid algorithms; Hybrid Monte-Carlo methods; Linear algebra problems; Linear-algebraic; Markov chain Monte Carlo method; Matrix inversions; Preconditioners; Systems of linear algebraic equations; Monte Carlo methods


Resumen:

An enhanced version of a stochastic SParse Approximate In- verse (SPAI) preconditioner for general matrices is presented in this paper. This is a Monte Carlo preconditioner based on Markov Chain Monte Carlo (MCMC) methods to compute a rough approximate matrix inverse first, which can further be optimized by an iterative filter process and a parallel refine- ment, to enhance the accuracy of the inverse and the precon- ditioner respectively. The above Monte Carlo preconditioner is further used to solve systems of linear algebraic equa- tions thus delivering hybrid stochastic/deterministic algo- rithms. 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. Com- putational experiments on the Monte Carlo preconditioners and the hybrid algorithms using BiCGSTAB and GMRES as SLAEs solvers are presented and the results are compared to those of MSPAI (parallel and optimized version of the deter- ministic SPAI) and combined MSPAI and BiCGSTAB and GMRES approaches to solve SLAEs. The experiment are carried out on classes of matrices from the matrix market and show the efficiency of the proposed approach. © 2015 ACM.


Entidades citadas de la UNAM: