Fast Computation of Orthogonal Systems with a Skew-symmetric Differentiation Matrix

Orthogonal systems in L2(R), once implemented in spectral methods, enjoy a number of important advantages if their differentiation matrix is skew-symmetric and highly structured. Such systems, where the differentiation matrix is skew-symmetric, tridiagonal and irreducible, have been recently fully characterised. In this paper we go a step further, imposing the extra requirement of fast computation: specifically, that the first N coefficients of the expansion can be computed to high accuracy in O(Nlog2N) operations. We consider two settings, one approximating a function f directly in (−∞,∞) and the other approximating [f(x)+ f(−x)]/2 and [f(x)− f(−x)]/2 separately in [0,∞). In each setting we prove that there is a single family, parametrised by α,β > −1, of orthogonal systems with a skew-symmetric, tridiagonal, irreducible differentiation matrix and whose coefficients can be computed as Jacobi polynomial coefficients of a modified function. The four special cases where α,β =±1/2 are of particular interest, since coefficients can be computed using fast sine and cosine transforms. Banded, Toeplitz-plus-Hankel multiplication operators are also possible for representing variable coefficients in a spectral method. In Fourier space these orthogonal systems are related to an apparently new generalisation of the Carlitz polynomials.