HOME

TheInfoList



OR:

An eikonal equation (from Greek εἰκών, image) is a
non-linear In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many other ...
first-order partial differential equation that is encountered in problems of wave propagation. The classical eikonal equation in geometric optics is a differential equation of the form where x lies in an open subset of \mathbb^n, n(x) is a positive function, \nabla denotes the gradient, and , \cdot , is the Euclidean norm. The function n is given and one seeks solutions u . In the context of geometric optics, the function n is the refractive index of the medium. More generally, an eikonal equation is an equation of the form where H is a function of 2n variables. Here the function H is given, and u is the solution. If H(x,y)= , y, - n(x) , then equation () becomes (). Eikonal equations naturally arise in the WKB method and the study of
Maxwell's equations Maxwell's equations, or Maxwell–Heaviside equations, are a set of coupled partial differential equations that, together with the Lorentz force law, form the foundation of classical electromagnetism, classical optics, and electric circuits. ...
. Eikonal equations provide a link between physical (wave) optics and geometric (ray) optics. One fast computational algorithm to approximate the solution to the eikonal equation is the
fast marching method The fast marching methodJ.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591--1595, 1996/ref> is a numerical method created by James Sethian for solving boundary value problems ...
.


History

The term "eikonal" was first used in the context of geometric optics by
Heinrich Bruns Ernst Heinrich Bruns (4 September 1848 – 23 September 1919) was a German mathematician and astronomer, who also contributed to the development of the field of theoretical geodesy. Early life Heinrich Bruns was born on 4 September 1848 in Be ...
. However, the actual equation appears earlier in the seminal work of William Rowan Hamilton on geometric optics.


Physical interpretation


Continuous shortest-path problems

