Pith. sign in

REVIEW 1 minor 1 cited by

Algebraic and FFT-Based Methods for Discrete-Time Matrix Convolutions with Applications to Semi-Markov Models

T0 review · 0 major / 1 minor · reviewed 2026-07-01 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Finite-horizon matrix convolution equations admit exact algebraic inversion via FFT multiplication and yield residual bounds for semi-Markov computations.

desk verdict This paper gives a usable algebraic-plus-FFT solver for finite-horizon matrix convolutions in semi-Markov models, with explicit exactness proofs and discretization error bounds that hold up on the stated assumptions. read the letter →

arxiv 2605.30379 v3 pith:2XVKFHOX submitted 2026-05-27 math.NA cs.NAmath.PR

L.Kordalis , S.Trevezas This is my paper · ORCID
classification math.NAcs.NAmath.PR
keywords matrixconvolutionssemi-Markovmodelsfinite-horizoninversionFFTmultiplicationMarkovrenewalequationsresidualboundsdiscretizationerrortransitionprobabilities
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper develops methods to solve finite-horizon convolution equations with matrix-valued coefficients that arise in Markov renewal computations. It proves exactness of the inversion in a truncated noncommutative series algebra together with deterministic perturbation identities and left and right a posteriori residual bounds. Explicit coefficient formulae are combined with zero-padded FFT multiplication, Newton iteration and Gauss-Jordan elimination to achieve the inversion. For continuous-time semi-Markov equations an endpoint mean-value rule converts Stieltjes convolutions into discrete ones, producing error estimates that give second-order convergence for smooth kernels. The resulting framework computes transition probabilities, first-entrance distributions, reliability, availability, renewal visits and reward-type quantities while reducing the cost of long-horizon calculations.

What carries the argument

Inversion of sequences in the truncated noncommutative series algebra combined with zero-padded FFT multiplication for matrix products.

What would settle it

A direct numerical comparison of the discrete inversion output against an independently computed exact solution of a known continuous-time semi-Markov process with a smooth kernel, for increasing horizon lengths, would confirm or refute the second-order convergence rate.

Watch

Extended reading notes

Core claim

By inverting sequences in a truncated noncommutative series algebra with explicit coefficient formulae, zero-padded fast Fourier transform multiplication, Newton iteration and Gauss-Jordan elimination, finite-horizon matrix convolution equations can be solved exactly, yielding deterministic perturbation identities and left and right a posteriori residual bounds. The same framework applies to semi-Markov models, where an endpoint mean-value rule converts continuous-time Stieltjes convolutions to discrete ones, with error estimates showing second-order convergence for smooth kernels, allowing computation of transition probabilities, first-entrance distributions, reliability, availability, rene

Load-bearing premise

The endpoint mean-value rule converts matrix Stieltjes convolutions into discrete matrix convolutions with error estimates obtained under bounded-variation and smoothness assumptions.

Editorial extensions

If this is right

  • The inversion computes transition probabilities in semi-Markov models for any finite horizon.
  • It computes first-entrance distributions, reliability, availability, renewal visits and reward-type quantities with the same code.
  • Error estimates under bounded-variation and smoothness assumptions give second-order convergence for smooth kernels.
  • The methods scale with horizon length and state dimension while preserving probabilistic accuracy.
  • Rounding and transform errors in the FFT step are accounted for in the residual bounds.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The residual bounds could support adaptive choice of horizon length in applications where computation time is limited.
  • The discretization approach may extend to other integral equations that admit Stieltjes convolution structure beyond the semi-Markov setting.
  • For very large state spaces the FFT-based matrix products could be further accelerated by block or parallel implementations not examined in the paper.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 1 minor

