Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems
The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Abstract
A concept called stochastic complementation is an idea which occurs naturally, although not always explicitly, in the theory and application of finite Markov chains. This paper brings this idea to the forefront with an explicit definition and a development of some of its properties. Applications of stochastic complementation are explored with respect to problems involving uncoupling procedures in the theory of Markov chains. Furthermore, the role of stochastic complementation in the development of the classical Simon–Ando theory of nearly reducible system is presented
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Since (I − Pii) −1 ≥ 0 [24] and (L + U) ≥ 0, the split- ting above is weak regular.”
From Distributed PageRank computation based on iterative aggregation-disaggregation methods (2005) · cites this paper as [24]
Citations
Cites
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Horn, R. A., & Johnson, C. R. (1985) · Cambridge University Press eBooks · doi:10.1017/cbo9780511810817 · Cited by 10,280 · cited 4×
“It is well known (see [19] or [11]) that for every square matrix A and each ǫ > 0, there exists a matrix norm ||| • ||| such that ρ(A) ≤ |||A||| ≤ ρ(A) + ǫ.”
BackgroundInfluentialNonnegative Matrices in the Mathematical Sciences
(1979) · Elsevier eBooks · doi:10.1016/c2013-0-10361-3 · Cited by 5,451
Kemeny, J. G., & Snell, J. L. (1976) · Medical Entomology and Zoology · Cited by 2,813
Introduction to matrix computations
Stewart, G. W. (1973) · International Linear Collider · Cited by 2,381
Bush, K. A., Kemeny, J. G., & Snell, J. L. (1960) · The American Mathematical Monthly · doi:10.2307/2309264 · Cited by 1,546
Aggregation of Variables in Dynamic Systems
Simon, H. A., & Ando, A. (1961) · Econometrica · doi:10.2307/1909285 · Cited by 562
Aggregation of Variables in Dynamic Systems
Simon, H. A. (1977) · Boston Studies in the Philosophy of Science · doi:10.1007/978-94-010-9521-1_12 · Cited by 550 · cited 6×
“The contribution of Simon and Ando [18] was to provide mathematical arguments for what had previously been a rather heuristic theory concerning nearly completely reducible systems.”
BackgroundMethodInfluentialDecomposability: Queueing and Computer System Applications
Courtois, P. (1977) · Cited by 471
Regenerative Analysis and Steady State Distributions for Markov Chains
Grassmann, W. K., Taksar, M. I., & Heyman, D. P. (1985) · Operations Research · doi:10.1287/opre.33.5.1107 · Cited by 364 · cited 1×
“Simple forms of stochastic complementation can be found either explicitly or implicitly in a variety of Markov chain applications such as those in [1], [3]–[6], [8]–[10], [12]–[16], [20], [21], in addition to several others.”
Background
Research works printed but not linked: 3
- Balsamo S., 1988, Computer performance and reliability (Rome, 1987), 73
- Courtois P.-J., 1977, Decomposability
- Gantmacher F. R., 1960, Matrix Theory—Vol. II
Cited by
1Kron Reduction of Graphs with Applications to Electrical Networks
Bullo, F. (2015) · Cited by 821
Graph Clustering Via a Discrete Uncoupling Process
Van Dongen, S. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/040608635 · Cited by 750
Robust Perron cluster analysis in conformation dynamics
Deuflhard, P., & Weber, M. (2005) · Linear Algebra and its Applications · doi:10.1016/j.laa.2004.10.026 · Cited by 506
Fuzzy spectral clustering by PCCA+: application to Markov state models and data classification
Röblitz, S., & Weber, M. (2013) · Advances in Data Analysis and Classification · doi:10.1007/s11634-013-0134-6 · Cited by 371
“Such Markov chains are also known as nearly completely decomposable or nearly reducible Markov chains, see Courtois (1977), Stewart (1984), Meyer (1989).”
BackgroundIdentification of almost invariant aggregates in reversible nearly uncoupled Markov chains
Deuflhard, P., Huisinga, W., Fischer, A., & Schütte, C. (2000) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(00)00095-1 · Cited by 319
Electrical Networks and Algebraic Graph Theory: Models, Properties, and Applications
Dorfler, F., Simpson-Porco, J. W., & Bullo, F. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2821924 · Cited by 227
“Thus, Kron reduction can be found under different names and with a graph-theoretic perspective in Gaussian elimination of sparse matrices [65], [71], [114], sparse grid and finite-element solvers [139], [43], [138], statistical mechanics [107], data mining [155], [69], reduction of Markov chains [98], [18], signal pro…”
BackgroundSpectral analysis of M/G/ 1 and G / M /1 type Markov chains
Gail, H. R., Hantler, S. L., & Taylor, B. A. (1996) · Advances in Applied Probability · doi:10.2307/1427915 · Cited by 171
A solver for the stochastic master equation applied to gene regulatory networks
Hegland, M., Burden, C. J., Santoso, L. M., MacNamara, S., & Booth, H. S. (2006) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2006.02.053 · Cited by 133
“For a discussion of aggregation in general, see [18,7,19,12].”
BackgroundParallel SimRank computation on large graphs with iterative aggregation
He, G., Feng, H., Li, C., & Chen, H. (2010) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835874 · Cited by 124
“Since [31] brought forward the concept of nearly completely reducible (NCR) Markov chain, the iterative aggregation method has been widely exploited to applications based on NCR Markov chains, e.g. distributed PageRank computing [41], PageRank updating [20], [21], etc. GPU Applications.”
MethodA coarse graining method for the identification of transition rates between molecular conformations
Kube, S., & Weber, M. (2007) · The Journal of Chemical Physics · doi:10.1063/1.2404953 · Cited by 123
A Reordering for the PageRank Problem
Langville, A. N., & Meyer, C. D. (2006) · SIAM Journal on Scientific Computing · doi:10.1137/040607551 · Cited by 100
“Perhaps Perron complementation [10] or stochastic complementation [9] can be used for the updating problem [6].”
MethodSelf-citationRecWalk: Nearly Uncoupled Random Walks for Top-N Recommendation
Νικολακόπουλος, Α. Ν., & Karypis, G. (2019) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3289600.3291016 · Cited by 90
“[26, 41, 42]) as well as the development of new network centrality measures [13, 29, 32].”
Updating Markov Chains with an Eye on Google's PageRank
Langville, A. N., & Meyer, C. D. (2006) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/040619028 · Cited by 105
Self-citationOn the Doubling Algorithm for a (Shifted) Nonsymmetric Algebraic Riccati Equation
Guo, C., Iannazzo, B., & Meini, B. (2007) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/060660837 · Cited by 80
“Remark 2.6. The last statement in Lemma 2.5 follows from Theorem 2.3 of [ 20 ], where the irreducibility of the Schur complement is proved for any irreducible singular M-matrix of the form I P with P stochastic.”
BackgroundInfluentialPromoting Interactions Between Humans and Robots Using Robotic Emotional Behavior
Ficocelli, M., Terao, J., & Nejat, G. (2016) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2015.2492999 · Cited by 77
“the power method [38], aggregation techniques [39], and the Sherman–Morrison rank-one updating method [40], prove to be too computationally inefficient to be used as online updat-”
MethodA web aggregation approach for distributed randomized PageRank algorithmsPreprint
Ishii, H., Tempo, R., & Bai, E. (2012) · Cited by 77
Modeling and analysis of communication systems based on computational methods for Markov chains
Krieger, U. R., Müller‐Clostermann, B., & Sczittnick, M. (1990) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.62851 · Cited by 73
Comparison of Partitioning Techniques for Two-Level Iterative Solvers on Large, Sparse Markov Chains
Dayar, T., & Stewart, W. J. (2000) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827598338159 · Cited by 70
A Web Aggregation Approach for Distributed Randomized PageRank Algorithms
Ishii, H., Tempo, R., & Bai, E. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2012.2190161 · Cited by 77
“The paper [41] formalizes a general method for finding the exact distribution, and its application to the PageRank computation is discussed in [39].”
Kron Reduction of Graphs With Applications to Electrical Networks
Dörfler, F., & Bullo, F. (2013) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2012.2215780 · Cited by 491
“This concept finds application in Markov chain reduction [33] and data mining [36], where it is termed stochastic complement.”
InfluentialAn Algorithmic Approach to Stochastic Bounds
Fourneau, J., & Pekergin, N. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45798-4_4 · Cited by 68
“Then we present,in section 3,several algorithms for “st” bounds based on structures: upper-Hessenberg,lumpability,stochastic complement [ 26 ],Class C Matrices.”
BackgroundMethodInfluentialDistributed PageRank computation based on iterative aggregation-disaggregation methods
Zhu, Y., Ye, S., & Li, X. (2005) · Proceedings of the 14th ACM international conference on Information and knowledge management · doi:10.1145/1099554.1099705 · Cited by 65
“Therefore, the random walk on the web can be viewed as a nearly completely decomposable (NCD) Markov chain [24].”
BackgroundAlternating-directional Doubling Algorithm for M -Matrix Algebraic Riccati Equations
Wang, W., Wang, W., & Ren-cang Li, C. (2012) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/110835463 · Cited by 64
Updating pagerank with iterative aggregation
Langville, A. N., & Meyer, C. D. (2004) · Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters - WWW Alt. '04 · doi:10.1145/1013367.1013491 · Cited by 64
Self-citationJohnson, C. R., & Smith, R. L. (2011) · Linear Algebra and its Applications · doi:10.1016/j.laa.2011.02.016 · Cited by 61
Markov Chains and Dependability Theory
Rubino, G., & Séricola, B. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139051705 · Cited by 61
Convergence Analysis of a PageRank Updating Algorithm by Langville and Meyer
Ipsen, I. C. F., & Kirkland, S. (2006) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479804439808 · Cited by 60
Kuntz, J., Thomas, P., Stan, G.-B. V., & Barahona, M. (2021) · SIAM Review · doi:10.1137/19m1289625 · Cited by 69
Yu, F. R., Krishnamurthy, V., & Leung, V. C. M. (2006) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2005.861785 · Cited by 67
“Since the embedded Markov chain of the SMDP formulated in CMAC-I and CMAC-II for packet-switched CDMA networks has NCD structure, in this section, we formulate the CAC problem as a reduced complexity constrained SMDP by exploiting this NCD structure.”
MethodInfluentialNon-Skip-Free M/G/ 1 and G/M/ 1 Type Markov Chains
Gail, H. R., Hantler, S. L., & Taylor, B. A. (1997) · Advances in Applied Probability · doi:10.1017/s0001867800028329 · Cited by 59
Meshless Methods in Conformation Dynamics
Weber, M. (2006) · Cited by 60
NGUYEN, V., MATHIAS, R., & SMITH, G. (2004) · Bulletin of Mathematical Biology · doi:10.1016/j.bulm.2004.08.010 · Cited by 60
Measuring the Network Vulnerability Based on Markov Criticality
Li, H., Wang, L., Bu, Z., Cao, J., & Shi, Y. (2021) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3464390 · Cited by 59
“3 PROBLEM SETTING Markov theory [23] is a powerful tool to model intrinsic relationship in real systems, and we can naturally use it to analyze elements’ criticality.”
MethodSchur complements and its applications to symmetric nonnegative and Z-matrices
Fan, Y.-Z. (2002) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(02)00327-0 · Cited by 49
“The concept is derived from Schur complement and was introduced by Meyer [11,12] in his construction of an algorithm for computing the stationary distribution vector for Markov chains.”
MethodA parallel solver for large-scale Markov chains
Michele Benzi, A., & Tůma, M. (2002) · Applied Numerical Mathematics · doi:10.1016/s0168-9274(01)00116-7 · Cited by 49
“Proof: Consider the stochastic complement [22] of P22 in P : = P22 + P21(I P11) 1P12: Note that I P11 is invertible since P is irreducible.”
BackgroundStochastic complement analysis of multi-server threshold queues with hysteresis
Lui, J. C. S., & Golubchik, L. (1999) · Performance Evaluation · doi:10.1016/s0166-5316(98)00043-1 · Cited by 49
Numerical Methods for Computing Stationary Distributions of Finite Irreducible Markov Chains
Stewart, W. J. (2000) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4757-4828-4_4 · Cited by 46
DTMC Model Checking by SCC Reduction
Ábrahám, E., Jansen, N., Wimmer, R., Katoen, J.-P., & Becker, B. (2010) · International Conference on the Quantitative Evaluation of Systems (QEST) · doi:10.1109/qest.2010.13 · Cited by 44
“To reduce their size, the detection of loops [13], the usage of regular expressions [12], and the abstraction of strongly connected components (SCCs) [11], thereby extending an approach presented in [15] and [16], where it is referred to as stochastic complementation , have been suggested.”
BackgroundAggregation of the policy iteration method for nearly completely decomposable Markov chains
Aldhaheri, R. W., & Khalil, H. K. (1991) · IEEE Transactions on Automatic Control · doi:10.1109/9.67293 · Cited by 44
Metastability and Dominant Eigenvalues of Transfer Operators
Huisinga, W., & Schmidt, B. G. (2006) · Springer eBooks · doi:10.1007/3-540-31618-3_11 · Cited by 57
“Key words: Molecular dynamics, Markov processes, spectral properties, Rayleigh-trace, lower and upper bounds on metastability”
BackgroundDayar, T., & Stewart, W. J. (1997) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479895294277 · Cited by 41
Zhao, Y. Q., Li, W., & Braun, W. J. (2003) · Methodology And Computing In Applied Probability · doi:10.1023/a:1024125320911 · Cited by 41
Hidden Markov model state estimation with randomly delayed observations
Evans, J., & Krishnamurthy, V. (1999) · IEEE Transactions on Signal Processing · doi:10.1109/78.774757 · Cited by 41
“If and have very large dimensions, then the computation of and can be simplified by using numerical algorithms such as stochastic complementation [ 6 ].”
MethodBounding the equilibrium distribution of Markov population models
Dayar, T., Hermanns, H., Spieler, D., & Wolf, V. (2011) · Numerical Linear Algebra with Applications · doi:10.1002/nla.795 · Cited by 40
“In the second step of our approach, we consider the stochastic complement of W [16], which allows us to derive bounds for the probabilities of individual states within W .”
BackgroundAn evolutionary game-theoretic approach to congestion control
Menasché, D. S., Figueiredo, D. R., & Silva, E. D. S. E. (2005) · Performance Evaluation · doi:10.1016/j.peva.2005.07.028 · Cited by 39
Inverses of Perron complements of inverse M-matrices
Neumann, M. (2000) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(00)00128-2 · Cited by 38
Yang, M., Shahramian, S., Shakiba, H., Wong, H., Krotnev, P., & Carusone, A. C. (2019) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2019.2943569 · Cited by 37
“Transition matrix P = [ p i mim ] of the lumped process Y is then given by Moreover, a more straightforward two-step procedure for computing the aggregated state probabilities from the original chain is provided in [30].”
MethodMolecular Conformation Dynamics and Computational Drug Design
Deuflhard, P., & Schütte, C. (2004) · Cited by 38
Learning by Unsupervised Nonlinear DiffusionPreprint
Maggioni, M., & Murphy, J. M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.06702 · Cited by 43
“hain to be reversible, and hence applies to diusion processes dened on directed graphs. The assumption that S is diagonalizable is not strictly necessary, and similar estimates hold more generally (Meyer, 1989). The estimate t+ j K+1j tsplits into two terms. The tterm corresponds to kPt S k 1, which accounts for the a…”
BackgroundMethodInfluentialNCDawareRank: a novel ranking method that exploits the decomposable structure of the web
Νικολακόπουλος, Α. Ν., & Garofalakis, J. D. (2013) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/2433396.2433415 · Cited by 34
“The “mathematical fingerprint” of NCD in the PageRank problem is the special spectral structure [11, 23] of the stochastic matrix corresponding to the random walk on the Web graph.”
BackgroundUse of Characteristic Roots for Solving Infinite State Markov Chains
Gail, H. R., Hantler, S. L., & Taylor, B. A. (2000) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4757-4828-4_7 · Cited by 34
Graphs and Stochastic Automata Networks
Fourneau, J.-M., & Quessette, F. (1995) · Springer eBooks · doi:10.1007/978-1-4615-2241-6_14 · Cited by 33
ETAQA: an efficient technique for the analysis of QBD-processes by aggregation
Ciardo, G., & Smirni, E. (1999) · Performance Evaluation · doi:10.1016/s0166-5316(99)00030-9 · Cited by 33
“3 Relations to stochastic complementation Readers familiar with the concept of stochastic complementation [11] will have realized that it is related to the idea we used in the previous section.”
BackgroundFrom Molecular Dynamics to Conformation Dynamics in Drug Design
Deuflhard, P. (2003) · Springer eBooks · doi:10.1007/978-3-662-05281-5_6 · Cited by 31
“Then, for a reversible Markov chain, the total transition matrix T is strictly block diagonal with block submatrices {T1, ..., Tk} - see, e.g., [ 21 ].”
BackgroundAnalysis of Markov Influence Graphs
Berkhout, J., & Heidergott, B. (2019) · Operations Research · doi:10.1287/opre.2018.1813 · Cited by 32
“The phenomenon that aMarkov chain P has sets of nodes that are relatively more close has been frequently observed in the literature: It is called homophily in social networks (Mcpherson et al. 2001) and is known as nearly decomposability1 in Markov chain theory (Meyer 1989, Stewart 1994).”
A Link Analysis Extension of Correspondence Analysis for Mining Relational Databases
Yen, L., Saerens, M., & Fouss, F. (2010) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.142 · Cited by 30
“…as in (9), is defined as (see, for instance, [41]) P c ¼ P 11 þ P 12 ðI À P 22 Þ À1 P 21 : ð10Þ It can be shown that the matrix P c is stochastic, that is, the sum of the elements of each row is equal to 1 [41]; it therefore corresponds to a valid transition matrix between states of interest.”
BackgroundMethodInfluentialM/G/1-Type Markov Processes: A Tutorial
Riska, A., & Smirni, E. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45798-4_3 · Cited by 28
“To illustrate the existence of the geometric relationship among the various stationary probability vectors π, we use the concept of stochastic complementation [22].”
MethodNearly reducible finite Markov chains: Theory and algorithms
Sharpe, D., & Wales, D. J. (2021) · The Journal of Chemical Physics · doi:10.1063/5.0060978 · Cited by 29
On the Effects of Using the Grassmann–Taksar–Heyman Method in Iterative Aggregation–Disaggregation
Dayar, T., & Stewart, W. J. (1996) · SIAM Journal on Scientific Computing · doi:10.1137/0917021 · Cited by 27
Bounding of performance measures for a threshold-based queueing system with hysteresis
Golubchik, L., & Lui, J. C. S. (1997) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/258612.258684 · Cited by 27
Hierarchical Uncoupling-Coupling of Metastable Conformations
Fischer, A., Schütte, C., Deuflhard, P., & Cordes, F. S. (2002) · Lecture notes in computational science and engineering · doi:10.1007/978-3-642-56080-4_10 · Cited by 27
Block cyclic SOR for Markov chains with p-cyclic infinitesimal generator
Kontovasilis, K. P., Plemmons, R. J., & Stewart, W. J. (1991) · Linear Algebra and its Applications · doi:10.1016/0024-3795(91)90377-9 · Cited by 27
Markov Chain Models of Ion Channels and Calcium Release Sites
Groff, J. R., DeRemigio, H., & Smith, G. D. (2009) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199235070.003.0002 · Cited by 26
Meyer, C. D., & Wessell, C. D. (2012) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/100804395 · Cited by 28
“ctice to cluster data. 2.1. Theoretical background. The method introduced here is based on the variable aggregation work of Simon and Ando [17] and owes much to the writings of Courtois [4] and Meyer [14] which claried the earlier work and updated the notation therein. Simon-Ando theory was originally designed as a wa…”
BackgroundMethodInfluentialSelf-citationAlgorithmic Complexity of Power Law Networks
Brach, P., Cygan, M., Łącki, J., & Sankowski, P. (2015) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974331.ch91 · Cited by 34
AggregateRank: bringing order to web sites
Feng, G., Liu, T., Wang, Y., Bao, Y., Ma, Z.-M., Zhang, X., & Ma, W. (2006) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/1148170.1148187 · Cited by 24
“To tackle these aforementioned problems, we propose a novel method based on the theory of stochastic complement [15] to calculate the rank of a website that can approximate the PageRankSum accurately, while the corresponding computational complexity is lower than PageRankSum.”
BackgroundMethodInfluentialIterative disaggregation for a class of lumpable discrete-time stochastic automata networks
Юрьевич, Г. О., Dayar, T., & Fourneau, J.-M. (2003) · Performance Evaluation · doi:10.1016/s0166-5316(02)00227-4 · Cited by 23
Estimating the global pagerank of web communities
Davis, J. V., & Dhillon, I. S. (2006) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1150402.1150419 · Cited by 23
Performance/availability modeling with the TANGRAM-II modeling environment
Carmo, R. M. L. R., de Carvalho, L. R., Suva, E. D. S. E., Diniz, M. C., & Muntz, R. R. (1998) · Performance Evaluation · doi:10.1016/s0166-5316(98)00011-x · Cited by 23
Golubchik, L., & Lui, J. C. S. (2002) · IEEE Transactions on Computers · doi:10.1109/12.995445 · Cited by 24
Computing Moments of First Passage Times to a Subset of States in Markov Chains
Dayar, T., & Akar, N. (2005) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479804442462 · Cited by 22
Stochastic Automata Networks and Near Complete Decomposability
Юрьевич, Г. О., Dayar, T., & Fourneau, J.-M. (2001) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s089547980036975x · Cited by 21
“Hence, NCD MCs are said to be ill-conditioned [15, p. 258].”
BackgroundAggregation of Markov flows I: theory
MacKay, R. S., & Robinson, J. D. (2018) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2017.0232 · Cited by 21
“After writing the paper, we became aware of the stochastic complementation method of [24], which is closely related but different in some ways.”
BackgroundMethodInfluentialStable Computation of Probability Densities for Metastable Dynamical Systems
Weber, M., Röblitz, S., Walter, L., & Deuflhard, P. (2007) · Multiscale Modeling and Simulation · doi:10.1137/060675423 · Cited by 21
A Two-Stage Algorithm for Computing PageRank and Multistage Generalizations
Lee, C. P., Golub, G. H., & Zenios, S. A. (2007) · Internet Mathematics · doi:10.1080/15427951.2007.10129151 · Cited by 25
“These techniques come from the applied probability literature (see, for example, [Cao and Stewart 85, Meyer 89, Simon and Ando 61]).”
BackgroundMethodSilvestrov, D. S., & Silvestrov, S. D. (2017) · AIP conference proceedings · doi:10.1063/1.4972739 · Cited by 19
“…Semal (1984b), Seneta (1984), Cao and Stewart (1985), Vantilborgh (1985), Feinberg and Chiu (1987), Haviv (1987, 1992, 1999), Sumita and Reiders (1988), Meyer (1989), Schweitzer (1991), Stewart and Zhang (1991), Stewart (1993a), Kim and Smith (1995) and Avrachenkov, Filar and Howlett (2013),…”
BackgroundIntegrated Performance Evaluation of Extended Queueing Network Models with Line
Casale, G. (2020) · Winter Simulation Conference · doi:10.1109/wsc48552.2020.9383931 · Cited by 19
“Thanks to the royalty-free MATLAB compiler runtime, LINE can also be used without a MATLAB license, for example as an external solver for the Palladio Simulator for software engineers (P´erez and Casale 2013; Heinrich et al. 2018).”
MethodComponentwise accurate fluid queue computations using doubling algorithms
Nguyen, G. T., & Poloni, F. (2014) · Numerische Mathematik · doi:10.1007/s00211-014-0675-4 · Cited by 19
Statistical error estimation and grid-free hierarchical refinement in conformation dynamics
Röblitz, S. (2009) · Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver · doi:10.17169/refubium-12330 · Cited by 19
“For the same reason, the partial densities are well-conditioned and can be computed with higher accuracy by stochastic complementation [70]; see Figure 6.”
BackgroundMethodInfluentialCensoring Markov Chains and Stochastic Bounds
Fourneau, J., Pekergin, N., & Younès, S. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-75211-0_16 · Cited by 18
“When Q is irreducible the transition probability matrix of the censored chains is the stochastic complement matrix defined by Meyer and we have the following results [11]: Theorem 2.”
BackgroundMethodExtracting spatial information from networks with low-order eigenvectors
Cucuringu, M., Blondel, V. D., & Dooren, P. M. V. (2013) · Physical Review E · doi:10.1103/physreve.87.032803 · Cited by 20
A direct projection method for Markov chains
Michele Benzi, A. (2004) · Linear Algebra and its Applications · doi:10.1016/j.laa.2003.12.019 · Cited by 18
“On this problem GTH and SDPM display comparable accuracy, with an error one order of magnitude smaller than the other methods.”
ResultReduced-complexity filtering for partially observed nearly completely decomposable Markov chains
Dey, S. (2000) · IEEE Transactions on Signal Processing · doi:10.1109/78.886997 · Cited by 18
“In [7], stochastic complementation was used to develop an aggregation procedure to obtain the exact stationary distribution.”
MethodA Dynamic Algorithm for Updating Katz Centrality in Graphs
Nathan, E., & Bader, D. A. (2017) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1145/3110025.3110034 · Cited by 17
“By using exact [10] and approximate [11] aggregation techniques, the transition matrix is efficiently updated after the graph is changed.”
MethodModularity revisited: A novel dynamics-based concept for decomposing complex networks
Sarich, M., Conrad, N. D., Bruckner, S., Conrad, T., & Schütte, C. (2014) · Journal of Computational Dynamics · doi:10.3934/jcd.2014.1.191 · Cited by 20
“There is rich literature addressing different variants of the problems of identifying dominant metastable sets of Markov processes (Meila and Shi, 2001; Doyle and Snell, 2000; Meerbach et al., 2005; Mattingly, 1995; Cho and Meyer, 1999; Meyer, 1989; Marek and Mayer, 2001; Deuflhard and Weber, 2005) and similar related…”
BackgroundConditional steady-state bounds for a subset of states in Markov chains
Dayar, T., Pekergin, N., & Younès, S. (2006) · doi:10.1145/1190366.1190368 · Cited by 17
“INTRODUCTION Let P denote the transition probability matrix of an irreducible discrete-time Markov chain (DTMC) [14] de.ned on the .nite state space Swith n states and the block par titioning » P = PA,A PB,A PA,B PB,B nA nB , (1) where A.B= S, AnB= Ø, and nA and nB are respectively the number…”
BackgroundBelhadj, M., & Aldemir, T. (1996) · Reliability Engineering & System Safety · doi:10.1016/0951-8320(95)00144-1 · Cited by 17
Trace-driven steady-state probability estimation in FSMs with application to power estimation
Marculescu, D., Mărculescu, R., & Pedram, M. (1998) · doi:10.5555/368058.368413 · Cited by 17
Johnson, C. R., Smith, R. L., & Tsatsomeros, M. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108778619 · Cited by 16
Modeling, analysis, measurement and experimentation with the Tangram-II integrated environment
Silva, E. D. S. E., da Silva, A. P. C., Rocha, A. A. D. A., Leão, R. M. M., Duarte, F. P., Filho, F. J. S., Jaime, G. D. G., & Muntz, R. R. (2006) · International ICST Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS) · doi:10.1145/1190095.1190103 · Cited by 16
“The tool’s direct method of choice is the so called GTH algorithm [27] (and its block version) which is a stable LU decomposition method for Markov chains based on stochastic complementation [ 44 ].”
MethodAn exact aggregation/disaggregation algorithm for large scale markov chains
Kim, D. S., & Smith, R. L. (1995) · Naval Research Logistics (NRL) · doi:10.1002/1520-6750(199510)42:7 · Cited by 15
Haviv, M. (1992) · Stochastic Models · doi:10.1080/15326349208807239 · Cited by 15
A Variable Rate Fronthaul Scheme for Cloud Radio Access Networks
Das, S., & Ruffini, M. (2019) · Journal of Lightwave Technology · doi:10.1109/jlt.2019.2912127 · Cited by 15
“Meyer in 1989 [21] provides a way of decoupling a Markov”
On Perron complements of totally nonnegative matrices
Fallat, S., & Neumann, M. (2001) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(00)00312-8 · Cited by 15
Trace-driven steady-state probability estimation in FSMs with application to power estimation
Marculescu, D., Mărculescu, R., & Pedram, M. (2002) · Design, Automation, and Test in Europe · doi:10.1109/date.1998.655946 · Cited by 15
“[16] Let Q be an×n irreducible stochastic matrix partitioned as”
BackgroundAsymptotic Expansions for Stationary Distributions of Perturbed Semi-Markov Processes
Silvestrov, D. S., & Silvestrov, S. D. (2016) · International Symposium on Stochastic Models in Reliability Engineering, Life Science and Operations Management · doi:10.1109/smrlo.2016.18 · Cited by 14
Analysis and interpretation of first passage time distributions featuring rare events
Woods, E. J., & Wales, D. J. (2024) · Physical Chemistry Chemical Physics · doi:10.1039/d3cp04199a · Cited by 18
Optimal dimensionality reduction of Markov chains using graph transformation
Kannan, D., Sharpe, D., Swinburne, T. D., & Wales, D. J. (2020) · The Journal of Chemical Physics · doi:10.1063/5.0025174 · Cited by 16
Eigenvalue bounds on restrictions of reversible nearly uncoupled Markov chains
Meerbach, E., Schütte, C., & Fischer, A. (2004) · Linear Algebra and its Applications · doi:10.1016/j.laa.2004.10.018 · Cited by 19
Convergence analysis of an improved pagerank algorithm
Ipsen, I. C. F., & Kirkland, S. (2004) · NCSU Libraries Repository (North Carolina State University Libraries) · Cited by 14
Metadata
- Authors
- Meyer, C. D.
- Corresponding author
- Meyer, Carl D.
- Venue
- SIAM Review
- Published
- 1989-06
- Volume
- 31
- Issue
- 2
- Pages
- 240-272
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2042624802
- Cited by
- 316
- References
- 21
- Citations by year
- 2026: 2 · 2025: 4 · 2024: 3 · 2023: 4 · 2022: 7 · 2021: 14 · 2020: 17 · 2019: 12 · 2018: 6 · 2017: 14 · 2016: 8 · 2015: 8 · 2014: 9 · 2013: 15 · 2012: 18
- FWCI
- 3.53
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Review (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Physical Sciences › Mathematics › Mathematical Physics › Mathematical Dynamics and Fractals
- Keywords
- finite Markov chains, Markov chain decomposition, stochastic matrices
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.