We study the rank structures of the matrices in Fourier- and Chebyshev-spectral methods for differential equations with variable coefficients in one dimension. We show analytically that these matrices have a so-called low-rank property, not only for constant or smooth variable coefficients, but also for coefficients with steep gradients and/or high variations (large ratios in their maximum-minimum function values). We develop a matrix-free direct spectral solver, which uses only a small number of matrix-vector products to construct a structured approximation to the original discretized matrix $A$, without the need to explicitly form $A$. This is followed by fast structured matrix factorizations and solutions. The overall direct spectral solver has $O(N\log^{2}N)$ complexity and $O(N)$ memory requirement. Numerical tests for several important but notoriously difficult problems show the superior efficiency and accuracy of our direct spectral solver, especially when iterative methods have severe difficulties...
['Jie Shen', 'Yingwei Wang', 'Jianlin Xia']
Fast Structured Direct Spectral Methods for Differential Equations with Variable Coefficients, I. The One-Dimensional Case