Exact algorithms for singular tridiagonal systems with applications to Markov chains (Q702603)

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.