🔢 mathematics

High-order WENO-based semi-implicit Newton-type fast sweeping methods for static Hamilton-Jacobi equations

This paper proposes high-order WENO-based semi-implicit Newton-type Gauss-Seidel fast sweeping methods that achieve fifth-, seventh-, and ninth-order accuracy for solving generalized Eikonal equations in moving fluids, demonstrating their efficiency and precision through numerical examples in two and three dimensions.

Original authors: Yuan Liu, Jianliang Qian

Published 2026-08-04

📖 3 min read🧠 Deep dive

CC0 1.0

Original authors: Yuan Liu, Jianliang Qian

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to map out the fastest route for a sound wave to travel from a single point to every other corner of a room. But here's the twist: the air in the room isn't still. It's a moving fluid, like a river of wind blowing through the space, which pushes the sound waves faster in some directions and slower in others. This is a classic puzzle in physics known as the "Eikonal equation." It's the mathematical rulebook for figuring out "travel time"—how long it takes for a wavefront to reach a specific spot. Scientists need to solve this to understand everything from how earthquakes shake the ground to how sonar works underwater.

The tricky part is that the math behind these moving fluids is incredibly messy and non-linear. It's like trying to predict the path of a leaf floating down a turbulent river; you can't just draw a straight line. For decades, computers have solved this by checking one tiny point at a time, updating the map step-by-step. It works, but it's slow, like trying to paint a massive mural by filling in one pixel at a time with a tiny brush. Another method, called "Fast Sweeping," speeds things up by checking whole lines of points at once, but until now, the most accurate versions of this method were stuck with a trade-off: they were either fast but a bit blurry, or sharp but incredibly slow to compute.

This paper introduces a clever new way to paint that mural. The authors, Yuan Liu and Jianliang Qian, have built a "high-order" version of the Fast Sweeping method that is both lightning-fast and incredibly precise. They took an existing technique that updates entire lines of data simultaneously (like filling a whole row of pixels in one go) and supercharged it with a sophisticated mathematical tool called WENO (Weighted Essentially Non-Oscillatory). Think of WENO as a super-smart artist who knows exactly how to blend colors to avoid jagged, ugly edges when drawing a curve. By combining this "smart blending" with a line-by-line update strategy, they created a solver that can calculate travel times with fifth-, seventh-, and even ninth-order accuracy.

In their simulations, the authors tested this new method on various scenarios, including 2D maps and complex 3D environments with moving fluids. They found that their approach doesn't just work; it converges to the correct answer with the high precision they promised. Whether they swept the grid column-by-column, row-by-row, or a mix of both, the method consistently achieved the desired accuracy levels. The paper suggests that this new framework is a significant step forward, offering a way to get highly detailed, accurate maps of wave travel times without the computational headache that usually comes with high precision. It's a tool that could help researchers model complex wave behaviors in moving fluids more efficiently than ever before.

Technical Summary: High-order WENO-based Semi-implicit Newton-type Fast Sweeping Methods for Static Hamilton-Jacobi Equations

Problem Statement
This paper addresses the numerical solution of static Hamilton-Jacobi (HJ) equations, specifically the generalized Eikonal equation arising in wave propagation through a moving fluid. The governing equation is given by $H(x, \nabla T(x)) = f(x)$ , where the Hamiltonian is defined as $H(x, \nabla T(x)) = \|\nabla T(x)\| - |1 - v(x) \cdot \nabla T(x)| / F(x)$ . Here, $T(x)$ represents the travel time, $v(x)$ is the background fluid velocity, and $F(x)$ is the wave speed. The authors note that while classical Lagrangian ray-tracing methods are efficient in smooth media, they often fail to provide globally resolved, uniformly accurate fields on regular grids due to shadow zones. Conversely, Eulerian grid-based methods, such as Fast Marching and Fast Sweeping methods, solve the equation directly on a mesh. However, existing high-order Fast Sweeping methods (typically point-wise) suffer from slow convergence on fine meshes and poor utilization of modern vectorized hardware. Furthermore, high-order WENO (Weighted Essentially Non-Oscillatory) schemes often face convergence issues where iteration residues stagnate at the truncation-error level rather than machine zero.

Methodology
The authors propose a class of high-order, semi-implicit Newton-type Gauss–Seidel Lax–Friedrichs fast sweeping methods. The methodology builds upon the line-wise Newton framework introduced by Li and Qian [19], extending it to fifth-, seventh-, and ninth-order accuracy.

