Fast Fourier solvers for the tensor product high-order fem for a Poisson type equation

Logarithmically optimal in theory and fast in practice, direct algorithms for implementing a tensor product finite element method (FEM) based on tensor products of 1D high-order FEM spaces on multi-dimensional rectangular parallelepipeds are proposed for solving the $N$-dimensional Poisson-type equation $-\Delta u+\alpha u=f$ ($N \geqslant 2$) with Dirichlet boundary conditions. The algorithms are based on well-known Fourier approaches. The key new points are a detailed description of the eigenpairs of the 1D eigenvalue problems for the high-order FEM, as well as fast direct and inverse eigenvector expansion algorithms that simultaneously employ several versions of the fast Fourier transform. Results of numerical experiments in the 2D and 3D cases are presented. The algorithms can be used in numerous applications, in particular, to implement tensor product high-order finite element methods for various time-dependent partial differential equations, including the multidimensional heat, wave, and Schrödinger ones.