Tractability of Multivariate Problems

这位研究人员和他的同事研究了高维问题算法的可承受力的方法。他们专注于高维积分，通过满足小误差的随机保证或使用额外的领域知识来探索打破困难，并进一步开发用于高维积分的软件包FINDER。算法的计算复杂性是对该算法为产生给定输入的解所必须执行的工作量的度量。通常，复杂性是用要解决的问题的大小来衡量的。例如，在N个未知数中求一个线性矩阵方程的解-ANN-维问题-通常需要N乘N乘N个算术运算的数量级；这样的算法的计算复杂度是N立方体。人们对解决高维问题有着巨大的兴趣。许多应用涉及数百、数千、甚至无限多个变量的函数，例如在物理、化学、数学科学和经济学中。这些问题通常必须用数值方法解决，而且必须在误差ε内找到一个近似的数值解。如果希望在最坏的情况下确定性地保证epsilon近似，那么计算的复杂性通常以指数形式依赖于变量的数量；这个问题被称为不可解的。研究人员通过解决小误差的随机保证或通过使用额外的领域知识来研究打破难题。使用正规化的额外领域知识是一个强大的新想法。特别是，研究人员研究了在什么条件下高维积分这一重要问题可以实现双赢：何时计算高维积分值的算法既比蒙特卡罗算法收敛得更快，又能在最坏情况下保证确定性？他们应用理论结果来改进计算高维积分的Finder软件系统。这一新范式也被应用于计算数学的其他问题。

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.