Tractability of 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.