pith. sign in

arxiv: 1907.02449 · v1 · pith:I7ZZ3ZMTnew · submitted 2019-07-04 · 🧮 math.NA · cs.NA

Tensor methods for the computation of MTTA in large systems of loosely interconnected components

Leonardo Robol , Giulio Masetti This is my paper

Pith reviewed 2026-05-25 09:03 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords mean time to absorptioncontinuous time Markov chainstensor train formatloosely interconnected componentsiterative methodsnumerical linear algebra
0
0 comments X

The pith

Splitting local and synchronization transitions yields a linearly convergent MTTA algorithm that becomes quadratic and scales to billions of states in tensor-train format.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that for continuous-time Markov chains modeling systems of loosely interconnected components, separating the local transitions within each component from the synchronization transitions between them produces an iterative method for computing the mean-time-to-absorption. The basic version of this method is proven to converge linearly, and a modification achieves quadratic convergence even when the linear rate is close to one. Because the separation keeps the operators in a form that factors nicely across components, all matrices and vectors can be stored and manipulated in the tensor-train format, which the authors demonstrate allows treatment of systems whose full state space reaches billions of states.

Core claim

By decoupling local and synchronization transitions, the authors formulate an algorithm for the MTTA that converges linearly and can be accelerated to quadratic convergence, while the same decoupling permits all matrices and vectors to be represented in tensor-train format, enabling numerical solution of problems with up to billions of states.

What carries the argument

The decoupling of local and synchronization transitions, which produces both the convergent iteration and the low-rank tensor-train structure.

If this is right

  • The algorithm converges linearly to the exact MTTA value.
  • A simple modification upgrades the convergence rate to quadratic.
  • Tensor-train storage keeps memory and arithmetic costs independent of the full state-space size.
  • Systems with up to billions of states become numerically tractable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same local-synchronization split could be used to compute absorption probabilities or other transient quantities in the same model class.
  • Quadratic convergence removes the iteration count penalty that appears when the linear rate is close to one.
  • Tensor-train techniques developed here may transfer directly to steady-state analysis of loosely coupled continuous-time Markov chains.

Load-bearing premise

The components must be loosely interconnected so that separating local and synchronization transitions both produces fast convergence and keeps the tensor-train ranks small.

What would settle it

Applying the method to a system whose components are tightly coupled and observing either failure of linear convergence or tensor-train ranks that grow linearly with the number of components.

Figures

Figures reproduced from arXiv: 1907.02449 by Giulio Masetti, Leonardo Robol.

