Tractability of Multivariate Problems

多元问题的可处理性

• 批准号: 0074238
• 负责人: Joseph Traub
• 金额: $ 27万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0074238&HistoricalAwards=false
• 关键词: Tractability; Multivariate; Problems

The investigator and his colleague study ways to breakintractability of algorithms for high-dimensional problems. Theyfocus on high-dimensional integration, explore breakingintractability either by settling for a stochastic assurance ofsmall error or by using additional domain knowledge, and furtherdevelop FinDer, a software package for high-dimensionalintegration. The computational complexity of an algorithm is a measure ofthe amount of work the algorithm must perform to produce asolution for given inputs. Usually the complexity is measured inthe size of the problem being solved. For example, finding thesolution of a linear matrix equation in N unknowns --- anN-dimsional problem --- generally takes on the order of N times Ntimes N arithmetic operations; the computational complexity ofsuch an algorithm is N cubed. There is huge interest in solvinghigh-dimensional problems. Many applications involve functionsof hundreds, thousands, and even an infinite number of variables.Examples occur in physics, chemistry, mathematical science, andeconomics. These problems must usually be solved numerically andone has to settle for an approximate numerical solution to withinan error epsilon. If a worst case deterministic assurance of anepsilon approximation is desired, then the computationalcomplexity usually depends exponentially on the number ofvariables; the problem is said to be intractible. Theinvestigators study breaking intractability either by settlingfor a stochastic assurance of small error or by using additionaldomain knowledge. The use of formalizing additional domainknowledge is a powerful new idea. In particular, theinvestigators study under what conditions a double win isachievable for the important problem of high-dimensionalintegration: when does an algorithm to compute the value of ahigh-dimensional integral both converge faster than a Monte Carloalgorithm and do so with a worst case deterministic assurance?They apply the theoretical results to improve the FinDer softwaresystem for computing high-dimensional integrals. This newparadigm is applied to other problems of computationalmathematics.

研究者和他的同事研究如何打破高维问题算法的可处理性。 他们专注于高维集成，探索突破棘手的解决方案，通过解决小误差的随机保证或通过使用额外的领域知识，并进一步开发Finder，一个软件包的高维集成。 一个算法的计算复杂度是对给定输入的算法必须执行的工作量的度量。 复杂性通常是以所解决问题的大小来衡量的。 例如，寻找一个N维线性矩阵方程的解--一个N维问题--通常需要N乘N乘N的算术运算，这样一个算法的计算复杂度是N的立方。 人们对解决高维问题有着极大的兴趣。 许多应用涉及到成百上千甚至无穷多个变量的函数，例如物理学、化学、数学和经济学。 这些问题通常必须解决数值和一个解决的近似数值解误差范围内。 如果一个最坏的情况下确定性保证的近似值是期望的，那么计算的复杂性通常取决于指数的变量的数量，这个问题被称为棘手。 研究者们研究如何通过解决小误差的随机保证或使用额外的领域知识来打破棘手性。 使用形式化的额外领域知识是一个强大的新想法。 特别是，调查研究在什么条件下双赢是实现的重要问题的high-dimensionalintegration：当一个算法来计算的值的一个高维积分都收敛速度比蒙特卡洛算法，这样做的最坏情况下确定性的保证？他们将理论结果应用于改进计算高维积分的Finder软件。 这种新的范式被应用到计算数学的其他问题。