权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Causality as a source of efficiency in numerical methods.

因果关系是数值方法效率的来源。

基本信息

批准号：
1016150
负责人：
Alexander Vladimirsky
金额：
$ 24.92万
依托单位：
Cornell University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2011
资助国家：
美国
起止时间：
2011-02-15 至 2016-01-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016150&HistoricalAwards=false
关键词：
Causality source efficiency numerical methods.

项目摘要

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.

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