On the Multilevel Solution Algorithm for Markov Chains.

Abstract

We discuss the recently introduced multilevel algorithm for the steady-state solution of Markov chains. The method is based on an aggregation principle which is well established in the literature and features a multiplicative coarse-level correction. Recursive application of the aggregation principle which uses an operator-dependent coarsening yields a multi-level method which has been shown experimentally to give results significantly faster than the typical methods currently in use. When cast as a multigrid-like method, the algorithm is seen to be a Galerkin-Full Approximation Scheme with a solution-dependent prolongation operator. Special properties of this prolongation lead to the cancellation of the computationally intensive terms of the coarse-level equations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1997
Accession Number
ADA325603

Entities

People

  • Graham Horton

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Fluid Dynamics
  • Computational Science
  • Computer Science
  • Computers
  • Differential Equations
  • Equations
  • Fluid Mechanics
  • Markov Chains
  • Mathematics
  • Operating Systems
  • Operations Research
  • Partial Differential Equations
  • Petri Nets
  • Probability
  • Standards
  • Stochastic Processes

Readers

  • Computational Fluid Dynamics (CFD)
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Statistical inference.