High-Order Numerical Method for 1D Non-local Diffusive Equation

D. Do, Hossein Nick Zinat Matin, Maria Laura Delle MonachearXiv 2023 · DOI · OpenReview

Abstract

Modeling traffic flow requires balancing physical realism with computational feasibility. Traditional local models often fail to capture driver anticipation and the smoothing effects of speed adjustments. This paper presents a high-order Local Discontinuous Galerkin (LDG) scheme for a 1D non-local diffusive traffic flow model. By utilizing a perceived density framework, the method ensures physical consistency—specifically avoiding negative velocities—while leveraging high-order approximations to overcome the $O(n^2)$ computational complexity inherent in non-local simulations.

Introduction

Traffic flow modeling has historically relied on the Lighthill-Whitham-Richards (LWR) model, a first-order conservation law that assumes a driver's speed is determined solely by the local density at their exact position. However, real-world driving involves anticipation—drivers look ahead to adjust their speed—and diffusion, as speed changes are not instantaneous.

While incorporating non-local and diffusive terms improves model fidelity, it introduces significant numerical challenges. Standard diffusive models frequently produce non-physical artifacts, such as negative velocities. Furthermore, calculating non-local interactions requires evaluating convolution integrals, which scales quadratically ($O(n^2)$) with the number of grid points. This study addresses these issues by proposing a robust, high-order numerical framework designed for both accuracy and efficiency.

The Non-local Diffusive Model

The core of the proposed approach is a model where velocity is a function of "perceived density" ($\hat{\rho}$). Unlike standard density, perceived density accounts for the average density within a specific look-ahead window and the gradient of that density.

A critical theoretical contribution of this work is the proof (Theorem 2.1) that this perceived density $\hat{\rho}$ remains strictly within the bounds of $[0, 1]$. This mathematical guarantee ensures that the model never predicts negative velocities, a common failure point in previous diffusive traffic models that lacked such constraints.

Numerical Methodology: Local Discontinuous Galerkin (LDG)

To solve the governing equations, the authors employ a Local Discontinuous Galerkin (LDG) method. The LDG approach is particularly suited for this problem due to its flexibility in handling high-order approximations and its ability to manage the diffusive (second-order) terms by splitting them into a system of first-order equations.

Key Technical Components:

  • High-Order Basis Functions: The solution within each grid cell is represented using Legendre polynomials defined on Chebyshev nodes. This allows for high-order spatial accuracy.
  • Non-local Integration: The convolution terms, which represent the driver's look-ahead behavior, are computed using piecewise integrals across multiple intervals. This ensures the integration remains accurate even when the look-ahead window spans several grid cells.
  • Temporal Discretization and Stability: The system is evolved in time using a 3rd-order Runge-Kutta method. To prevent artificial oscillations near sharp traffic shocks (such as the sudden onset of a traffic jam), a Generalized Slope Limiter (GSL) is applied.

Results and Performance

The method was evaluated using standard synthetic benchmarks, including rarefaction waves, forward/backward shockwaves, and smooth sine waves for convergence testing.

Accuracy and Convergence

The numerical experiments confirmed the theoretical convergence rates. For instance, using $p=3$ polynomials (fourth-order accuracy) resulted in a convergence rate of approximately 4.1. This implies that doubling the grid resolution reduces the error by a factor of 16, demonstrating the high precision of the LDG scheme.

Overcoming the $O(n^2)$ Bottleneck

The most significant finding regarding performance is the efficiency of high-order methods in the context of non-local interactions. Because non-local terms require $O(n^2)$ operations, the computational cost grows rapidly as the grid is refined. However, the authors demonstrate that a high-order simulation (e.g., $p=3$) requires significantly fewer grid points to achieve a target accuracy than a low-order simulation ($p=1$).

In practice, the high-order method was both faster and more accurate than its low-order counterparts. This is vital because, as the number of grid partitions ($n$) increases, the non-local convolution begins to dominate the CPU time—accounting for over 80% of the total computation at $n=320$.

Conclusion

This research provides a robust framework for simulating non-local diffusive traffic flow. By combining a physically consistent perceived density model with a high-order LDG scheme, the authors successfully mitigate the computational burden of non-local convolutions while maintaining high accuracy and physical reliability.

Future work will need to address the scalability of these methods to 2D environments, where the complexity could reach $O(n^4)$. Potential avenues for optimization include the use of GPU acceleration or Fast Multipole Methods (FMM) to further reduce the burden of the convolution calculations.

Summary updated

Abstract

In this paper we present a non-local numerical scheme based on the Local Discontinuous Galerkin method for a non-local diffusive partial differential equation with application to traffic flow. In this model, the velocity is determined by both the average of the traffic density as well as the changes in the traffic density at a neighborhood of each point. We discuss nonphysical behaviors that can arise when including diffusion, and our measures to prevent them in our model. The numerical results suggest that this is an accurate method for solving this type of equation and that the model can capture desired traffic flow behavior. We show that computation of the non-local convolution results in $\mathcal{O}(n^2)$ complexity, but the increased computation time can be mitigated with high-order schemes like the one proposed.
BibTeX
@misc{do2023high,
  author = {D. Do and Hossein Nick Zinat Matin and Maria Laura Delle Monache},
  title = {{High-Order Numerical Method for 1D Non-local Diffusive Equation}},
  year = {2023},
  eprint = {2311.04306},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.04306},
}
Figure