Exact algorithms for singular tridiagonal systems with applications to Markov chains
divide-and-conquer algorithmirreducible tridiagonal matrixMarkov chainsmatrix partitioningoverflow queuing networkrandom walkssingular linear systemsteady state probability distributionssuccessive matrix decomposition
Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational methods in Markov chains (60J22) Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20) Numerical analysis or methods applied to Markov chains (65C40) Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50)
The authors propose two algorithms for the exact solution of a singular linear system \(Tp=0\), where \(T\in{\mathbb R}^{n\times n}\) is an irreducible tridiagonal singular M-matrix with column sums equal to zero. The idea of the first algorithm is based on stochastic complementation [cf. \textit{C. D. Meyer}, SIAM Rev. 31, No. 2, 240--272 (1989; Zbl 0685.65129)] and leads to a divide-and-conquer algorithm by successive matrix decomposition. The second algorithm also uses matrix partitioning to reduce the solution to the solution of a given number of subproblems which can then be solved independently of each other. There are two applications given in the paper; one is finding the steady state probability distribution vector for a random walk problem, while the second application is to calculate an approximative solution of a 2-queue overflow network.
- Algorithms for finding steady state probabilities for some special classes of finite state Markov chains
- An algorithmic approach for a special class of Markov chains
- Further Comparisons of Direct Methods for Computing Stationary Distributions of Markov Chains
- scientific article; zbMATH DE number 278843
- scientific article; zbMATH DE number 729460
- A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
- A note on the recursive decoupling method for solving tridiagonal linear systems
- A Parallel Method for Tridiagonal Equations
- An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations
- Circulant Preconditioners for Markov-Modulated Poisson Processes and Their Applications to Manufacturing Systems
- Circulant preconditioners for stochastic automata networks
- Divide and conquer: A parallel algorithm for the solution of a tridiagonal linear system of equations
- scientific article; zbMATH DE number 1576689 (Why is no real title available?)
- scientific article; zbMATH DE number 3760340 (Why is no real title available?)
- scientific article; zbMATH DE number 729460 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Iterative methods for overflow queueing models. I
- Parallel algorithms for solving tridiagonal and near-circulant systems.
- Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems
This page was built for publication: Exact algorithms for singular tridiagonal systems with applications to Markov chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q702603)
