Complexity Blowup in Simulating Analog Linear Time-Invariant Systems on Digital Computers

Abstract

This paper proves that every non-trivial, linear time-invariant (LTI) system of the first order shows a complexity blowup if it is simulated on a digital computer. This means that there exists a low-complexity input signal, which can be generated on a Turing machine in polynomial time, but such that the output signal of the LTI system has high complexity in the sense that the computation time for determining an approximation up to n significant digits grows faster than any polynomial in n. Moreover, this input signal can easily and explicitly be generated from the given system parameters by a Turing machine. It is also shown that standard techniques for simulating higher-order LTI systems with real poles show the same complexity blowup. Finally, it is shown that a similar complexity blowup occurs for the calculation of Fourier series approximations and Fourier transforms.