A direct projection method for Markov chains
type: Item
instance of: scholarly article
title: A direct projection method for Markov chains
zbMATH Open document ID: 1062.65011
author: Michele Benzi
published in: Linear Algebra and its Applications
publication date: 2004-08-04T00:00:00Z
review text: Let \(P\) be an \(n\times n\) transition probability matrix of a finite ergodic Markov chain. The author explains how the direct method of \textit{E. W. Purcell} [J. Math. Phys. 32, 180--183 (1953; Zbl 0051.35303)] based on oblique projections can be used to find the stationary distribution vector, i.e., the unique row vector \(\pi=(\pi_ 1,\ldots,\pi_ n)\) satisfying \(\pi=\pi P\), \(\pi>0\), \(\sum_ i\pi_ i=1\). The method can be also used for computation of the group inverse of the generator matrix and for updating the latter and stationary vector after a one-row change of the transition matrix. The relationship between this method and Gaussian elimination method is exploited to develop a more stable, GTH-like variant [cf. \textit{W. K. Grassmann, M. I. Taksar}, and \textit{D. P. Heyman}, Oper. Res. 33, 1107--1116 (1985; Zbl 0576.60083)] that can handle nearly uncoupled systems and other situations where the original algorithm fails.
reviewed by: Vigirdas Mackevičius
Mathematics Subject Classification ID: 65C40
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 60J22
zbMATH DE Number: 2081255
zbMATH Keywords: finite Markov chains
zbMATH Keywords: stationary vector
zbMATH Keywords: Purcell's method
zbMATH Keywords: Gaussian elimination method
zbMATH Keywords: generalized inverses
zbMATH Keywords: GTH algorithm
zbMATH Keywords: Projections
zbMATH Keywords: Direct solution method
zbMATH Keywords: Rank-one updates
zbMATH Keywords: Nearly uncoupled chains
MaRDI profile type: Publication
full work available at URL: j.laa.2003.12.019
OpenAlex ID: W2085455895
cites work: Perturbation results for nearly uncoupled Markov chains with applications to iterative methods
cites work: A Direct Projection Method for Sparse Linear Systems
cites work: A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient Method
cites work: A Sparse Approximate Inverse Preconditioner for Nonsymmetric Linear Systems
cites work: A parallel solver for large-scale Markov chains
cites work: Q3943082
cites work: Q3207128
cites work: Parallel algorithms of the Purcell method for direct solution of linear systems
cites work: Q4144754
cites work: On the Effects of Using the Grassmann–Taksar–Heyman Method in Iterative Aggregation–Disaggregation
cites work: Q3849175
cites work: Q4421359
cites work: NOTES ON THE SOLUTION OF ALGEBRAIC LINEAR SIMULTANEOUS EQUATIONS
cites work: Solution of Homogeneous Systems of Linear Equations Arising from Compartmental Models
cites work: Sensitivity of the stationary distribution vector for an ergodic Markov chain
cites work: LU decompositions of generalized diagonally dominant matrices
cites work: Updating $LU$ Factorizations for Computing Stationary Distributions
cites work: Using the QR Factorization and Group Inversion to Compute, Differentiate, and Estimate the Sensitivity of Stationary Probabilities for Markov Chains
cites work: Regenerative Analysis and Steady State Distributions for Markov Chains
cites work: Methods of conjugate gradients for solving linear systems
cites work: Q5687211
cites work: Q5543004
cites work: Stationary distributions of perturbed Markov chains
cites work: Uniform Stability of Markov Chains
cites work: Generalized Inversion of Modified Matrices
cites work: The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains
cites work: Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems
cites work: Sensitivity of the Stationary Distribution of a Markov Chain
cites work: Updating finite markov chains by using techniques of group matrix inversion
cites work: Q5840814
cites work: Entrywise perturbation theory and error analysis for Markov chains
cites work: Relative-error bounds for the LU decomposition via the GTH algorithm
cites work: Computation of the stationary distribution of a markov chain
cites work: The Vector Method of Solving Simultaneous Linear Equations
cites work: Conjugate direction methods for solving systems of linear equations
cites work: Q4281294
cites work: On a direct method for the solution of nearly uncoupled Markov chains
cites work: Q4324960
cites work: Perturbations of countable Markov chains and processes
cites work: Q4758117
cites work: On the Sensitivity of the Solution of Nearly Uncoupled Markov Chains
DOI: 10.1016/J.LAA.2003.12.019
description: scientific article; zbMATH DE number 2081255