Summary. The paper develops algebraic methods (truncated noncommutative series inversion with explicit coefficients, Newton iteration, Gauss-Jordan) combined with zero-padded FFT multiplication for solving finite-horizon discrete-time matrix convolution equations. It proves exactness of the finite-horizon inversion, deterministic perturbation identities, and left/right a posteriori residual bounds, with FFT error analysis for transform and rounding effects. For continuous-time semi-Markov equations, an endpoint mean-value discretization converts Stieltjes convolutions to discrete ones, with error estimates under bounded-variation/smoothness assumptions and a weighted resolvent argument yielding fixed-horizon convergence (second-order for smooth kernels). The framework is applied to compute transition probabilities, first-entrance distributions, reliability, availability, renewal visits, and reward quantities, with numerical experiments on scaling, residuals, first-entrance probabilities, Markov benchmarks, and a heavy-tailed Lognormal model.

Significance. If the central algebraic exactness claims and discretization convergence hold, the work supplies a practical, rigorously bounded solver for matrix convolutions that directly supports multiple probabilistic computations in semi-Markov models. The explicit coefficient formulae, FFT acceleration for long horizons, and second-order discretization error control under standard assumptions constitute a coherent contribution to numerical methods for renewal-type equations. The preservation of probabilistic structure while reducing computational cost for long horizons is a clear practical strength.

minor comments (1)
  1. The abstract and experiments section would benefit from an explicit statement of the precise matrix dimensions and horizon lengths used in the scaling tests to allow direct reproducibility assessment.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, positive summary, and recommendation to accept the manuscript. No major comments were raised.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The derivation relies on explicit algebraic formulae for truncated noncommutative inversion, combined with standard FFT multiplication, Newton iteration, and Gauss-Jordan elimination. Exactness of finite-horizon inversion and residual bounds are proved directly from the algebra. The endpoint mean-value discretization and second-order convergence follow from bounded-variation assumptions and a weighted resolvent argument, which are independent of the target quantities. Probabilistic applications are obtained by direct substitution into the solved convolutions. No self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations appear in the chain; all steps rest on external algebraic and analytic properties.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

Ledger extracted from abstract only; full paper may introduce additional parameters or assumptions not visible here.

assumptions (1)
  • domain assumption bounded-variation and smoothness assumptions on kernels for error estimates and fixed-horizon convergence
    Invoked for continuous-time semi-Markov equations and second-order convergence claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Algebraic and FFT-Based Methods for Discrete-Time Matrix Convolutions with Applications to Semi-Markov Models." pith.science (2026). https://pith.science/paper/2XVKFHOX

@misc{pith2026260530379,
  author       = {Pith},
  title        = {Pith review of: Algebraic and FFT-Based Methods for Discrete-Time Matrix Convolutions with Applications to Semi-Markov Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2XVKFHOX}},
  note         = {Machine review of arXiv:2605.30379}
}
read the original abstract

We consider finite-horizon convolution equations with matrix-valued coefficients and their use in Markov renewal computations. A sequence is inverted in a truncated noncommutative series algebra, and explicit coefficient formulae are combined with zero-padded fast Fourier transform (FFT) multiplication, Newton iteration and Gauss--Jordan elimination. We prove exactness of finite-horizon inversion, deterministic perturbation identities, and left and right a posteriori residual bounds. The FFT analysis includes transform errors and rounding in the frequency-domain matrix products. For continuous-time semi-Markov equations, an endpoint mean-value rule converts matrix Stieltjes convolutions into discrete matrix convolutions. Error estimates are obtained under bounded-variation and smoothness assumptions, and a weighted resolvent argument yields fixed-horizon convergence, with second-order convergence for smooth kernels. The same inversion framework computes transition probabilities, first-entrance distributions, reliability, availability, renewal visits and reward-type quantities. Numerical experiments examine scaling in the horizon and state dimension, residual accuracy, first-entrance probabilities, convergence against an exact Markov benchmark, and a heavy-tailed Lognormal model. The accelerated methods preserve the probabilistic calculations while reducing the cost of long-horizon convolutional inversion.

