Optimal Adaptive Ridgelet Schemes for Linear Transport Equations

Philipp Grohs, Axel Obermeier

Abstract

In this paper, we present a novel method for the numerical solution of linear transport equations based on ridgelets. These equations are fundamental in fields such as radiative transfer and phase contrast imaging. Because ridgelet systems are naturally adapted to the structure of linear transport operators, our proposed scheme operates with optimal complexity, even in the presence of line singularities. We demonstrate that the system matrix, when combined with diagonal preconditioning, is uniformly well-conditioned and compressible. The proof of compressibility constitutes the core theoretical contribution of this work. We conclude with numerical experiments validating N-term approximations and the localization of singularities within the ridgelet frame.

Introduction

Linear transport equations, such as the Radiative Transport Equation (RTE), pose significant challenges for traditional numerical solvers. These equations often describe high-dimensional phenomena where solutions exhibit line singularities—sharp discontinuities or edges that propagate along the direction of transport.

Standard numerical techniques often fall short in these scenarios. Wavelets, while excellent for point singularities, are inefficient at capturing linear features. Finite Element Methods (FEM) typically suffer from slow convergence rates, often limited to $N^{-1/2}$ when singularities are present. Furthermore, the resulting algebraic systems are frequently ill-conditioned, leading to slow or unstable iterative solutions. This paper introduces an "optimal" solver where computational effort scales linearly with the number of parameters required to represent the solution to a target accuracy.

Ridgelet Frames and Methodology

The cornerstone of our approach is the use of Ridgelet Frames. Unlike standard wavelets, which are isotropic "blobs," a ridgelet is an anisotropic "needle." It oscillates rapidly in one direction while remaining smooth along a line, known as the "ridge."

Physical and Fourier space representations of a ridgelet showing its directional sensitivity and localized frequency support.

Mathematical Framework

To discretize the transport operator, we utilize Gelfand Frames. This framework allows us to transform the continuous operator equation into a bi-infinite matrix system while ensuring numerical stability. The solver employs an Adaptive Richardson Iteration (specifically the SOLVE and modSOLVE routines), which performs matrix-vector multiplications approximately. This adaptivity ensures that computational resources are focused only on the most significant coefficients of the solution.

Conditioning and Preconditioning

A critical finding of our research is that the system matrix is uniformly well-conditioned across all transport directions when paired with simple diagonal preconditioning. This uniformity is essential for applications like the RTE, where the transport direction varies continuously across the angular domain.

The Core Challenge: Compressibility

The primary theoretical hurdle addressed in this paper is proving the compressibility of the system matrix. A matrix is compressible if its entries decay rapidly away from the diagonal, allowing it to be approximated by a sparse matrix without significant loss of accuracy.

We show that ridgelets don't just provide a sparse representation of the solution; they also "sparsify" the transport operator itself. Because the transport occurs along lines and ridgelets are oriented along lines, the operator's action in the ridgelet domain is highly localized. This property is what ultimately enables the scheme to achieve optimal computational complexity.

Numerical Experiments and Results

We evaluated the ridgelet-based solver using synthetic benchmarks designed to highlight its strengths:

  1. Smooth Gaussian: Established a baseline for convergence on well-behaved functions.
  2. Box Function with Gaussian Envelope: A rigorous test involving a sharp jump (singularity) not aligned with any underlying grid.

Key Findings

  • Exponential Convergence: For piecewise smooth solutions with line singularities, the method achieved near-exponential convergence rates, a dramatic improvement over the algebraic rates of conventional FEM.
  • Optimal Complexity: The number of operations required to reach a specific error tolerance $\epsilon$ scales as $O(\epsilon^{-1/s})$, where $s$ is the sparsity of the solution.
  • Kernel Handling: We identified that a bounded projection ($P$) is necessary to remove error components in the operator's null space, a theoretical requirement that proved vital for practical stability.

Conclusion and Future Directions

This work provides a robust theoretical and practical foundation for solving linear transport equations using ridgelets. While currently implemented as a 2D proof-of-concept, the results demonstrate a path toward overcoming the limitations of traditional solvers in high-dimensional transport problems.

Future research will focus on scaling the ridgelet construction to the full 5D space of the RTE (3D space + 2D angle) and incorporating physical boundary conditions. Additionally, we are developing faster implementations utilizing Fast Fourier Transforms (FFT) to reduce the computational cost of the initial system setup.

Summary updated

Abstract

In this paper we present a novel method for the numerical solution of linear transport equations, which is based on ridgelets. Such equations arise for instance in radiative transfer or in phase contrast imaging. Due to the fact that ridgelet systems are well adapted to the structure of linear transport operators, it can be shown that our scheme operates in optimal complexity, even if line singularities are present in the solution. The key to this is showing that the system matrix (with diagonal preconditioning) is uniformly well-conditioned and compressible -- the proof for the latter represents the main part of the paper. We conclude with some numerical experiments about $N$-term approximations and how they are recovered by the solver, as well as localisation of singularities in the ridgelet frame.
BibTeX
@misc{grohs2014optimal,
  author = {Philipp Grohs and Axel Obermeier},
  title = {{Optimal Adaptive Ridgelet Schemes for Linear Transport Equations}},
  year = {2014},
  eprint = {1409.1881},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1409.1881},
}

Loading related content...

Figure