A Bootstrap Algebraic Multilevel method for Markov Chains

Mathematics – Numerical Analysis

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

16 pages, 7 figures, submitted to SISC April 2010.

Scientific paper

This work concerns the development of an Algebraic Multilevel method for computing stationary vectors of Markov chains. We present an efficient Bootstrap Algebraic Multilevel method for this task. In our proposed approach, we employ a multilevel eigensolver, with interpolation built using ideas based on compatible relaxation, algebraic distances, and least squares fitting of test vectors. Our adaptive variational strategy for computation of the state vector of a given Markov chain is then a combination of this multilevel eigensolver and associated multilevel preconditioned GMRES iterations. We show that the Bootstrap AMG eigensolver by itself can efficiently compute accurate approximations to the state vector. An additional benefit of the Bootstrap approach is that it yields an accurate interpolation operator for many other eigenmodes. This in turn allows for the use of the resulting AMG hierarchy to accelerate the MLE steps using standard multigrid correction steps. The proposed approach is applied to a range of test problems, involving non-symmetric stochastic M-matrices, showing promising results for all problems considered.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

A Bootstrap Algebraic Multilevel method for Markov Chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Bootstrap Algebraic Multilevel method for Markov Chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Bootstrap Algebraic Multilevel method for Markov Chains will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-220511

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.