Figures

Figures reproduced from arXiv: 2605.30379 by the authors.

Figure 1
Figure 1. Relative error of the FFT/IFFT-based convolution product [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Transition structure of the semi-Markov model. [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Transition structure of the semi-Markov model. [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Exponential Markov benchmark: comparison of the proposed Newton–Cotes and discretization [PITH_FULL_IMAGE:figures/full_fig_p022_4.png]
Figure 5
Figure 5. Figure 5: Semi-Markov case with Log-Gamma sojourn times: comparison of the proposed approximations [PITH_FULL_IMAGE:figures/full_fig_p022_5.png]
Figure 6
Figure 6. Figure 6: Semi-Markov case with Weibull sojourn times. [PITH_FULL_IMAGE:figures/full_fig_p037_6.png]
Figure 7
Figure 7. Figure 7: Semi-Markov case with Log-logistic sojourn times. [PITH_FULL_IMAGE:figures/full_fig_p037_7.png]
Figure 8
Figure 8. Figure 8: Semi-Markov case with Log-Cauchy sojourn times. [PITH_FULL_IMAGE:figures/full_fig_p038_8.png]
Figure 9
Figure 9. Figure 9: Semi-Markov case with Fréchet sojourn times. [PITH_FULL_IMAGE:figures/full_fig_p038_9.png]
Figure 10
Figure 10. Figure 10: Semi-Markov case with Lévy sojourn times. [PITH_FULL_IMAGE:figures/full_fig_p039_10.png]
Figure 11
Figure 11. Figure 11: Semi-Markov case with Lognormal sojourn times. [PITH_FULL_IMAGE:figures/full_fig_p039_11.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Multi-time Markov renewal chains and stratified renewal theorems

    math.PR 2026-07 accept novelty 7.0 of 10

    A multi-time Markov renewal theory on partially ordered lattices is developed, yielding stratified inverse-renewal limits that are Gaussian on single-coordinate cells and non-Gaussian minima on interfaces, plus exact-...

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages · cited by 1 Pith paper

  1. [1]

    R. Pyke, R. Schaufele, Limit theorems for markov renewal processes, The Annals of Mathematical Statistics (1964) 1746–1764

    work page 1964

  2. [2]

    Çinlar, Periodicity in markov renewal theory, Advances in Applied Probability 6 (1) (1974) 61–78

    E. Çinlar, Periodicity in markov renewal theory, Advances in Applied Probability 6 (1) (1974) 61–78

    work page 1974

  3. [3]

    Limnios, G

    N. Limnios, G. Oprisan, Semi-Markov processes and reliability, Springer Science & Business Media, 2012

    work page 2012

  4. [4]

    D. R. Cox, Renewal theory, Chapman and Hall (1962)

    work page 1962

  5. [5]

    Barbu, N

    V. Barbu, N. Limnios, Semi-Markov Chains and Hidden Semi-Markov Models Toward Applications: Their Use in Reliability and DNA Analysis, Vol. 191, Springer, 2008

    work page 2008

  6. [6]

    Barbu, M

    V. Barbu, M. Boussemart, N. Limnios, Discrete-time semi-markov model for reliability and survival analysis, Communications in Statistics-Theory and Methods 33 (11) (2004) 2833–2868

    work page 2004

  7. [7]

    G.D’Amico, R.Manca, F.Petroni, D.Selvamuthu, Onthecomputationofsomeinterval reliability indicators for semi-markov systems, Mathematics 9 (5) (2021) 575

    work page 2021

  8. [8]

    Pertsinidou, G

    C. Pertsinidou, G. Tsaklidis, E. Papadimitriou, N. Limnios, Application of hidden semi- markov models for the seismic hazard assessment of the north and south aegean sea, greece, Journal of Applied Statistics 44 (6) (2017) 1064–1085

    work page 2017

Show all 45 references
  1. [9]

    Votsi, N

    I. Votsi, N. Limnios, G. Tsaklidis, E. Papadimitriou, Semi-markov models for seismic hazard assessment in certain areas of greece, Bulletin of the Geological Society of Greece 43 (4) (2010) 2200–2009

    2010

  2. [10]

    Votsi, G

    I. Votsi, G. Gayraud, V. Barbu, N. Limnios, Hypotheses testing and posterior concen- tration rates for semi-markov processes, Statistical Inference for Stochastic Processes 24 (3) (2021) 707–732

    2021

  3. [11]

    Barbu, N

    V. Barbu, N. Limnios, Empirical estimation for discrete-time semi-markov processes with applications in reliability, Journal of Nonparametric Statistics 18 (7-8) (2006) 483–498

    2006

  4. [12]

    Trevezas, N

    S. Trevezas, N. Limnios, Exact mle and asymptotic properties for nonparametric semi- markov models, Journal of Nonparametric Statistics 23 (3) (2011) 719–739

    2011

  5. [13]

    D. J. McConalogue, A. Pacheco, Numerical treatment of convolution integrals involv- ing distributions with densities having singularities at the origin, Communications in Statistics - Simulation and Computation 10 (3) (1981) 265–280

    1981

  6. [14]

    L. A. Baxter, Some remarks on numerical convolution, Communications in Statistics - Simulation and Computation 10 (3) (1981) 281–288. 24

    1981

  7. [15]

    Xie, On the solution of renewal-type integral equations, Communications in Statis- tics - Simulation and Computation 18 (1) (1989) 281–293

    M. Xie, On the solution of renewal-type integral equations, Communications in Statis- tics - Simulation and Computation 18 (1) (1989) 281–293

    1989

  8. [16]

    T. K. Boehme, W. Preuss, V. v. d. Wall, On a simple numerical method for computing stieltjes integrals in reliability theory, Probability in the Engineering and Informational Sciences 5 (1) (1991) 113–128

    1991

  9. [17]

    M. Xie, W. Preuss, L.-R. Cui, Error analysis of some integration procedures for renewal equation and convolution integrals, Journal of Statistical Computation and Simulation 73 (1) (2003) 59–70

    2003

  10. [18]

    R. A. Howard, Dynamic probabilistic systems. Series in decision and control, Wiley, New York, 1971

    1971

  11. [19]

    Stehfest, Algorithm 368: Numerical inversion of laplace transforms, Communications of the ACM 13 (1) (1970) 47 – 49

    H. Stehfest, Algorithm 368: Numerical inversion of laplace transforms, Communications of the ACM 13 (1) (1970) 47 – 49

    1970

  12. [20]

    Finkelstein, V.Zarudnij, Laplace-transforms andfast-repairapproximationsfor mul- tiple availability and its generalizations, IEEE Transactions on Reliability 51 (2) (2002) 168–176

    M. Finkelstein, V.Zarudnij, Laplace-transforms andfast-repairapproximationsfor mul- tiple availability and its generalizations, IEEE Transactions on Reliability 51 (2) (2002) 168–176

    2002

  13. [21]

    Limnios, Dependability analysis of semi-markov systems, Reliability Engineering & System Safety 55 (3) (1997) 203–207

    N. Limnios, Dependability analysis of semi-markov systems, Reliability Engineering & System Safety 55 (3) (1997) 203–207

    1997

  14. [22]

    B. Wu, N. Limnios, A comparative study of numerical methods for reliability assessment based on semi-markov processes, Reliability Engineering & System Safety 252 (2024) 110431

    2024

  15. [23]

    J. W. Cooley, J. W. Tukey, An algorithm for the machine calculation of complex fourier series, Mathematics of Computation 19 (90) (1965) 297–301

    1965

  16. [24]

    Y. Hou, N. Limnios, W. Schön, On the existence and uniqueness of solution of mre and applications, Methodology and Computing in Applied Probability 19 (4) (2017) 1241–1250

    2017

  17. [25]

    Haukkanen, Formal power series in several variables, Notes on Number Theory and Discrete Math 25 (4) (2019) 44–57

    P. Haukkanen, Formal power series in several variables, Notes on Number Theory and Discrete Math 25 (4) (2019) 44–57

    2019

  18. [26]

    Sambale, An invitation to formal power series, Jahresbericht der Deutschen Mathematiker-Vereinigung 125 (1) (2023) 3–69

    B. Sambale, An invitation to formal power series, Jahresbericht der Deutschen Mathematiker-Vereinigung 125 (1) (2023) 3–69

    2023

  19. [27]

    N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd Edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002

    2002

  20. [28]

    Limnios, G

    N. Limnios, G. Oprisan, Semi-Markov Processes and Reliability, Springer, 2001. 25

    2001

  21. [29]

    B. Wu, B. I. G. Maya, N. Limnios, Using semi-markov chains to solve semi-markov processes, Methodology and Computing in Applied Probability 23 (4) (2021) 1419– 1431

    2021

  22. [30]

    Q. Liu, L. Xing, C. Zhou, Probabilistic modeling and analysis of sequential cyber- attacks, Engineering Reports 1 (4) (2019) e12065

    2019

  23. [31]

    J. W. Cooley, J. W. Tukey, An algorithm for the machine calculation of complex fourier series, Mathematics of computation 19 (90) (1965) 297–301

    1965

  24. [32]

    Van Loan, Computational frameworks for the fast Fourier transform, SIAM, 1992

    C. Van Loan, Computational frameworks for the fast Fourier transform, SIAM, 1992

    1992

  25. [33]

    Chakraborty, D

    S. Chakraborty, D. Chakravarty, Discrete gamma distributions: Properties and param- eter estimations, Communications in Statistics - Theory and Methods 41 (18) (2012) 3301–3324. Supplementary Material This supplementary material contains auxiliary proofs, algorithmic descripti...

    2012

  26. [34]

    Compute the discrete Fourier transforms of the zero-padded sequencesAandB

  27. [35]

    For eachm∈I L, compute bC(m) = bA(m)bB(m)

  28. [36]

    Compute the inverse FFT ofbCcomponentwise

  29. [37]

    , NA +N B −2

    Restrict the resulting sequence to the non-aliased range0, . . . , NA +N B −2. 31 M.2. Newton inversion For the convolution inverse of an invertible matrix-valued sequenceAtruncated at length M, proceed as follows

  30. [38]

    Compute the associated polynomial matrixPA(x)modulox M

  31. [40]

    Set PB =A(0) −1, n= 1

  32. [41]

    Whilen < M, replacenby2nand compute PB ←P B +P B(Is −P APB) modx n, using FFT-based polynomial products

  33. [42]

    ReturnP B modulox M. M.3. Gauss–Jordan elimination For the convolution inverse of an invertible matrix-valued sequenceAtruncated at order M, proceed as follows

  34. [43]

    Form the associated matrix polynomialPA(x)modulox M

  35. [44]

    IfA(0)is singular, the sequence is not convolu- tionally invertible

    Check whetherA(0)is nonsingular. IfA(0)is singular, the sequence is not convolu- tionally invertible

  36. [45]

    Perform Gauss–Jordan elimination onPA(x)overC[[x]]/⟨x M ⟩, using only pivots with nonzero constant coefficient

  37. [46]

    Its coefficients give the con- volutional inverse ofAup to orderM−1

    The resulting matrix polynomial isPA(x)−1 modulox M. Its coefficients give the con- volutional inverse ofAup to orderM−1. N. Error bound for the Stieltjes approximation In[17], thetruncationerrorboundforthescalarStieltjesapproximationisobtainedunder differentiability of the sm...

Pith tools

Reviewed July 1, 2026 · model on record in the stance chip above.