Complexity of preprocessing of recursive filters for running in parallel

AbstractTwo recipes for preparing a linear recurrence for execution on p processors are proposed, requiring O(log p) multiplications of recurrence coefficients to obtain the transformed equation and O(p) multiplications to compute extra terms of the sequence. For recursive filters, these counts are both O(p). The lower estimates are based upon Strassen's degree bound and linear independence of polynomials. A brief discussion of speedups and stability is included