Source-linked AI summary
Sparse Dynamics for Partial Differential Equations
Hayden Schaeffer, Stanley Osher, Russel Caflisch, Cory Hauck
TL;DR
Multiscale PDE simulation must account for fine scales that influence global dynamics, but representing all evolving information can be costly. The paper evolves PDEs while repeatedly restricting their basis coefficients through soft thresholding, and reports successful sparse dynamics across several PDE classes. The method fully resolves solutions while retaining important modes, with larger usable time steps observed in the vorticity example.
Problem
Multiscale PDEs contain interacting spatial scales, and fine scales can influence global solutions, making accurate simulation require their resolution.
Method
The method evolves a PDE and applies soft thresholding to project each updated basis representation onto a sparse subspace.
Results
The method successfully reduces dynamics for convection, diffusion, weak-shock, and vorticity equations, while retaining important modes and capturing the solution's true phenomena.
Takeaways & Limitations
Sparse projection can fully resolve multiscale PDE solutions while reducing the information retained at each time step.
Takeaways & Limitations
The threshold must remain small enough not to annihilate essential features, and the method assumes periodicity when using the Fourier basis.
Abstract
from arXiv · showhide
We investigate the approximate dynamics of several differential equations when the solutions are restricted to a sparse subset of a given basis. The restriction is enforced at every time step by simply applying soft thresholding to the coefficients of the basis approximation. By reducing or compressing the information needed to represent the solution at every step, only the essential dynamics are represented. In many cases, there are natural bases derived from the differential equations which promote sparsity. We find that our method successfully reduces the dynamics of convection equations, diffusion equations, weak shocks, and vorticity equations with high frequency source terms.
1 Introduction
Multiscale PDEs are difficult because fine spatial scales can influence global solutions, while standard basis representations may require substantial information. The paper transfers sparsity methods to compute such dynamics while retaining only important basis information.
- Multiscale PDE solutions can contain interacting behaviors across multiple spatial scales and high-frequency oscillations over smooth underlying behavior.
- Accurate simulation generally requires resolving all relevant scales because smaller scales influence global solutions.
- Basis coefficients encode scale-specific behavior, so basis approximations provide a representation of the underlying function across scales.
- Sparse representations can resolve drastically different phenomena using a small amount of information, motivating their transfer to multiscale differential equations.
- The proposed approach constrains approximate PDE solutions to a sparse basis subspace and is tested across oscillatory advection, diffusion, conservation-law, and vorticity problems.
2 Sparsity
The method evolves a PDE and repeatedly projects its basis representation onto a sparse subset. Soft thresholding provides a practical L1-based way to induce sparsity in the coefficients.
- The approximate solution is represented in basis functions whose terms correspond to separate scales and global behaviors.
- Each time step first evolves the PDE and then projects the updated solution onto a sparse subset of basis coefficients.
- The sparse projection can be formulated as constrained least-squares fitting of the updated solution to coefficients with few nonzero entries.
- 2.2 Sparsity via Optimization: Soft Thresholding: Replacing the non-convex L0 objective with the L1 norm yields a convex relaxation for inducing coefficient sparsity.
- 2.2 Sparsity via Optimization: Soft Thresholding: For non-orthonormal bases, the L1-regularized problem requires an iterative solution rather than the simple shrinkage formula.
3 Numerical Method
For periodic problems, the numerical method uses Fourier coefficients, evolves them with a time-discrete PDE update, and applies adaptive nonlinear shrinkage before reconstructing the solution. Convergence is retained when the threshold parameter decreases sufficiently with the time step.
- Under periodic boundary conditions, the method uses the Fourier basis, although the overall sparsity methodology is basis-independent.
- A time-discrete PDE update produces an auxiliary coefficient vector that may be non-sparse before projection.
- The shrinkage operator projects the auxiliary variable onto a sparse subspace, after which the spatial-domain solution is updated.
- The nonlinear adaptive projection lets the number and identities of nonzero coefficients evolve, selecting by amplitude rather than wavenumber.
- When λ = Cdt^p with p larger than the time-update accuracy order, shrinkage does not change spatial accuracy and convergence remains possible as dt → 0.
- The shrinkage operator is non-expansive in coefficient norms, which may support a general convergence result.
4 Numerical Results
The sparse dynamics method is tested on convection, parabolic diffusion, viscous Burgers, and vorticity equations with oscillatory coefficients or forcing. Across these examples, sparse solutions retain important coefficients across scales, approximate fully resolved solutions, and converge as spatial resolution increases.
- 4.1 Convection: The convection experiment compares sparse, fully resolved, and low-frequency solutions for an equation with highly oscillatory velocity.The coefficient contains fast and slow modes, and the sparse method is evaluated in both physical and spectral space.
- 4.1 Convection: 27 of 512 coefficients are retained in the convection sparse solution, or about 5.3%, while capturing the largest-amplitude coefficients throughout the spectrum.The sparse solution is compared with the true solution at t = 1; the low-frequency solution contains parasitic Leap Frog modes.
- 4.2 Parabolic: The parabolic diffusion sparse and true solutions are nearly indistinguishable, while the sparse spectrum retains high-frequency information rather than only low wavenumbers.The method retains 53 of 2048 coefficients, about 2.6%, and the active coefficients change over time to capture different behaviors.
- 4.3 Viscous Burgers: The viscous Burgers sparse solution captures local and global behavior more accurately than a low-frequency projection with the same number of retained coefficients.Its spectrum includes peaks associated with the oscillatory diffusion coefficient and nonlinear advection harmonics, retaining 130 of 1024 coefficients, about 12.7%.
- 4.4 Vorticity Equations: The vorticity experiment combines diffusion, high-frequency source oscillations, and nonlinear advection interactions, while retaining about 3.95% of the coefficients.The sparse spectrum contains coefficients throughout the domain, including the highest frequency, and the L2 and L∞ errors decrease as resolution increases.
- 4 Numerical Results: As dimension increases, solution sparsity increases proportionally to the product of sparsities in each dimension, so the method scales well with dimension.The reported convergence also holds for the sparse solutions as spatial discretization goes to zero.
5 Discussion
The method’s effectiveness depends on choosing a basis and threshold that preserve essential multiscale dynamics while discarding insignificant modes. Soft thresholding can improve stability and suppress artifacts, but extreme sparsity may reduce accuracy.
- Basis selection: The highest-order derivative generally determines the basis in which solutions can become sparse.For the preceding examples, nonlinear and oscillatory terms generate broad wavenumber and amplitude ranges that support Fourier sparsity.
- Filtering and stability: Soft thresholding acts as a nonlinear coefficient filter and can permit time steps larger than those allowed by the original scheme.In the vorticity example, substantially larger time steps were possible after applying soft thresholding.
- Filtering and stability: The nonlinear filter appears to reduce parasitic modes and spurious oscillations in spectral approximations.This behavior is reported for linear and slightly viscous nonlinear hyperbolic equations, including the Burgers example.
- Accuracy and sparsity: The method must use a sufficiently small λ to avoid annihilating essential features of unstable modes.A mode whose initial amplitude is below λ may be missed, while refinement lowers λ as Δx decreases and allows the mode to be captured.
- Computational cost: Spectral-domain convolution reduces computational cost when ns(t)^2 << NlogN.Knowing the maximum sparsity can also support routines and transforms optimized for the problem’s retained coefficients.
- Scaling and extensions: As dimension increases, solution sparsity increases proportionally to the product of sparsities across dimensions, so the method scales well with dimension.The discussion also reports that coefficient identities settle over time in high-viscosity dynamics, potentially enabling sparse bases for elliptic equations.
- Accuracy and sparsity: Hypersparse solutions with 1% or fewer coefficients are attainable in many cases, but at a cost in accuracy.Thus the strongest compression is not necessarily the most accurate representation.
6 Conclusion
The proposed sparse projection retains important modes while capturing the solution’s true multiscale phenomena. Sparsity also supports faster, more efficient computational routines.
- The sparse projection fully resolves multiscale PDE solutions while retaining only important modes.It applies shrinkage to updated coefficients at every time step.
- The reduced dynamics properly capture the true phenomena exhibited by the solution.
- Sparsity enables faster, more efficient computational routines.