Bandwidth truncation for Chebyshev polynomial and ultraspherical/Chebyshev Galerkin discretizations of differential equations: Restrictions and two improvements

The Petrov–Galerkin ultraspherical polynomial/Chebyshev polynomial discretization of the highest derivative of a differential equation is a diagonal   matrix. The same is true for Fourier–Galerkin discretizations. Nevertheless, the spectral discretizations of simple problems like uxx+q(x)u=f(x)uxx+q(x)u=f(x) are usually dense matrices. The villain is the “multiplication matrix”, the Galerkin representation of a term like q(x)u(x)q(x)u(x); unfortunately, this part of the Galerkin matrix is dense. However, if the ODE coefficient q(x)q(x) has a Chebyshev or Fourier series that converges much more rapidly than u(x)u(x), then it is possible to realize great cost savings at no loss of accuracy by truncating the full N×NN×N Galerkin matrix to a banded matrix where the bandwidth m≪Nm≪N. One of our themes is that when the spectral series for q(x)q(x) and u(x)u(x) have similar rates of convergence, as is almost universal when a nonlinear equation is linearized for a Newton–Krylov iteration, such “[accuracy] lossless” truncation is impossible. Nonlinearity is but one of many causes of this sort of solution/coefficient “equiconvergence”. When bandwidth truncation is possible, though, our second theme is to show that a modest amount of floating point operations and memory can be saved by an unsymmetric truncation in which the number of elements retained to the left of the main diagonal is roughly double the number kept to the right. Our second improvement is to replace the MM-term spectral series for q(x)q(x) by its [(M/2)/(M/2)][(M/2)/(M/2)] Chebyshev–Padé rational approximation. This sometimes allow one to halve the matrix bandwidth, reducing the linear algebra costs by a factor of four.