Figure 1
Figure 1. Figure 1: Example SAN for the case study where there are 4 comp [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Average timings as a function of k for Algorithm 3. For this case study, the timings appear to depend on k polynomially, with exponent close to 3.5. 19 [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Maximum TT-Rank of M during the iteration of Algorithm 2 for two runs with k = 24. The runs with smaller ranks took 4.55s, while the other needed 72.30s. when k > 10, so we could only make a direct comparison in [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
read the original abstract

We are concerned with the computation of the mean-time-to-absorption (MTTA) for a large system of loosely interconnected components, modeled as continuous time Markov chains. In particular, we show that splitting the local and synchronization transitions of the smaller subsystems allows to formulate an algorithm for the computation of the MTTA which is proven to be linearly convergent. Then, we show how to modify the method to make it quadratically convergent, thus overcoming the difficulties for problems with convergent rate close to $1$. In addition, it is shown that this decoupling of local and synchronization transitions allows to easily represent all the matrices and vectors involved in the method in the tensor-train (TT) format - and we provide numerical evidence showing that this allows to treat large problems with up to billions of states - which would otherwise be unfeasible.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper develops an iterative method for computing mean time to absorption (MTTA) in continuous-time Markov chains composed of loosely interconnected components. By separating local transitions from synchronization transitions, it derives a linearly convergent algorithm that is then accelerated to quadratic convergence; the resulting operators admit low-rank tensor-train representations, enabling numerical solution of systems with up to 10^9 states.

Significance. If the stated convergence proofs and TT-rank bounds hold under the modeling assumptions, the work supplies a practical route to MTTA computation for state spaces that are otherwise intractable, together with explicit linear and quadratic rates and reproducible numerical evidence on billion-state instances. These elements constitute a concrete advance for reliability and performance analysis of large stochastic systems.

minor comments (3)
  1. [Abstract] Abstract, line 4: 'convergent rate' should read 'convergence rate'.
  2. [§5] §5, Table 2: the reported TT-ranks for the largest instances are given only as upper bounds; explicit per-iteration ranks would strengthen the reproducibility claim.
  3. [§3.2] Notation for the synchronization matrix S is introduced in §2 but first used in §3.2 without a forward reference; a brief reminder would aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript and the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation begins from standard continuous-time Markov chain (CTMC) modeling of loosely interconnected components and proceeds by splitting local versus synchronization transitions to obtain a linearly convergent iteration for mean-time-to-absorption (MTTA); the iteration is then algebraically modified to quadratic convergence, after which the resulting operators are shown to admit low-rank tensor-train representations. None of these steps reduces by construction to a fitted parameter, a self-referential definition, or a load-bearing self-citation; the convergence proofs and TT-rank bounds rest on the explicit separation of transition classes and on the Kronecker structure of the infinitesimal generator, both of which are external to the algorithm itself. The abstract and manuscript description therefore remain self-contained against external CTMC and tensor-algebra benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that the system admits a clean separation into local and synchronization transitions whose product structure is compatible with tensor-train compression; no free parameters or invented entities are mentioned.

axioms (1)
  • standard math Standard properties of continuous-time Markov chains and the integral formula for mean time to absorption
    Invoked implicitly as the starting point for the MTTA computation.

pith-pipeline@v0.9.0 · 5668 in / 1206 out tokens · 42449 ms · 2026-05-25T09:03:58.114901+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · 2 internal anchors

  1. [1]

    J., 1994

    Berman, A., Plemmons, R. J., 1994. Nonnegative matrices in the ma th- ematical sciences. Vol. 9 of Classics in Applied Mathematics. Society f or Industrial and Applied Mathematics (SIAM), Philadelphia, PA, revise d reprint of the 1979 original. URL https://doi.org/10.1137/1.9781611971262

    work page doi:10.1137/1.9781611971262 1994

  2. [2]

    Multigrid methods combined with low-rank approximation for tensor structured Markov chains

    Bolten, M., Kahl, K., Kressner, D., Macedo, F., Sokolovi´ c, S., 201 6. Multi- grid methods combined with low-rank approximation for tensor stru ctured markov chains. arXiv preprint arXiv:1605.06246

    work page internal anchor Pith review Pith/arXiv arXiv

  3. [3]

    Approximation of 1 /x by exponential sums in [1 ,∞ )

    Braess, D., Hackbusch, W., 2005. Approximation of 1 /x by exponential sums in [1 ,∞ ). IMA journal of numerical analysis 25 (4), 685–697

    work page 2005

  4. [4]

    C., 2017

    Buchholz, P., Dayar, T., Kriege, J., Orhan, M. C., 2017. On compac t solu- tion vectors in Kronecker-based Markovian analysis. Performanc e Evalua- tion 115, 132–149

    work page 2017

  5. [5]

    Kronecker based matrix repres entations for large Markov models

    Buchholz, P., Kemper, P., 2004. Kronecker based matrix repres entations for large Markov models. Springer, pp. 256–295

    work page 2004

  6. [6]

    S., 1999

    Ciardo, G., Miner, A. S., 1999. A data structure for the efficient K ronecker solution of GSPNs. In: Proceedings 8th International Workshop o n Petri Nets and Performance Models (Cat. No.PR00331). pp. 22–31

    work page 1999

  7. [7]

    The numerical range as a spectral set

    Crouzeix, M., Palencia, C., 2017. The numerical range as a spectr al set. arXiv preprint arXiv:1702.00668

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  8. [8]

    A multilinear sin gu- lar value decomposition

    De Lathauwer, L., De Moor, B., Vandewalle, J., 2000. A multilinear sin gu- lar value decomposition. SIAM Journal of Matrix Analysis and Applicat ions 21 (4), 1253–1278. URL https://doi.org/10.1137/S0895479896305696

    work page doi:10.1137/s0895479896305696 2000

  9. [9]

    Tensor rank and the ill-posedness of t he best low-rank approximation problem

    de Silva, V., Lim, L.-H., 2008. Tensor rank and the ill-posedness of t he best low-rank approximation problem. SIAM Journal of Matrix Analy sis and Applications 30 (3), 1084–1127. URL https://doi.org/10.1137/06066518X

    work page doi:10.1137/06066518x 2008

  10. [10]

    W., 1997

    Demmel, J. W., 1997. Applied numerical linear algebra. Society for Indus- trial and Applied Mathematics (SIAM), Philadelphia, PA. URL https://doi.org/10.1137/1.9781611971446

    work page doi:10.1137/1.9781611971446 1997

  11. [11]

    V., Khoromskij, B

    Dolgov, S. V., Khoromskij, B. N., Oseledets, I. V., 2012. Fast so lution of parabolic problems in the tensor train/quantized tensor train fo rmat with initial application to the Fokker-Planck equation. SIAM Journal of Scientific Computing 34 (6), A3016–A3038. URL https://doi.org/10.1137/120864210 21

    work page doi:10.1137/120864210 2012

  12. [12]

    V., Savostyanov, D

    Dolgov, S. V., Savostyanov, D. V., 2014. Alternating minimal ene rgy meth- ods for linear systems in higher dimensions. SIAM Journal on Scientifi c Computing 36 (5), A2248–A2271

    work page 2014

  13. [13]

    Superposed stochastic automata: A class o f stochastic petri nets with parallel solution and distributed state space

    Donatelli, S., 1993. Superposed stochastic automata: A class o f stochastic petri nets with parallel solution and distributed state space. Perf ormance Evaluation 18 (1), 21–36

    work page 1993

  14. [14]

    Hierarchical singular value decomposition of tensors

    Grasedyck, L., 2010. Hierarchical singular value decomposition of tensors. SIAM Journal on Matrix Analysis and Applications 31 (4), 2029–2054

    work page 2010

  15. [15]

    Computation of best l∞ exponential sums for 1 /x by remez algorithm

    Hackbusch, W., 2019. Computation of best l∞ exponential sums for 1 /x by remez algorithm. Computing and Visualization in Science 20 (1-2), 1–1 1

    work page 2019

  16. [16]

    J., 2008

    Higham, N. J., 2008. Functions of matrices. Society for Indust rial and Ap- plied Mathematics (SIAM), Philadelphia, PA, theory and computation . URL https://doi.org/10.1137/1.9780898717778

    work page doi:10.1137/1.9780898717778 2008

  17. [17]

    J., Lim, L.-H., 2013

    Hillar, C. J., Lim, L.-H., 2013. Most tensor problems are np-hard. Journal of the ACM (JACM) 60 (6), 45

    work page 2013

  18. [18]

    A Compositional Approach to Performance Mo delling

    Hillston, J., 1996. A Compositional Approach to Performance Mo delling. Cambridge University Press, New York, NY, USA

    work page 1996

  19. [19]

    A., Khoromskij, B

    Kazeev, V. A., Khoromskij, B. N., 2012. Low-rank explicit QTT re presen- tation of the Laplace operator and its inverse. SIAM Journal of Ma trix Analysis and Applications 33 (3), 742–758. URL https://doi.org/10.1137/100820479

    work page doi:10.1137/100820479 2012

  20. [20]

    G., Bader, B

    Kolda, T. G., Bader, B. W., 2009. Tensor decompositions and app lications. SIAM Rev. 51 (3), 455–500. URL https://doi.org/10.1137/07070111X

    work page doi:10.1137/07070111x 2009

  21. [21]

    Low-rank tensor methods fo r communicat- ing markov processes

    Kressner, D., Macedo, F., 2014. Low-rank tensor methods fo r communicat- ing markov processes. In: International Conference on Quantit ative Eval- uation of Systems. Springer, pp. 25–40

    work page 2014

  22. [22]

    Algorithm 941: htucker–a Matlab tool- box for tensors in hierarchical Tucker format

    Kressner, D., Tobler, C., 2014. Algorithm 941: htucker–a Matlab tool- box for tensors in hierarchical Tucker format. ACM Trans. Math. Software 40 (3), Art. 22, 22. URL https://doi.org/10.1145/2538688

    work page doi:10.1145/2538688 2014

  23. [23]

    V., Vandereycken, B., 2015

    Lubich, C., Oseledets, I. V., Vandereycken, B., 2015. Time integ ration of tensor trains. SIAM Journal of Numerical Analysis 53 (2), 917–94 1. URL https://doi.org/10.1137/140976546

    work page doi:10.1137/140976546 2015

  24. [24]

    Computing performability measures in markov chains by means of matrix functions

    Masetti, G., Robol, L., 2018. Computing performability measures in markov chains by means of matrix functions. arXiv preprint arXiv:1803.06322. 22

    work page arXiv 2018

  25. [25]

    Stochastic evaluation of large interdependent composed models th rough kronecker algebra and exponential sums

    Masetti, G., Robol, L., Chiaradonna, S., Di Giandomenico, F., 2019 . Stochastic evaluation of large interdependent composed models th rough kronecker algebra and exponential sums. In: Application and Theo ry of Petri Nets and Concurrency. pp. 47–66

    work page 2019

  26. [26]

    MATLAB R2018a

    MathWorks, 2018. MATLAB R2018a. The Mathworks, Inc., Nat ick, Mas- sachusetts

    work page 2018

  27. [27]

    MAT- LAB TT-Toolbox

    Oseledets, I., Dolgov, S., Kazeev, V., Lebedeva, O., Mach, T., 20 19. MAT- LAB TT-Toolbox. https://github.com/oseledets/TT-Toolbox

    work page

  28. [28]

    V., 2011

    Oseledets, I. V., 2011. Tensor-train decomposition. SIAM Jou rnal of Scien- tific Computing 33 (5), 2295–2317. URL https://doi.org/10.1137/090752286

    work page doi:10.1137/090752286 2011

  29. [29]

    V., Dolgov, S

    Oseledets, I. V., Dolgov, S. V., 2012. Solution of linear systems a nd matrix inversion in the tt-format. SIAM Journal on Scientific Computing 34 (5), A2718–A2739

    work page 2012

  30. [30]

    J., 2000

    Plateau, B., Stewart, W. J., 2000. Stochastic Automata Netwo rks. Springer US, Boston, MA, pp. 113–151

    work page 2000

  31. [31]

    S., Bobbio, A., 2017

    Trivedi, K. S., Bobbio, A., 2017. Reliability and Availability Engineering : Modeling, Analysis, and Applications. Cambridge University Press

    work page 2017

  32. [32]

    S., Bobbio, A., 2017

    Trivedi, K. S., Bobbio, A., 2017. Reliability and Availability Engineering : Modeling, Analysis, and Applications. Cambridge University Press. 23

    work page 2017