On Mixed-Precision Iterative Methods and Analysis for Nearly Completely Decomposable Markov Processes

Beyond their broad applications, NCD structural properties represent a fundamental area in the theory of Markov processes. The most efficient approaches for computing the stationary distribution π of such NCD Markov processes are based on similar forms of aggregation-disaggregation. Despite significant performance benefits, these methods can still be prohibitively expensive for large-scale processes and/or realtime settings. Our focus is therefore on general NCD Markov processes and on the design and analysis of a general mathematical framework for computing the π of NCD processes that addresses the performance bottlenecks of existing methods. Our framework combines: (1) advances in computer architectures related to mixed-precision computation – to reduce computation times at the expense of inaccuracies; (2) advances in iterative approximate computing methods – to mitigate inaccuracies, further reduce computation times, and guarantee convergence. We derive a mathematical analysis that establishes theoretical properties of our general framework, including convergence rates, and then present numerical experiments that demonstrate orders of magnitude improvements in computation times over existing methods. We note that our general mathematical framework can be analogously exploited within the context of numerical methods for general Markov processes beyond those having NCD structural properties. This short paper briefly summarizes our full paper [1] to which we refer the reader for all details.