On-the-fly adaptive smoothed aggregation multigrid for Markov chains. (English) Zbl 1232.65167
Summary: A new adaptive algebraic multigrid scheme is developed for the solution of Markov chains, where the hierarchy of operators is adapted on-the-fly in a setup process that is interlaced with the solution process. The setup process feeds the solution process with improved operators, while the solution process provides the adaptive setup process with better approximations on which to base further-improved operators. The approach is demonstrated using Petrov-Galerkin smoothed aggregation where only the prolongation operator is smoothed, while the restriction remains of low order. Results show that the on-the-fly adaptive scheme can improve the performance of multigrid solvers that require extensive setup computations, in both serial and parallel environments.
MSC:
65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
65C40 | Numerical analysis or methods applied to Markov chains |
60J22 | Computational methods in Markov chains |
65F10 | Iterative numerical methods for linear systems |
65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |