×

zbMATH — the first resource for mathematics

A direct projection method for Markov chains. (English) Zbl 1062.65011
Let \(P\) be an \(n\times n\) transition probability matrix of a finite ergodic Markov chain. The author explains how the direct method of E. W. Purcell [J. Math. Phys. 32, 180–183 (1953; Zbl 0051.35303)] based on oblique projections can be used to find the stationary distribution vector, i.e., the unique row vector \(\pi=(\pi_ 1,\ldots,\pi_ n)\) satisfying \(\pi=\pi P\), \(\pi>0\), \(\sum_ i\pi_ i=1\). The method can be also used for computation of the group inverse of the generator matrix and for updating the latter and stationary vector after a one-row change of the transition matrix.
The relationship between this method and Gaussian elimination method is exploited to develop a more stable, GTH-like variant [cf. W. K. Grassmann, M. I. Taksar, and D. P. Heyman, Oper. Res. 33, 1107–1116 (1985; Zbl 0576.60083)] that can handle nearly uncoupled systems and other situations where the original algorithm fails.

MSC:
65C40 Numerical analysis or methods applied to Markov chains
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J22 Computational methods in Markov chains
PDF BibTeX Cite
Full Text: DOI
References:
[1] Barlow, J.L, Perturbation results for nearly uncoupled Markov chains with applications to iterative methods, Numer. math., 65, 51-62, (1993) · Zbl 0792.65027
[2] M. Benzi, A direct row-projection method for sparse linear systems, Ph.D. Thesis, North Carolina State University, Raleigh, NC, 1993
[3] Benzi, M; Meyer, C.D, A direct projection method for sparse linear systems, SIAM J. sci. comput., 16, 1159-1176, (1995) · Zbl 0853.65035
[4] Benzi, M; Meyer, C.D; Tůma, M, A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. sci. comput., 17, 1135-1149, (1996) · Zbl 0856.65019
[5] Benzi, M; Tůma, M, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. sci. comput., 19, 968-994, (1998) · Zbl 0930.65027
[6] Benzi, M; Tůma, M, A parallel solver for large-scale Markov chains, Appl. numer. math., 41, 135-153, (2002) · Zbl 0997.65006
[7] Berman, A; Plemmons, R.J, Nonnegative matrices in the mathematical sciences, (1979), Academic Press New York, Reprinted by SIAM, Philadelphia, PA, 1994 · Zbl 0484.15016
[8] Campbell, S.L; Meyer, C.D, Generalized inverses of linear transformations, (1979), Pitman London, Reprinted by Dover Publishing, New York, 1991 · Zbl 0417.15002
[9] Chen, K; Lai, C.H, Parallel algorithms of the purcell method for direct solution of linear systems, Parallel comput., 28, 1275-1291, (2002) · Zbl 0999.68254
[10] Courtois, P.J, Decomposability: queueing and computer system applications, (1977), Academic Press New York · Zbl 0368.68004
[11] T. Dayar, Stability and conditioning issues on the numerical solution of Markov chains, Ph.D. Thesis, North Carolina State University Raleigh, NC, 1994
[12] Dayar, T; Stewart, W.J, On the effects of using the grassmann – taksar – heyman method in iterative aggregation – disaggregation, SIAM J. sci. comput., 17, 287-303, (1996) · Zbl 0840.60062
[13] Faddeev, D.K; Faddeeva, V.N, Computational methods of linear algebra, (1963), W.H. Freeman and Co San Francisco, CA · Zbl 0112.07503
[14] Fletcher, R, Dense factors of sparse matrices, (), 145-166 · Zbl 1031.65043
[15] G.E. Forsythe, Review of [37], Mathematical Reviews # 15,471h (1953)
[16] Fox, L; Huskey, H.D; Wilkinson, J.H, Notes on the solution of algebraic linear simultaneous equations, Quart. J. mech. appl. math., 1, 253-280, (1948) · Zbl 0033.28503
[17] Funderlic, R.E; Mankin, J.B, Solution of homogeneous systems of linear equations arising from compartmental models, SIAM J. sci. statist. comput., 2, 375-383, (1981) · Zbl 0468.65042
[18] Funderlic, R.E; Meyer, C.D, Sensitivity of the stationary vector for an ergodic Markov chain, Linear algebra appl., 76, 1-17, (1986) · Zbl 0583.60064
[19] Funderlic, R.E; Neumann, R.E; Plemmons, R.J, LU decompositions of generalized diagonally dominant matrices, Numer. math., 40, 57-69, (1982) · Zbl 0481.65017
[20] Funderlic, R.E; Plemmons, R.J, Updating LU factorizations for computing stationary distributions, SIAM J. algebr. disc. meth., 7, 30-42, (1986) · Zbl 0592.65014
[21] Golub, G.H; Meyer, C.D, Using the QR factorization and group inversion to compute, differentiate, and estimate the sensitivity of stationary probabilities for Markov chains, SIAM J. algebr. disc. meth., 7, 273-281, (1986) · Zbl 0594.60072
[22] Grassmann, W.K; Taksar, M.I; Heyman, D.P, Regenerative analysis and steady state distributions for Markov chains, Oper. res., 33, 1107-1116, (1985) · Zbl 0576.60083
[23] Hestenes, M.R; Stiefel, E, Methods of conjugate gradients for solving linear systems, J. res. nat. bur. standards, 49, 409-436, (1952) · Zbl 0048.09901
[24] Heyman, D.P; O’Leary, D.P, What is fundamental for Markov chains: first passage times, fundamental matrices, and group generalized inverses, (), 151-161 · Zbl 0862.60051
[25] Householder, A.S, The theory of matrices in numerical analysis, (1964), Blaisdell Publishing Co New York, Reprinted by Dover Publishing, New York, 1975 · Zbl 0161.12101
[26] Hunter, J.J, Stationary distributions of perturbed Markov chains, Linear algebra appl., 82, 201-214, (1986) · Zbl 0608.60062
[27] Ipsen, I.C.F; Meyer, C.D, Uniform stability of Markov chains, SIAM J. matrix anal. appl., 15, 1061-1074, (1994) · Zbl 0809.65144
[28] Meyer, C.D, Generalized inversion of modified matrices, SIAM J. appl. math., 24, 315-323, (1973) · Zbl 0253.15001
[29] Meyer, C.D, The role of the group generalized inverse in the theory of finite Markov chains, SIAM rev., 17, 443-464, (1975) · Zbl 0313.60044
[30] Meyer, C.D, Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems, SIAM rev., 31, 240-272, (1989) · Zbl 0685.65129
[31] Meyer, C.D, Sensitivity of the stationary distribution of a Markov chain, SIAM J. matrix anal. appl., 15, 715-728, (1994) · Zbl 0809.65143
[32] Meyer, C.D; Shoaf, J.M, Updating finite Markov chains by using techniques of group matrix inversion, J. statist. comput. simul., 11, 163-181, (1980) · Zbl 0464.60075
[33] Morris, J, An escalator process for the solution of linear simultaneous equations, Philos. mag., 7, 106-120, (1946) · Zbl 0061.27101
[34] O’Cinneide, C.A, Entrywise perturbation theory and error analysis for Markov chains, Numer. math., 65, 109-120, (1993) · Zbl 0804.65145
[35] O’Cinneide, C.A, Relative-error bounds for the LU decomposition via the GTH algorithm, Numer. math., 75, 507-519, (1996) · Zbl 0859.65018
[36] Paige, C.C; Styan, P.H; Wachter, P.G, Computation of the stationary distribution of a Markov chain, J. statist. comput. simul., 4, 1156-1179, (1975) · Zbl 0331.60040
[37] Purcell, E.W, The vector method of solving simultaneous linear equations, J. math. phys., 32, 180-183, (1953) · Zbl 0051.35303
[38] Stewart, G.W, Conjugate direction methods for solving systems of linear equations, Numer. math., 21, 283-297, (1973) · Zbl 0253.65017
[39] Stewart, G.W, Gaussian elimination, perturbation theory and Markov chains, (), 59-69 · Zbl 0789.65102
[40] Stewart, G.W; Zhang, G, On a direct method for the solution of nearly uncoupled Markov chains, Numer. math., 59, 1-12, (1991) · Zbl 0697.65016
[41] Stewart, W.J, Introduction to the numerical solution of Markov chains, (1994), Princeton University Press Princeton, NJ · Zbl 0821.65099
[42] Tweedie, R.L, Perturbations of countable Markov chains and processes, Ann. inst. statist. math., 32, 283-290, (1980) · Zbl 0452.60075
[43] Wedderburn, J.H.M, Lectures on matrices, am. math. soc. colloq. publ. XVII, (1934), American Mathematical Society Providence, RI, Reprinted by Dover Publishing, New York, 1964 · Zbl 0010.09904
[44] Zhang, G, On the sensitivity of the solution of nearly uncoupled Markov chains, SIAM J. matrix anal. appl., 14, 1112-1123, (1993) · Zbl 0780.60068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.