Fast convolution algorithm for state space models

We present an unconditionally stable algorithm for applying matrix transfer function of a linear time invariant system (LTI) in time domain. The state matrix of an LTI system used for modeling long range dependencies in state space models (SSMs) has eigenvalues close to 1. The standard recursion defining LTI system becomes unstable if the m× m state matrix has just one eigenvalue with absolute value even slightly greater than 1. This may occur when approximating a state matrix by a structured matrix to reduce the cost of matrix-vector multiplication from Oleft(m2right) to Oleft(mright) or Oleft(mlog mright). We introduce an unconditionally stable algorithm that uses an approximation of the rational transfer function in the z-domain by a matrix polynomial of degree 2N+1-1, where N is chosen to achieve any user-selected accuracy. Using a cascade implementation in time domain, applying such transfer function to compute L states requires no more than 2L matrix-vector multiplications (whereas the standard recursion requires L matrix-vector multiplications). However, using unconditionally stable algorithm, it is not necessary to assure that an approximate state matrix has all eigenvalues with absolute values strictly less than 1 i.e., within the desired accuracy, the absolute value of some eigenvalues may possibly exceed 1. Consequently, this algorithm allows one to use a wider variety of structured approximations to reduce the cost of matrix-vector multiplication and we briefly describe several of them to be used for this purpose.