Suppose that \Omega is an open set with suitably smooth boundary \partial \Omega. The solution to the eikonal equation :\left, \nabla u(x)\ = \frac 1 \text x \in \Omega \subset \mathbb^n, :u(x) = q(x) \text x \in \partial\Omega can be interpreted as the minimal amount of time required to travel from x to \partial \Omega, where f: \bar \to (0, +\infty) is the speed of travel, and q: \partial\Omega \to [0, +\infty) is an exit-time penalty. (Alternatively this can be posed as a minimal cost-to-exit by making the right-side C(x)/f(x) and q an exit-cost penalty.) In the special case when f=1, the solution gives the signed distance from \partial \Omega. By assuming that \nabla u(x) exists at all points, it is easy to prove that u(x) corresponds to a time-optimal control problem using [ Bellman's optimality principle and a Taylor expansion. Unfortunately, it is not guaranteed that \nabla u(x) exists at all points, and more advanced techniques are necessary to prove this. This led to the development of
viscosity solution In mathematics, the viscosity solution concept was introduced in the early 1980s by Pierre-Louis Lions and Michael G. Crandall as a generalization of the classical concept of what is meant by a 'solution' to a partial differential equation (PDE). ...
s in the 1980s by Pierre-Louis Lions and Michael G. Crandall, and Lions won a
Fields Medal The Fields Medal is a prize awarded to two, three, or four mathematicians under 40 years of age at the International Congress of the International Mathematical Union (IMU), a meeting that takes place every four years. The name of the award h ...
for his contributions.


Electromagnetic potential

The physical meaning of the eikonal equation is related to the formula : \mathbf E = -\nabla V, where \mathbf E is the electric field strength, and V is the electric potential. There is a similar equation for velocity potential in fluid flow and temperature in heat transfer. The physical meaning of this equation in the electromagnetic example is that any charge in the region is pushed to move at right angles to the lines of constant potential, and along lines of force determined by the field of the E vector and the sign of the charge. Ray optics and electromagnetism are related by the fact that the eikonal equation gives a second electromagnetic formula of the same form as the potential equation above where the line of constant potential has been replaced by a line of constant phase, and the force lines have been replaced by normal vectors coming out of the constant phase line at right angles. The magnitude of these normal vectors is given by the square root of the relative permittivity. The line of constant phase can be considered the edge of one of the advancing light waves (''
wavefront In physics, the wavefront of a time-varying ''wave field'' is the set ( locus) of all points having the same ''phase''. The term is generally meaningful only for fields that, at each point, vary sinusoidally in time with a single temporal frequ ...
''). The normal vectors are the rays the light is traveling down in ray optics.


Computational algorithms

Several fast and efficient algorithms to solve the eikonal equation have been developed since the 1990s. Many of these algorithms take advantage of algorithms developed much earlier for shortest path problems on graphs with nonnegative edge lengths. These algorithms take advantage of the
causality Causality (also referred to as causation, or cause and effect) is influence by which one event, process, state, or object (''a'' ''cause'') contributes to the production of another event, process, state, or object (an ''effect'') where the ca ...
provided by the physical interpretation and typically discretize the domain using a mesh or regular grid and calculate the solution at each discretized point. Eikonal solvers on triangulated manifolds are. Sethian's
fast marching method The fast marching methodJ.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591--1595, 1996/ref> is a numerical method created by James Sethian for solving boundary value problems ...
(FMM) was the first "fast and efficient" algorithm created to solve the Eikonal equation. The original description discretizes the domain \Omega \subset \mathbb^n into a regular grid and "marches" the solution from "known" values to the undiscovered regions, precisely mirroring the logic of Dijkstra's algorithm. If \Omega is discretized and has M meshpoints, then the computational complexity is O(M\log M) where the \log term comes from the use of a heap (typically binary). A number of modifications can be prescribed to FMM since it is classified as a label-setting method. In addition, FMM has been generalized to operate on general meshes that discretize the domain. Label-correcting methods such as the Bellman–Ford algorithm can also be used to solve the discretized Eikonal equation also with numerous modifications allowed (e.g. "Small Labels First" or "Large Labels Last" ). Two-queue methods have also been developed that are essentially a version of the Bellman-Ford algorithm except two queues are used with a threshold used to determine which queue a gridpoint should be assigned to based on local information. Sweeping algorithms such as the
fast sweeping method In applied mathematics, the fast sweeping method is a numerical method for solving boundary value problems of the Eikonal equation. : , \nabla u(\mathbf), = \frac 1 \text \mathbf \in \Omega : u(\mathbf) = 0 \text \mathbf \in \partial \Omega ...
(FSM) are highly efficient for solving Eikonal equations when the corresponding characteristic curves do not change direction very often. These algorithms are label-correcting but do not make use of a queue or heap, and instead prescribe different orderings for the gridpoints to be updated and iterate through these orderings until convergence. Some improvements were introduced such as "locking" gridpoints during a sweep if does not receive an update, but on highly refined grids and higher-dimensional spaces there is still a large overhead due to having to pass through every gridpoint. Parallel methods have been introduced that attempt to decompose the domain and perform sweeping on each decomposed subset. Zhao's parallel implementation decomposes the domain into n-dimensional subsets and then runs an individual FSM on each subset. Dextrixhe's parallel implementation also decomposes the domain, but parallelizes each individual sweep so that processors are responsible for updating gridpoints in an (n-1)-dimensional
hyperplane In geometry, a hyperplane is a subspace whose dimension is one less than that of its ''ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyperp ...
until the entire domain is fully swept. Hybrid methods have also been introduced that take advantage of FMM's efficiency with FSM's simplicity. For example, the Heap Cell Method (HCM) decomposes the domain into cells and performs FMM on the cell-domain, and each time a "cell" is updated FSM is performed on the local gridpoint-domain that lies within that cell. A parallelized version of HCM has also been developed.


Numerical approximation

For simplicity assume that \Omega is discretized into a uniform grid with spacings h_x and h_y in the x and y directions, respectively.


2D approximation on a Cartesian grid

Assume that a gridpoint x_ has value U_ = U(x_) \approx u(x_). A first-order scheme to approximate the partial derivatives is :\max\left(D_^U, -D_^U, 0\right)^2 + \max\left(D_^U, -D_^U, 0\right)^2 \ = \ \frac where :u_x(x_) \approx D_^ U = \frac \quad\text\quad u_y(x_) \approx D_^ U = \frac. Due to the consistent, monotone, and causal properties of this discretization it is easy to show that if U_X = \min(U_,U_) and U_Y = \min(U_, U_) and , U_X/h_x-U_Y/h_y, \leq 1/f_ then :\left(\frac\right)^2 + \left(\frac\right)^2 = \frac which can be solved as a quadratic. In the limiting case of h_x = h_y = h, this reduces to :U_ = \frac + \frac\sqrt. This solution will always exist as long as , U_X-U_Y, \leq \sqrth/f_ is satisfied and is larger than both, U_X and U_Y, as long as , U_X-U_Y, \leq h/f_ . If , U_X/h_x-U_Y/h_y, \geq 1/f_, a lower-dimensional update must be performed by assuming one of the partial derivatives is 0: :U_ = \min\left(U_X + \frac, U_Y + \frac\right).


''n''-D approximation on a Cartesian grid

Assume that a grid point x has value U = U(x) \approx u(x). Repeating the same steps as in the n=2 case we can use a first-order scheme to approximate the partial derivatives. Let U_i be the minimum of the values of the neighbors in the \pm\mathbf_i directions, where \mathbf_i is a standard unit basis vector. The approximation is then :\sum_^n \left(\frac\right)^2 \ = \ \frac. Solving this quadratic equation for U yields: :U = \frac\sum_^n U_j + \frac\sqrt. If the discriminant in the square root is negative, then a lower-dimensional update must be performed (i.e. one of the partial derivatives is 0). If n=2 then perform the one-dimensional update :U = \frac + \min_ U_j. If n \geq 3 then perform an n-1 dimensional update using the values \ \setminus \ for every i=1,\ldots,n and choose the smallest.


Mathematical description

An eikonal equation is one of the form :H(x,\nabla u(x)) = 0 :u(0,x') = u_0(x'),\text x = (x_1,x') The plane x = (0,x') can be thought of as the initial condition, by thinking of x_1 as t. We could also solve the equation on a subset of this plane, or on a curved surface, with obvious modifications. The eikonal equation shows up in geometrical optics, which is a way of studying solutions of the wave equation c^2 , \nabla_x u, ^2 = , \partial_t u, ^2, where c(x) and u(x,t). In geometric optics, the eikonal equation describes the phase fronts of waves. Under reasonable hypothesis on the "initial" data, the eikonal equation admits a local solution, but a global smooth solution (e.g. a solution for all time in the geometrical optics case) is not possible. The reason is that caustics may develop. In the geometrical optics case, this means that wavefronts cross. We can solve the eikonal equation using the method of characteristics. One must impose the "non-characteristic" hypothesis \partial_ H(x,p) \neq 0 along the initial hypersurface x = (0,x'), where ''H'' = ''H''(''x'',''p'') and ''p'' = (''p''1,...,''p''''n'') is the variable that gets replaced by ∇''u''. Here ''x'' = (''x''1,...,''x''''n'') = (''t'',''x''′). First, solve the problem H(x,\xi(x)) = 0, \xi(x) = \nabla u(x), x\in H. This is done by defining curves (and values of \xi on those curves) as :\dot x(s) = \nabla_\xi H(x(s),\xi(s)), \;\;\;\; \dot \xi(s) = -\nabla_x H(x(s),\xi(s)). :x(0) = x_0, \;\;\;\; \xi(x(0)) = \nabla u(x(0)). Note that even before we have a solution u, we know \nabla u(x) for x = (0,x') due to our equation for H. That these equations have a solution for some interval 0 \leq s < s_1 follows from standard ODE theorems (using the non-characteristic hypothesis). These curves fill out an
open set In mathematics, open sets are a generalization of open intervals in the real line. In a metric space (a set along with a distance defined between any two points), open sets are the sets that, with every point , contain all points that are ...
around the plane x = (0,x'). Thus the curves define the value of \xi in an open set about our initial plane. Once defined as such it is easy to see using the chain rule that \partial_s H(x(s), \xi(s)) = 0, and therefore H = 0 along these curves. We want our solution u to satisfy \nabla u = \xi, or more specifically, for every s, (\nabla u)(x(s)) = \xi(x(s)). Assuming for a minute that this is possible, for any solution u(x) we must have :\frac u(x(s)) = \nabla u(x(s)) \cdot \dot x(s) = \xi \cdot \frac, and therefore :u(x(t)) = u(x(0)) + \int_0^t \xi(x(s))\cdot \dot x(s)\, ds. In other words, the solution u will be given in a neighborhood of the initial plane by an explicit equation. However, since the different paths x(t), starting from different initial points may cross, the solution may become multi-valued, at which point we have developed caustics. We also have (even before showing that u is a solution) :\xi(x(t)) = \xi(x(0)) - \int_0^t \nabla_x H(x(s),\xi(x(s))) \, ds. It remains to show that \xi, which we have defined in a neighborhood of our initial plane, is the gradient of some function u. This will follow if we show that the vector field \xi is curl free. Consider the first term in the definition of \xi. This term, \xi(x(0)) = \nabla u(x(0)) is curl free as it is the gradient of a function. As for the other term, we note :\frac H = \frac H. The result follows.


Applications

* A concrete application is the
computation of radiowave attenuation in the atmosphere The computation of radiowave attenuation in the atmosphere is a series of radio propagation models and methods to estimate the path loss due to attenuation of the signal passing through the atmosphere by the absorption of its different components ...
. * Finding the shape from shading in computer vision. * Geometric optics * Continuous shortest path problems * Image segmentation * Study of the shape for a solid propellant rocket grain


See also

* Hamilton–Jacobi–Bellman equation * Hamilton–Jacobi equation *
Fermat's principle Fermat's principle, also known as the principle of least time, is the link between ray optics and wave optics. In its original "strong" form, Fermat's principle states that the path taken by a ray between two given points is the pat ...
* One-way wave equation


References


Further reading

* *


External links


The linearized eikonal equationEnglish translation of "Das Eikonal" by Heinrich Bruns
{{DEFAULTSORT:Eikonal Equation Partial differential equations Geometrical optics