Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 341 / 3 / c / Solution

Split the generator as $iA-iV$. One Strang splitting step isThe two potential half-steps are componentwise multiplications. The circulant matrix $A$ is diagonalized by the discrete Fourier transform; its eigenvalues areThus the middle step consists of a Fast Fourier transform, multiplication of Fourier coefficient $j$ by $e^{ih{\lambda }_j}$, and an inverse transform. Its cost is $O(M\log M)$ and every factor is unitary, so the implementation preserves the discrete norm exactly up to roundoff.