More Web Proxy on the site http://driver.im/

article

Free access

A comparison of numerical techniques in Markov modeling

Author:

William J. StewartAuthors Info & Claims

Communications of the ACM, Volume 21, Issue 2

Pages 144 - 152

https://doi.org/10.1145/359340.359350

Published: 01 February 1978 Publication History

Abstract

This paper presents several numerical methods which may be used to obtain the stationary probability vectors of Markovian models. An example of a nearly decomposable system is considered, and the results obtained by the different methods examined. A post mortem reveals why standard techniques often fail to yield the correct results. Finally, a means of estimating the error inherent in the decomposition of certain models is presented.

References

[1]

Bauer, F.L. Das Verfahren der Treppeniteration und Verwandte Verfahren zur Losung Algebraischer Eigenwertprobleme. ZAMP 8 (1957), 214-235.

[2]

Brandwajn, A. A model of a time sharing virtual memory system solved using equivalence and decomposition methods. Acta lnformatica 4, 1 (1974), 11-47.

[3]

Belady, L.A., and Kuehner, C.J. Dynamic space sharing in computer systems. Comm. ACM 12, 5 (1969), 282-288.

Digital Library

[4]

Clint, M., and Jennings, A. The evaluation of eigenvalues and eigenvectors of real symmetric matrices by simultaneous iteration. Computer J. 13 (1970), 76-80.

[5]

Clint, M., and Jennings, A. A simultaneous iteration method for the unsymmetric eigenvalue problem. J.IMA 8 (1971), 111- 121.

[6]

Cohen, A.M. Numerical Analysis. McGraw-Hill Book Co., U.K., 1973.

[7]

Courtois, P.J. On the near-complete-decomposability of networks of queues and of stochastic models of multiprogramming computer systems. MBLE Rep., MBLE Res. Lab., Brussels, Belgium, Nov. 1970.

[8]

Courtois, P.J. Decomposability, instabilities and saturation in multiprogramming systems. Comm. ACM 18, 7 (1975), 371-389.

Digital Library

[9]

Courtois, P.J. Error analysis in nearly-completely decomposable stochastic systems. Econometrica 43, 4 (1975), 691- 709.

[10]

Duff, I.S. A survey of sparse matrix research. Internal Rep. HL 76/485, Feb. 1976. Comptr. Sci. and Syst. Div., A.E.R.E., Hartwell, U.K., (to be published in Proc. IEEE).

[11]

Gantmacher, F.R. Applications of the Theory of Matrices. Interscience, New York, 1959.

[12]

Jennings, A. Matrix Computation for Engineers and Scientists. Wiley, London, 1977.

[13]

Jennings, A., and Stewart, W.J. Simultaneous iteration for partial eigensolution of real matrices. J.1MA 15 (1975), 351-361.

[14]

Kahan, W. Gauss-Seidel methods of solving large systems of linear equations. Ph.D. Th., U. of Toronto, Toronto, Ont., 1958.

[15]

Nomura, K. Stochastic models for systems of multiple integrated processors. Ph.D. Th., U. of North Carolina at Chapel Hill, Chapel Hill, N. C., 1974.

Digital Library

[16]

Paige, C.C., Styan, G.P.H., and Wachter, P.G. Computation of the stationary distribution of a Markov chain. Tech. Rep. No. 128, Inst. for Math. Studies in the Soc. Sci., Stanford U., Stanford, Calif., April 1974.

[17]

Simon, H., and Ando, A. Aggregation of variables in dynamic systems. Econometrica 20 (April 1961), 111-138.

[18]

Stewart, G.W. Simultaneous iteration for computing invariant subspaces of non-hermitian matrices. Num. Math. 25 (1976), 123- 136.

Digital Library

[19]

Stewart, W.J. Markov analysis of operating system techniques. PhD. Th., Dept. of Comptr. Sci., Queen's University of Belfast, N. Ireland, 1974.

[20]

Vantilborgh, H. Exact aggregation in exponential queueing networks. MBLE Res. Rep. No. R-337, MBLE Res. Lab., Brussels, Belgium, Nov. 1976.

[21]

Varga, R.S. Matrix lterative Analysis. Prentice-Hall, Englewood Cliffs, N. J., 1963.

[22]

Wallace, V.L., and Rosenberg, R.S. The Recursive Queue Analyzer. Syst. Eng. Dept., Tech. Rep. No. 2, U. of Michigan, Ann Arbor, Mich., 1966.

[23]

Wilkinson, J.H. The Algebraic Eigenvalue Problem. Clarendon Press, Oxford, 1965.

Digital Library

[24]

Young, D.M. lterative Solution of Large Linear Systems. Academic Press, New York, 1971.

[25]

Zarling, R.L. Numerical solution of nearly decomposable queueing networks. Ph.D. Th., Comptr. Sci. Dept., U. of North Carolina at Chapel Hill, Chapel Hill, N. C., 1976.

Digital Library

Cited By

