Exact algorithms for singular tridiagonal systems with applications to Markov chains

Lin Zhang Lu; Wai Ki Ching; Michael K. Ng

doi:10.1016/j.amc.2003.10.029

Exact algorithms for singular tridiagonal systems with applications to Markov chains

Lin Zhang Lu^*, Wai Ki Ching, Michael K. Ng

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

4 Citations (Scopus)

Abstract

In this paper, we propose two exact algorithms to solve the steady state probability distributions of irreducible Markov chains whose generator matrices have tridiagonal structure. The first exact algorithm is based on divide-and-conquer procedure and the second one is a parallel algorithm. Examples on random walks and queuing networks are given to demonstrate the usefulness of the algorithms.

Original language	English
Pages (from-to)	275-289
Number of pages	15
Journal	Applied Mathematics and Computation
Volume	159
Issue number	1
DOIs	https://doi.org/10.1016/j.amc.2003.10.029
Publication status	Published - 25 Nov 2004

Scopus Subject Areas

Computational Mathematics
Applied Mathematics

User-Defined Keywords

Divide-and-conquer procedure
Irreducible tridiagonal matrix
M-matrices

Access to Document

10.1016/j.amc.2003.10.029

Cite this

@article{edded5fdbea645dcaddfd5f04255f395,

title = "Exact algorithms for singular tridiagonal systems with applications to Markov chains",

abstract = "In this paper, we propose two exact algorithms to solve the steady state probability distributions of irreducible Markov chains whose generator matrices have tridiagonal structure. The first exact algorithm is based on divide-and-conquer procedure and the second one is a parallel algorithm. Examples on random walks and queuing networks are given to demonstrate the usefulness of the algorithms.",

keywords = "Divide-and-conquer procedure, Irreducible tridiagonal matrix, M-matrices",

author = "Lu, {Lin Zhang} and Ching, {Wai Ki} and Ng, {Michael K.}",

note = "Funding Information: Research supported in part by RGC Grant No. HKU 7126/02P and HKU CRCG Grant No. 10203919 and 10204436. Research supported in part by Hong Kong Research Grants Council Grant Nos. HKU 7130/ 02P and 7046/03P, and HKU CRCG Grant Nos. 10203501, 10203907 and 10204437. Publisher copyright: {\textcopyright} 2003 Elsevier Inc. All rights reserved.",

year = "2004",

month = nov,

day = "25",

doi = "10.1016/j.amc.2003.10.029",

language = "English",

volume = "159",

pages = "275--289",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Exact algorithms for singular tridiagonal systems with applications to Markov chains

AU - Lu, Lin Zhang

AU - Ching, Wai Ki

AU - Ng, Michael K.

N1 - Funding Information: Research supported in part by RGC Grant No. HKU 7126/02P and HKU CRCG Grant No. 10203919 and 10204436. Research supported in part by Hong Kong Research Grants Council Grant Nos. HKU 7130/ 02P and 7046/03P, and HKU CRCG Grant Nos. 10203501, 10203907 and 10204437. Publisher copyright: © 2003 Elsevier Inc. All rights reserved.

PY - 2004/11/25

Y1 - 2004/11/25

N2 - In this paper, we propose two exact algorithms to solve the steady state probability distributions of irreducible Markov chains whose generator matrices have tridiagonal structure. The first exact algorithm is based on divide-and-conquer procedure and the second one is a parallel algorithm. Examples on random walks and queuing networks are given to demonstrate the usefulness of the algorithms.

AB - In this paper, we propose two exact algorithms to solve the steady state probability distributions of irreducible Markov chains whose generator matrices have tridiagonal structure. The first exact algorithm is based on divide-and-conquer procedure and the second one is a parallel algorithm. Examples on random walks and queuing networks are given to demonstrate the usefulness of the algorithms.

KW - Divide-and-conquer procedure

KW - Irreducible tridiagonal matrix

KW - M-matrices

UR - http://www.scopus.com/inward/record.url?scp=4944255656&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2003.10.029

DO - 10.1016/j.amc.2003.10.029

M3 - Journal article

AN - SCOPUS:4944255656

SN - 0096-3003

VL - 159

SP - 275

EP - 289

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

IS - 1

ER -

Exact algorithms for singular tridiagonal systems with applications to Markov chains

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this