A Fast Spectral Solver for the Heat Equation, with Applications to Navier-Stokes

We develop a spectral method to solve the heat equation in a closed cylinder, achieving a near-optimal $\mathcal{O}(N\log N)$ complexity and high-order, spectral accuracy. The algorithm relies on a novel Chebyshev-Chebyshev-Fourier (CCF) discretization of the cylinder, which is easily implemented and decouples the heat equation into a collection of smaller, sparse Sylvester equations. In turn, each of these equations is solved using the alternating direction implicit (ADI) method, which improves the complexity of each solve from cubic in the matrix size (in more traditional methods) to log-linear; overall, this represents an improvement in the heat equation solver from $\mathcal{O}(N^{7/3})$ (in traditional methods) to $\mathcal{O}(N\log N)$. Lastly, we provide numerical simulations demonstrating significant speed-ups over traditional spectral collocation methods and finite difference methods, and we provide a framework by which this heat equation solver could be applied to the incompressible Navier--Stokes equations. For the latter, we decompose the equations using a poloidal-toroidal (PT) decomposition, turning them into heat equations with nonlinear forcing from the advection term; by using implicit-explicit methods to integrate these, we can achieve the same $\mathcal{O}(N\log N)$ complexity and spectral accuracy achieved here in the heat equation.