Kaur M(2020)Why Stochastic Models That Are So Famous, Become Infamous In Reliability Engineering2020 Annual Reliability and Maintainability Symposium (RAMS)10.1109/RAMS48030.2020.9153643(1-8)Online publication date: Jan-2020
https://doi.org/10.1109/RAMS48030.2020.9153643
Du ZOzay NBalzano L(2019)Mode Clustering for Markov Jump Systems2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)10.1109/CAMSAP45676.2019.9022650(126-130)Online publication date: Dec-2019
https://doi.org/10.1109/CAMSAP45676.2019.9022650
Goldberg H(2016) Computation Of State Probabilities For Mim/S Priority Queues With Customer Classes Having Different Service Rates * INFOR: Information Systems and Operational Research10.1080/03155986.1981.1173180619:1(48-58)Online publication date: 25-May-2016
https://doi.org/10.1080/03155986.1981.11731806
Show More Cited By

Index Terms

A comparison of numerical techniques in Markov modeling
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis

Recommendations

Optimal decisions for continuous time Markov decision processes over finite planning horizons

The computation of ź-optimal policies for continuous time Markov decision processes (CTMDPs) over finite time intervals is a sophisticated problem because the optimal policy may change at arbitrary times. Numerical algorithms based on time ...
On the Numerical Analysis of Inhomogeneous Continuous-Time Markov Chains

Inhomogeneous continuous-time Markov chains play an important role in different application areas. In contrast to homogeneous continuous-time Markov chains, where a large number of numerical analysis techniques are available and have been compared, few ...
Robust stability of polytopic time-inhomogeneous Markov jump linear systems
Abstract
The transition probabilities of jumps between operational modes of discrete-time Markov(ian) jump linear systems (dtMJLSs) are generally considered to be time-invariant, certain, and often completely known in the majority of dedicated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 21, Issue 2

Feb. 1978

74 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359340

Editor:
Robert L. Ashenhurst
The Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Copyright © 1978 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1978

Published in CACM Volume 21, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

128
Total Citations
View Citations
713
Total Downloads

Downloads (Last 12 months)88
Downloads (Last 6 weeks)13

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kaur M(2020)Why Stochastic Models That Are So Famous, Become Infamous In Reliability Engineering2020 Annual Reliability and Maintainability Symposium (RAMS)10.1109/RAMS48030.2020.9153643(1-8)Online publication date: Jan-2020
https://doi.org/10.1109/RAMS48030.2020.9153643
Du ZOzay NBalzano L(2019)Mode Clustering for Markov Jump Systems2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)10.1109/CAMSAP45676.2019.9022650(126-130)Online publication date: Dec-2019
https://doi.org/10.1109/CAMSAP45676.2019.9022650
Goldberg H(2016) Computation Of State Probabilities For Mim/S Priority Queues With Customer Classes Having Different Service Rates * INFOR: Information Systems and Operational Research10.1080/03155986.1981.1173180619:1(48-58)Online publication date: 25-May-2016
https://doi.org/10.1080/03155986.1981.11731806
Kaur MLal ABhatia SReddy A(2013)Numerical solution of stochastic partial differential difference equation arising in reliability engineeringApplied Mathematics and Computation10.1016/j.amc.2013.01.052219:14(7645-7652)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.amc.2013.01.052
Ni WCollings ILiu R(2012)Relay Handover and Link Adaptation Design for Fixed Relays in IMT-Advanced Using a New Markov Chain ModelIEEE Transactions on Vehicular Technology10.1109/TVT.2012.218731961:4(1839-1853)Online publication date: May-2012
https://doi.org/10.1109/TVT.2012.2187319
Monahan J(2011)EigenproblemsNumerical Methods of Statistics10.1017/CBO9780511977176.008(128-150)Online publication date: 1-Jun-2011
https://doi.org/10.1017/CBO9780511977176.008
Gurgur C(2011)Optimal configuration of a decentralized, market-driven production/inventory systemAnnals of Operations Research10.1007/s10479-011-0977-1209:1(139-157)Online publication date: 4-Oct-2011
https://doi.org/10.1007/s10479-011-0977-1
Ekren BHeragu S(2010)Approximate analysis of load-dependent generally distributed queuing networks with low service time variabilityEuropean Journal of Operational Research10.1016/j.ejor.2010.01.022205:2(381-389)Online publication date: Sep-2010
https://doi.org/10.1016/j.ejor.2010.01.022
Gambin AKrzyżanowski PPokarowski P(2008)Aggregation Algorithms for Perturbed Markov Chains with Applications to Networks ModelingSIAM Journal on Scientific Computing10.1137/05062471631:1(45-73)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1137/050624716
Ke JLin C(2008)Maximum entropy approach for batch-arrival queue under N policy with an un-reliable server and single vacationJournal of Computational and Applied Mathematics10.1016/j.cam.2007.10.001221:1(1-15)Online publication date: 1-Nov-2008
https://dl.acm.org/doi/10.1016/j.cam.2007.10.001
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents