Exact algorithms for singular tridiagonal systems with applications to Markov chains

DOI10.1016/J.AMC.2003.10.029MaRDI QIDQ702603zbMATH OpenOpenAlexFDO

Authors Linzhang Lu, Wai-Ki Ching, Michael Ng

Publication date 17 January 2005

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2003.10.029

zbMATH Keywords

divide-and-conquer algorithmirreducible tridiagonal matrixMarkov chainsmatrix partitioningoverflow queuing networkrandom walkssingular linear systemsteady state probability distributionssuccessive matrix decomposition

Mathematics Subject Classification ID

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)

Recommendations

• 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

Cites work

• 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

Cited in

(3)

• Boundary value methods for solving transient solutions of Markovian queueing networks
• scientific article; zbMATH DE number 431648 (Why is no real title available?)
• scientific article; zbMATH DE number 1226277 (Why is no real title available?)

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)