Accession Number : ADA325603
Title : On the Multilevel Solution Algorithm for Markov Chains.
Descriptive Note : Contractor rept.,
Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA
Personal Author(s) : Horton, Graham
PDF Url : ADA325603
Report Date : MAR 1997
Pagination or Media Count : 25
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.
Descriptors : *ALGORITHMS, *MARKOV PROCESSES, MATHEMATICAL MODELS, QUEUEING THEORY, APPROXIMATION(MATHEMATICS), RECURSIVE FUNCTIONS, SYSTEMS ANALYSIS, OPERATORS(MATHEMATICS), APPLIED MATHEMATICS, GALERKIN METHOD.
Subject Categories : Operations Research
Statistics and Probability
Distribution Statement : APPROVED FOR PUBLIC RELEASE