Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Iterative and semi-iterative methods for computing stationary probability vectors of Markov operators
HTML articles powered by AMS MathViewer

by Ivo Marek and Daniel B. Szyld PDF
Math. Comp. 61 (1993), 719-731 Request permission

Abstract:

Iterative and semi-iterative methods for computing stationary probability vectors of Markov-type operators are proposed and their convergence properties are analyzed. The methods studied apply to certain classes of problems in infinite-dimensional spaces as well as to classical $n \times n$ stochastic matrices.
References
  • G. P. Barker and S.-J. Yang, Semi-iterative and iterative methods for singular $M$-matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 2, 168–180. MR 938496, DOI 10.1137/0609014
  • G. P. Barker and R. J. Plemmons, Convergent iterations for computing stationary distributions of Markov chains, SIAM J. Algebraic Discrete Methods 7 (1986), no. 3, 390–398. MR 844041, DOI 10.1137/0607044
  • V. A. Barker, Numerical solution of sparse singular systems of equations arising from ergodic Markov chains, Comm. Statist. Stochastic Models 5 (1989), no. 3, 335–381. MR 1010533, DOI 10.1080/15326348908807115
  • Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR 544666
  • E. B. Dynkin, Markov processes. Vols. I, II, Die Grundlehren der mathematischen Wissenschaften, Band 121, vol. 122, Academic Press, Inc., Publishers, New York; Springer-Verlag, Berlin-Göttingen-Heidelberg, 1965. Translated with the authorization and assistance of the author by J. Fabius, V. Greenberg, A. Maitra, G. Majone. MR 0193671
  • Michael Eiermann, Ivo Marek, and Wilhelm Niethammer, On the solution of singular linear systems of algebraic equations by semi-iterative methods, Numer. Math. 53 (1988), no. 3, 265–283. MR 948587, DOI 10.1007/BF01404464
  • Michael Eiermann and Wilhelm Niethammer, On the construction of semi-iterative methods, SIAM J. Numer. Anal. 20 (1983), no. 6, 1153–1160. MR 723832, DOI 10.1137/0720085
  • M. Eiermann, W. Niethammer, and R. S. Varga, A study of semi-iterative methods for nonsymmetric systems of linear equations, Numer. Math. 47 (1985), no. 4, 505–533. MR 812617, DOI 10.1007/BF01389454
    • F. R. Gantmacher, The theory of matrices, Goz. Izdat. Lit., Moscow, 1954; English transl., Applications of the theory of matrices, Interscience, New York, 1959. Halim D. Kafeety, Carl D. Meyer, and William J. Stewart, A general framework for iterative aggregation/disaggregation methods for the numerical solution of Markov chains, Technical Report No. 06039101, Center for Research in Scientific Computation, North Carolina State University, Raleigh, North Carolina, November 1990. (See also the Proceedings of the Copper Mountain Conference on Iterative Methods (Copper Mountain, Colorado, April 9-14, 1992), Computational Mathematics Group, University of Colorado at Denver, 1992.) M. G. Kreǐn and M. A. Rutman, Linear operators leaving a cone invariant in a Banach space, Uspekhi Mat. Nauk 3 (1948), no. 1, 3-95; English transl., Amer. Math. Soc. Transl. 26 (1950).
  • Walter Ledermann and Steven Vajda (eds.), Handbook of applicable mathematics. Vol. IV, A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1982. Analysis. MR 667016
  • Vladimír Lelek and Ivo Marek, Data fitting under eigenvalue constraints, Proceedings of the 9th Conference on Problems and Methods in Mathematical Physics (9.TMP) (Karl-Marx-Stadt, 1988) Teubner-Texte Math., vol. 111, Teubner, Leipzig, 1989, pp. 159–166. MR 1087318
  • Ivo Marek, Aggregation methods of computing stationary distributions of Markov processes, Numerical treatment of eigenvalue problems, Vol. 5 (Oberwolfach, 1990) Internat. Ser. Numer. Math., vol. 96, Birkhäuser, Basel, 1991, pp. 155–169. MR 1109102, DOI 10.1007/978-3-0348-6332-2_{1}2
    • —, On square roots of M-operators, Linear Algebra Appl. (submitted).
  • Ivo Marek and Daniel B. Szyld, Comparison theorems for weak splittings of bounded operators, Numer. Math. 58 (1990), no. 4, 387–397. MR 1077585, DOI 10.1007/BF01385632
  • Ivo Marek and Daniel B. Szyld, Splittings of $M$-operators: irreducibility and the index of the iteration operator, Numer. Funct. Anal. Optim. 11 (1990), no. 5-6, 529–553. MR 1079290, DOI 10.1080/01630569008816387
    • —, Iterative aggregation with inexact correction, Technical Report no. 91-52, Department of Mathematics, Temple University, May 1991.
  • Ivo Marek and Karel Žitný, Equivalence of $K$-irreducibility concepts, Comment. Math. Univ. Carolin. 25 (1984), no. 1, 61–72. MR 749116
  • M. Z. Nashed, Generalized inverses, normal solvability, and iteration for singular operator equations, Nonlinear Functional Anal. and Appl. (Proc. Advanced Sem., Math. Res. Center, Univ. of Wisconsin, Madison, Wis., 1970) Academic Press, New York, 1971, pp. 311–359. MR 0275246
  • W. Niethammer and R. S. Varga, The analysis of $k$-step iterative methods for linear systems from summability theory, Numer. Math. 41 (1983), no. 2, 177–206. MR 703121, DOI 10.1007/BF01390212
  • Donald J. Rose, Convergent regular splittings for singular $M$-matrices, SIAM J. Algebraic Discrete Methods 5 (1984), no. 1, 133–144. MR 731863, DOI 10.1137/0605015
  • Uriel G. Rothblum, Algebraic eigenspaces of nonnegative matrices, Linear Algebra Appl. 12 (1975), no. 3, 281–292. MR 404298, DOI 10.1016/0024-3795(75)90050-6
  • Uriel G. Rothblum, Convergence properties of powers of matrices with applications to iterative methods for solving linear systems, Extremal methods and systems analysis (Internat. Sympos., Univ. Texas, Austin, Tex., 1977) Lecture Notes in Econom. and Math. Systems, vol. 174, Springer, Berlin-New York, 1980, pp. 231–247. MR 563868
  • Ikuko Sawashima, On spectral properties of some positive operators, Natur. Sci. Rep. Ochanomizu Univ. 15 (1964), 53–64. MR 187096
  • Paul J. Schweitzer, A survey of aggregation-disaggregation in large Markov chains, Numerical solution of Markov chains, Probab. Pure Appl., vol. 8, Dekker, New York, 1991, pp. 63–88. MR 1142109
  • Kunio Tanabe, The conjugate gradient method for computing all the extremal stationary probability vectors of a stochastic matrix, Ann. Inst. Statist. Math. 37 (1985), no. 1, 173–187. MR 790385, DOI 10.1007/BF02481090
  • Angus E. Taylor, Introduction to functional analysis, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1958. MR 0098966
  • Richard S. Varga, Factorization and normalized iterative methods, Boundary problems in differential equations, Univ. Wisconsin Press, Madison, Wis., 1960, pp. 121–142. MR 0121977
  • Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502
Similar Articles
Additional Information
  • © Copyright 1993 American Mathematical Society
  • Journal: Math. Comp. 61 (1993), 719-731
  • MSC: Primary 65J10; Secondary 15A48, 47A50, 47B65, 60J10
  • DOI: https://doi.org/10.1090/S0025-5718-1993-1192973-1
  • MathSciNet review: 1192973