Semi-implicit Line-wise Solver: Instead of updating grid points individually (point-wise), the method updates entire lines (rows or columns) simultaneously. For a specific column $j$ , the system of equations $F_j(T_j) = 0$ is solved using Newton's method.
Jacobian Structure: A critical component of the approach is the construction of the Jacobian matrix $\nabla F_j$ . By utilizing a first-order Lax–Friedrichs discretization for the implicit part of the update, the authors demonstrate that the Jacobian remains tridiagonal and strictly diagonally dominant regardless of the order of the WENO reconstruction used for the spatial derivatives. This structural preservation allows the linear system to be solved efficiently in $O(N)$ operations using the Thomas algorithm, maintaining the overall $O(N^2)$ complexity per sweep in 2D.
High-Order WENO Reconstruction: To achieve high-order accuracy, the spatial derivatives ( $T_x, T_y$ ) within the numerical Hamiltonian are approximated using WENO reconstructions of orders 5, 7, and 9. The paper details the specific stencils, smoothness indicators ( $\beta_k$ ), and optimal linear weights ( $d_k$ ) for these reconstructions.
Sweeping Strategies: The method employs Gauss–Seidel iterations with three alternating sweeping strategies:
- Column-wise (sweeping columns in forward and backward directions).
- Row-wise (sweeping rows in forward and backward directions).
- Column-row-wise (a combination of the above, sweeping the domain four times per iteration).
Initialization and Boundary Treatment: The high-order schemes are initialized using a first-order point-wise Gauss–Seidel method. Boundary treatments involve linear extrapolation or enforcing exact solutions on physical boundaries and neighboring points, depending on the order and mesh resolution.

Key Contributions

Extension of Newton-type Framework: The paper successfully extends the line-wise Newton-type fast sweeping method from first/third-order (as in [19]) to fifth-, seventh-, and ninth-order accuracy.
Preservation of Efficiency: The authors prove that incorporating high-order WENO approximations into the numerical Hamiltonian does not compromise the tridiagonal and strictly diagonally dominant structure of the Jacobian. This ensures that the computational cost per Newton step remains linear ( $O(N)$ ), avoiding the need for more complex linear solvers.
Comprehensive Numerical Validation: The study provides extensive numerical experiments in both two and three spatial dimensions, covering isotropic and anisotropic Eikonal equations with moving fluids.

Results
Numerical examples demonstrate that the proposed schemes achieve their designed orders of accuracy for smooth solutions.

Convergence: In tests involving isotropic and anisotropic cases (Examples 4.1–4.6), the methods converge to machine zero, overcoming the stagnation issues often seen in classical high-order WENO fast sweeping.
Accuracy: Tables 4.1 through 4.10 show that WENO5, WENO7, and WENO9 schemes achieve high convergence orders (often exceeding 5th order and reaching 10th+ order in specific error norms) as the mesh is refined.
Efficiency: The line-wise approach significantly reduces the number of sweeps required compared to point-wise schemes. The authors note that the Newton-type algorithm typically requires roughly half as many sweeps as point-wise schemes.
Robustness: The methods handle complex scenarios, including 3D problems with background flows (Example 4.6) and problems with discontinuous wave speeds or multiple wavefronts (Example 4.7), producing results comparable to lower-order methods but with higher accuracy on coarser grids.

Significance and Claims
The paper claims that the proposed high-order Newton-type fast sweeping methods offer a robust and efficient solution for static HJ equations, particularly for the generalized Eikonal equation in moving fluids. The primary significance lies in the ability to achieve high-order accuracy without sacrificing the computational efficiency of the line-wise Newton solver. By maintaining the tridiagonal structure of the Jacobian, the method leverages modern hardware vectorization capabilities effectively.

The authors modestly note that the convergence of higher-order schemes is sensitive to numerical parameters (such as the viscosity parameter $\alpha$ and the WENO smoothness parameter $\epsilon_{WENO}$ ), which they attribute to the oscillatory nature of high-degree interpolating polynomials. They also observe that the choice of sweeping strategy (column-wise vs. row-wise vs. combined) affects convergence behavior, suggesting a relationship with the structure of the background velocity field $v(x)$ . The paper concludes that while the current framework is effective, future work will focus on developing more robust WENO reconstructions to reduce parameter sensitivity and establishing systematic guidelines for selecting sweeping strategies based on problem structure.

More like this