On the Utility of the Multi-Level Algorithm for the Solution of Nearly Completely Decomposable Markov Chains

Abstract

Recently the Multi-Level algorithm was introduced as a general purpose solver for the solution of steady state Markov chains. In this paper we consider the performance of the Multi-Level algorithm for solving Nearly Completely Decomposable (NCD) Markov chains, for which special-purpose interactive aggregation/disaggregation algorithms such as the Koury-McAllister- Stewart (KMS) method have been developed that can exploit the decomposability of the Markov chain. We present experimental results indicating that the general- purpose Multi-Level algorithm is competitive, and can be significantly faster than the special-purpose KMS algorithm when Gauss-Seidel and Gaussian Elimination are used for solving the individual blocks. Markov chains, Multi- level, Numerical solution.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1994
Accession Number
ADA284423

Entities

People

  • Graham Horton
  • Scott T. Leutenegger

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computers
  • Contracts
  • Elimination
  • Engineering
  • Equations
  • Floating Point Operations
  • Information Operations
  • Iterations
  • Markov Chains
  • Mathematics
  • Probability
  • Steady State
  • Terminals

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Cybersecurity.
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)