Causality as a source of efficiency in numerical methods.

迭代法求解大型非线性耦合方程组的费用往往过高。 这样的系统经常导致静态非线性偏微分方程的离散化，提出了从业者的计算效率的“瓶颈”。然而，在许多应用中（从机器人导航到光刻，地震成像，计算几何，光学，微分游戏和图像分割），“信息流”的方向可以用来连续消除或至少显着减少方程的耦合，从而产生有效的（通常是非迭代的）数值方法。 相关的“因果关系”概念提供了一个先验的不明显的，但自然的计算元素的顺序。 主要研究者和他的合作者以前介绍了这样的因果算法的问题，在各向异性混合确定性控制和近似的几何刚性不变流形。 目前，主要研究者开发了更广泛的一类“结构因果”的随机问题的图形和连续域的有效算法。 这包括重要的特殊类型的不确定性随机性，以及多个长度尺度的最优控制问题。 研究者和他的同事们还使用拉格朗日流形的近似来建立有效的方法来恢复非线性一阶偏微分方程的多值解--这是一个在色散波计算、多波到达地震成像和层析成像中具有高度实际重要性的问题。许多重要实际问题的实时答案取决于相应偏微分方程的鲁棒和高效数值方法的可用性。 飞机避碰的最小安全距离是多少？ 如何在紧急呼叫之间安排一辆“闲置”的救护车？ 火星车在火星表面行驶的最佳轨迹是什么？ 现有的数值技术有助于回答这些问题，但仅在不现实/理想化的条件下：单一标准（例如，仅能量最优轨迹）、已知的终端时间、地形的单个可靠地图等。PI当前的工作在结合多个标准（例如，时间与精力与金钱）和不确定性（何时会收到下一个紧急呼叫？）在没有过多计算成本的情况下进行决策。

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.