Exact algorithms for singular tridiagonal systems with applications to Markov chains
type: Item
instance of: scholarly article
title: Exact algorithms for singular tridiagonal systems with applications to Markov chains
zbMATH Open document ID: 1074.65032
author: Linzhang Lu
author: Wai-Ki Ching
author: Michael Ng
published in: Applied Mathematics and Computation
publication date: 2005-01-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 60J22
Mathematics Subject Classification ID: 60K20
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 65C40
zbMATH DE Number: 2128805
zbMATH Keywords: irreducible tridiagonal matrix
zbMATH Keywords: divide-and-conquer algorithm
zbMATH Keywords: Markov chains
zbMATH Keywords: random walks
zbMATH Keywords: overflow queuing network
zbMATH Keywords: steady state probability distributions
zbMATH Keywords: singular linear system
zbMATH Keywords: successive matrix decomposition
zbMATH Keywords: matrix partitioning
reviewed by: Wolfgang zu Castell
MaRDI profile type: Publication
full work available at URL: j.amc.2003.10.029
OpenAlex ID: W2070194995
cites work: Divide and conquer: A parallel algorithm for the solution of a tridiagonal linear system of equations
cites work: Q3943082
cites work: Iterative methods for overflow queueing models. I
cites work: Circulant preconditioners for stochastic automata networks
cites work: Q2703763
cites work: Circulant Preconditioners for Markov-Modulated Poisson Processes and Their Applications to Manufacturing Systems
cites work: A note on the recursive decoupling method for solving tridiagonal linear systems
cites work: Q5689624
cites work: A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
cites work: Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems
cites work: Parallel algorithms for solving tridiagonal and near-circulant systems.
cites work: Q4324960
cites work: An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations
cites work: A Parallel Method for Tridiagonal Equations
DOI: 10.1016/J.AMC.2003.10.029
description: scientific article; zbMATH DE number 2128805