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