Causality as a source of efficiency in numerical methods.

Cornell University, Ithaca NY

Investigators

Abstract

Iterative methods for large non-linear systems of coupled equations are often prohibitively expensive. Such systems frequently result from discretizations of static nonlinear partial differential equations, presenting practitioners with a computational efficiency "bottleneck". However, in many applications (from robotic navigation to photolithography, seismic imaging, computational geometry, optics, differential games, and segmentation of images) the direction of "information flow" can be used to successively eliminate or at least significantly decrease the coupling of equations, resulting in efficient (often non-iterative) numerical methods. The related notion of "causality" provides an a priori unobvious yet natural ordering of the elements of computation. The primary investigator and his collaborators have previously introduced such causal algorithms for problems in anisotropic & hybrid deterministic control and for approximations of geometrically stiff invariant manifolds. Currently, the primary investigator develops efficient algorithms for a wider class of "structurally causal" stochastic problems on graphs and in continuous domains. This includes important special types of uncertainty & stochasticity as well as optimal control problems with multiple length scales. The investigator and his colleagues also use approximations of Lagrangian manifolds to build efficient methods for recovering multivalued solutions of nonlinear first-order PDEs -- a problem of high practical importance in dispersive waves computations, multiple-arrival seismic imaging and tomography. Real-time answers to many important practical questions depend on availability of robust and efficient numerical methods for the corresponding partial differential equations. What is the minimum safe distance for the aircraft collision avoidance? How should an "idle" ambulance be routed in between emergency calls? Which trajectory is optimal for a rover traveling on the surface of Mars? The prior numerical techniques help one answer these questions, but only under unrealistic/idealized conditions: a single criterion (e.g., energy-optimal trajectories only), a known terminal time, a single reliable map of the terrain, etc. The PI's current work makes a difference in incorporating multiple criteria (e.g., time versus energy versus money) and uncertainty (when will the next emergency call be received?) into the decision making process without excessive computational costs.