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

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.