A Multi-Level Solution Algorithm for Steady-State Markov Chains

Abstract

A new iterative algorithm, the multi-level algorithm, for the numerical solution of steady state Markov chains is presented. The method utilizes a set of recursively coarsened representations of the original system to achieve accelerated convergence. It is motivated by multigrid methods, which are widely used for fast solution of partial differential equations. Initial results of numerical experiments are reported, showing significant reductions in computation time, often an order of magnitude or more, relative to the Gauss- Seidel and optimal SOR algorithms for a variety of test problems. The paper also contrasts and compares the multi-level method with the iterative aggregation- disaggregation algorithm of Takahashi.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1993
Accession Number
ADA274630

Entities

People

  • Graham Horton
  • Scott T. Leutenegger

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Boundary Value Problems
  • Computations
  • Convergence
  • Differential Equations
  • Engineering
  • Equations
  • Floating Point Operations
  • Markov Chains
  • Partial Differential Equations
  • Petri Nets
  • Probability
  • Steady State
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Operations Research