Inexact Sparse Matrix-Vector Products in the Calculation of Passage Time Distributions in Large Semi-Markov Models

We have previously presented an iterative algorithm based on repeated sparse matrix-vector multiplication for the calculation of passage time distributions in large semi-Markov models. We showed that the required number of operations can be reduced without affecting the accuracy of the final result if we do not perform multiplications with vector elements that are small in magnitude. Our earlier evaluation was limited, however, to a small number of test cases and no general error bound was derived. This paper addresses our prior work's limitations. We present an error analysis of inexact matrix-vector products in our iterative algorithm that leads to a bound on the overall error compared with the exactly computed solution. We support this analysis with numerical results from a range of semi-Markov models that demonstrate that the bound is valid in practice and that reducing the number of multiplications leads to a reduction in run-time of over 50% in the best cas