Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems

DOI10.1137/1031050zbMath0685.65129OpenAlexW2042624802MaRDI QIDQ4203792

Publication date: 1989

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/0e1761b91996cefebe1d3e00b66f3e00f3e6d53c

zbMATH Keywords

fast algorithms parallel computation reduction Markov chain discrete parameters irreducible stochastic matrix multiprocessor computers stochastic complementation divide-and-conquer principle

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) General equilibrium theory (91B50) Stochastic matrices (15B51) Probabilistic methods, stochastic differential equations (65C99)

Related Items

Fast reactions with non-interacting species in stochastic reaction networks ⋮ Total nonnegativity of the extended Perron complement ⋮ A parallel solver for large-scale Markov chains ⋮ Replacement process decomposition for discounted Markov renewal programming ⋮ Multi-scale metastable dynamics and the asymptotic stationary distribution of perturbed Markov chains ⋮ Unnamed Item ⋮ Fuzzy spectral clustering by PCCA+: application to Markov state models and data classification ⋮ A divide and conquer approach to computing the mean first passage matrix for Markov chains via Perron complement reductions ⋮ Stochastic complements in substochastic Matrices^∗ ⋮ Design of biased random walks on a graph with application to collaborative recommendation ⋮ A solver for the stochastic master equation applied to gene regulatory networks ⋮ Estimating random walk centrality in networks ⋮ On symbolic RG factorization of quasi-birth-and-death processes ⋮ Asymptotic Expansions for Stationary Distributions of Perturbed Semi-Markov Processes ⋮ Analysis of Markov Influence Graphs ⋮ Stochastic Bounds for Partially Generated Markov Chains: An Algebraic Approach ⋮ Block cyclic SOR for Markov chains with \(p\)-cyclic infinitesimal generator ⋮ A direct projection method for Markov chains ⋮ A partitioning algorithm for solving systems of linear equations ⋮ Computing mean first passage times for a Markov chain ⋮ Modularity revisited: a novel dynamics-based concept for decomposing complex networks ⋮ Basic Soules matrices and their applications ⋮ Bounding the equilibrium distribution of Markov population models ⋮ Stationary Distributions of Continuous-Time Markov Chains: A Review of Theory and Truncation-Based Approximations ⋮ Aggregation of Markov flows I: theory ⋮ Computing the fundamental matrix for a nonirreducible Markov chain ⋮ Blockwise perturbation theory for nearly uncoupled Markov chains and its application ⋮ Schur complements and its applications to symmetric nonnegative and \(Z\)-matrices ⋮ On Perron complements of totally nonnegative matrices ⋮ Exact algorithms for singular tridiagonal systems with applications to Markov chains ⋮ Inverse \(M\)-matrices. II ⋮ Componentwise bounds for nearly completely decomposable Markov chains using stochastic comparison and reordering ⋮ Eigenvalue bounds on restrictions of reversible nearly uncoupled Markov chains ⋮ Robust Perron cluster analysis in conformation dynamics ⋮ On single and double Soules matrices ⋮ A combined approach for evaluating papers, authors and scientific journals ⋮ Optimal bulking threshold of batch service queues ⋮ Analyzing discrete-time \(GI^{[X}/D-MSP/1/\infty\) queueing system using \(RG\)-factorization] ⋮ The Markov chain tree theorem in commutative semirings and the state reduction algorithm in commutative semifields ⋮ Inequalities for permanents involving Perron complements ⋮ A multiscale environment for learning by diffusion ⋮ Accurate numerical solution for shifted \(M\)-matrix algebraic Riccati equations ⋮ TOPOLOGICAL VERSUS DYNAMICAL ROBUSTNESS IN A LEXICAL NETWORK ⋮ Inverses of Perron complements of inverse \(M\)-matrices ⋮ Diffusion State Distances: Multitemporal Analysis, Fast Algorithms, and Applications to Biological Networks ⋮ Identification of almost invariant aggregates in reversible nearly uncoupled Markov chains ⋮ Parallel computing for Markov chains with islands and ports ⋮ Estimating equilibrium probabilities for band diagonal Markov chains using aggregation and disaggregation techniques ⋮ Singularly Perturbed Markov Modulated Fluid Queues ⋮ Componentwise accurate fluid queue computations using doubling algorithms ⋮ State reduction in a Markov decision process

This page was built for publication: Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems