• Research
• Profiles
• Research Profile

Random Walks on the Adjoint Equation

The iCME's interdiciplinary environment enables researchers with expertise in different fields to collaborate and solve previously intractable problems.

Solving the adjoint equation associated with a partial different equation allows us to answer a key question: How do uncertainties in the initial condition affect the final solution? This question is the center of verifying and validating the results of scientific simulations.

Although adjoint methods are extremely useful, often they are computationally intractable. Intuitively, solving the adjoint equation involves reversing the computation of the solution so we can understand how the final solution depends upon the initial condition.

For a discretized partial differential equation, a simple algorithm for computing the adjoint requires storing all intermediate data because it needs to run the procedure in reverse. On a 5000 x 5000 grid, computing the adjoint after only 1000 time steps requires storing 25 billion numbers. With larger problems, such as fluid-dynamics simulations with around 100 million grid points, the storage quickly scales to trillions of numbers. Better approaches reduce the storage requirements, but increase the computation cost.

Combining ideas from algorithm design and stochastic processes, Etemadi, Gleich, Moin, Saberi, and Wang eliminate the extra storage requiment of previous techniques for computing the adjoint solution with nearly no increase in computation cost. The key idea is to use a random walk to propagate information about the adjoint equation while computing the solution to the partial differential equation.

Solving Burger's equation in two-dimensions with a one-step upwinding scheme illustrates how their approach works. The random walk from the current time step to the next has the following structure. Each blue circle represents a mesh-point. The right figure represents how information is propagated from a single mesh point.

Because the random walk only propagates information forward in time, this scheme avoids storing the entire time history.  Rather than deterministically computing the influence of each of the five links to the next time step, the random walk picks one link to the next time step and uses that information to approximate the result.

The Monte carlo method can reduce the running time and memory space requirements substantially. For example in a simulation of Burger's equation on a grid of size 5000, the time was reduced from 1.1 seconds to 0.13 seconds and memory space was reduced from 200 kB to 28.8 kB. The Monte carlo method estimated the adjoint for each variable with significant accuracy.

Methods based on the adjoint equation are a key tool for analyzing and controlling the behavior of many systems including aircraft thrust and trajectory optimization. By solving the adjoint equation associated with a system, we can compute solutions to a large class of optimization problems, inverse problems, and control problems.