Towards Monte Carlo preconditioning approach and hybrid Monte Carlo algorithms for Matrix Computations

详细信息    查看全文

• 作者：Vassil Alexandrov^a ; ^b ; ^{vassil.alexandrov@bsc.es" class="auth_mail" title="E-mail the corresponding author} ; Oscar A. Esquivel-Flores^a ; ^c ; ^{oscar.esquivel@bsc.es" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Monte Carlo algorithms for linear algebra problems ; Monte Carlo preconditioners ; Parallel algorithms
• 刊名：Computers & Mathematics with Applications
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：70
• 期：11
• 页码：2709-2718
• 全文大小：662 K

文摘

An enhanced version of a stochastic SParse Approximate Inverse (SPAI) preconditioner for general matrices is presented in this paper. This method is used in contrast to the standard deterministic preconditioners computed by the Modified SParse Approximate Inverse Preconditioner (MSPAI). Thus we present a Monte Carlo preconditioner that relies on the use of 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 refinement, to enhance the accuracy of the inverse and the preconditioner respectively. The advantage of the proposed approach is that finding 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. The behaviour of the proposed algorithm is studied and its performance measured, evaluated and compared with MSPAI.