When solving partial differential equations (PDEs) numerically, scientists have traditionally been forced to make a frustrating trade-off between two competing paradigms:
- Local methods (such as finite differences or finite elements) discretize space into a localized grid or mesh. Because each point only interacts with its immediate neighbors, the resulting mathematical matrices are highly sparse and banded. These systems can be solved very quickly—often in linear time ($O(N)$)—but achieving high accuracy requires a dense grid, which drives up memory costs.
- Global spectral methods (such as Chebyshev or Fourier methods) approximate the solution using smooth, global basis functions. Because these functions span the entire domain, they achieve incredible accuracy ("spectral accuracy") with very few points. However, differentiating these global functions couples every coefficient to every other coefficient. This turns the differential operators into dense matrices, requiring expensive $O(N^3)$ operations to solve.
The research direction of sparse spectral discretization eliminates this trade-off. By cleverly changing the underlying polynomial or wavelet bases, or by applying localized transformations, researchers have found ways to represent global, continuous operators as sparse, banded matrices. This achieves the best of both worlds: the exponential precision of global spectral methods operating at the linear-time speed of local methods.
The Ultraspherical Solution: Sparsity through Basis-Switching
To understand why traditional spectral methods produce dense matrices, consider representing a function $u(x)$ as a sum of Chebyshev polynomials, $T_n(x)$. When we take the derivative $u'(x)$, the derivative of each Chebyshev polynomial cannot be expressed as a single Chebyshev polynomial; instead, it expands into a dense combination of all lower-degree polynomials of the same parity. Consequently, the differentiation matrix becomes a dense upper-triangular mess.
The breakthrough introduced in A fast and well-conditioned spectral method by Townsend et al. relies on a simple but powerful realization: the derivative of a Chebyshev polynomial is exactly equal to a single ultraspherical (or Gegenbauer) polynomial. Specifically, $\frac{d}{dx}T_n(x) = n C_{n-1}^{(1)}(x)$.
If we allow the basis to change when we apply a differential operator, the differentiation matrix transforms from a dense matrix into a perfectly sparse, diagonal matrix.
Standard Chebyshev Method:
[Chebyshev Basis] ---> (Differentiate) ---> [Dense Matrix] ---> [Chebyshev Basis]
Ultraspherical Method:
[Chebyshev Basis] ---> (Differentiate) ---> [Diagonal Matrix] ---> [Ultraspherical Basis (C¹)]
Of course, a differential equation often contains multiple terms, such as $u''(x) + g(x)u'(x) + u(x) = f(x)$. If every derivative shifts the function into a different ultraspherical basis ($C^{(1)}, C^{(2)}$, etc.), how do we add them together?
As the authors demonstrate in The automatic solution of partial differential equations using a global spectral method, the solution lies in banded conversion operators. Moving a function from the $C^{(\lambda)}$ basis to the $C^{(\lambda+1)}$ basis can be accomplished via a tridiagonal matrix. By composing these sparse differentiation and conversion matrices, the entire differential equation is mapped to a shared ultraspherical space.
The final linear system is "almost banded"—it is perfectly banded except for a few dense rows at the top that enforce boundary conditions. As a result, complex linear ordinary differential equations can be solved with machine precision in $O(N)$ time.
Scaling to Complex Geometries and Higher Orders
While the one-dimensional case provides clear intuition, physical problems often occur in multi-dimensional or non-rectangular domains. The sparse spectral framework scales elegantly to these scenarios by treating algebraic and differential operations as discrete, composable linear operators.
In A Sparse Spectral Method on Triangles, Townsend et al. extended this logic to triangular domains by shifting between families of bivariate orthogonal polynomials. By treating coordinate multiplications and partial derivatives as sparse operator-valued logic, they maintained matrix sparsity even when constructing high-order partial differential equations, such as fourth-order biharmonic equations.
For highly complex, unstructured meshes, The ultraspherical spectral element method by Fortunato et al. combines the ultraspherical basis with a spectral element framework. Normally, mapping an element from a physical curved domain to a reference rectangular domain introduces variable coefficients that destroy sparsity. The authors bypassed this by scaling the transformed PDEs by the determinant of the Jacobian, ensuring that variable coefficients remain polynomial. This preserved the banded structure of the operators and reduced the computational complexity of the element build stage from $O(p^6)$ to $O(p^4)$ for a polynomial order $p$.
This sparsity is also highly effective for eigenvalue problems. As shown by Townsend et al. in FEAST for Differential Eigenvalue Problems, using an ultraspherical spectral discretization converts continuous differential eigenvalue problems into sparse, well-conditioned linear systems, making it highly efficient to resolve rapidly oscillating, high-frequency wave modes.
Compressing Integral Operators with Wavelets
Differential equations represent local physics, but many physical phenomena—such as quantum transport, non-local diffusion, or fluid boundaries—are governed by integral equations. Integral operators have global reach, meaning their discretized matrices are fundamentally dense. To sparsify these systems, researchers look to the multi-resolution properties of wavelets.
In Controlled Differential Equations on Long Sequences via Non-standard Wavelets, Pal et al. tackle the problem of processing long sequences in time-series models. They recast the underlying differential equations as integral transforms and apply a neural variant of the Beylkin-Coifman-Rokhlin (BCR) wavelet algorithm.
The intuition behind using wavelets for operator compression relies on the property of vanishing moments. Because wavelets oscillate rapidly, their integral against a smooth, slowly varying function is zero. In a dense integral kernel, the interactions between distant points are often highly smooth. When transformed into a wavelet basis, these distant interactions cancel out, mapping the dense matrix into a highly compressed, diagonally banded structure:
$$\int K(x, y) u(y) dy \quad \xrightarrow{\text{Wavelet Transform}} \quad \begin{pmatrix} \mathbf{B} & 0 & 0 \\ 0 & \mathbf{B} & 0 \\ 0 & 0 & \mathbf{B} \end{pmatrix}$$
Similarly, Multiwavelet-based Operator Learning for Differential Equations by Gupta et al. leverages multiwavelets to compress integral kernels within neural operators. By combining orthogonal polynomials (to capture smooth, global trends) with localized wavelets (to isolate sharp singularities), the authors achieve extreme sparsity. This allows neural networks to learn complex operator maps with a fraction of the parameters required by dense architectures.
Sparsifying Preconditioners for Dense Pseudospectral Methods
There are times when a dense discretization cannot be avoided—for instance, when using Fourier pseudospectral methods to simulate periodic wave phenomena like solitons. Even in these inherently dense environments, sparse operator logic can be used to accelerate computation.
In Sparsifying preconditioner for soliton calculations, Lu et al. introduced a method to numerically transform a dense global operator into a sparse local operator to serve as a preconditioner. Because global wave interactions are governed by underlying local physics, the authors applied a localization matrix that isolates the near-field interactions.
This sparse approximation captures the essential spectral information of the dense system's inverse. When paired with iterative Krylov-subspace solvers, this sparsifying transformation allows memory-efficient, sparse direct linear solvers to accelerate the computation of complex wave equations, bypassing the $O(N^3)$ bottleneck entirely.
Key Foundational Work
Wavelet-Like Bases for the Fast Solution of Second-Kind Integral Equations (1993) — contributed 4 concept elements to this direction.