The EPS method: A new method for constructing pseudospectral derivative operators

We develop a new type of derivative matrix for pseudospectral methods. The norm of these matrices grows at the optimal rate O(N2) for N-by-N matrices, in contrast to standard pseudospectral constructions that result in O(N4) growth of the norm. The smaller norm has a big advantage when using the derivative matrix for solving time dependent problems such as wave propagation. The construction is based on representing the derivative operator as an integral kernel, and does not rely on the interpolating polynomials. In particular, we construct second derivative matrices that incorporate Dirichlet or Neumann boundary conditions on an interval and on the disk, but the method can be used to construct a wide variety of commonly used operators for solving PDEs and integral equations. The construction can be used with any quadrature, including traditional Gauss–Legendre quadratures, but we have found that by using quadratures based on prolate spheroidal wave functions, we can achieve a near optimal sampling rate close to two points per wavelength, even for non-periodic problems. We provide numerical results for the new construction and demonstrate that the construction achieves similar or better accuracy than traditional pseudospectral derivative matrices, while resulting in a norm that is orders of magnitude smaller than the standard construction. To demonstrate the advantage of the new construction, we apply the method for solving the wave equation in constant and discontinuous media and for solving PDEs on the unit disk. We also present two compression algorithms for applying the derivative matrices in O(N log N) operations.