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 matrix-free direct spectral solutions, which use only a small (nearly bounded) number of matrix-vector products to construct a structured approxi- mation 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 solution has nearly O(N) complexity and O(N) memory. Numerical tests for several important but notoriously difficult problems show the superior efficiency and accuracy of the direct solutions, especially when iterative methods have severe difficulties in the convergence.
This is a joint work with Jianlin Xia and Yingwei Wang.