Information-Based Complexity and Efficient Algorithms for Multivariate Problems

There are many computational problems dealing with multivariate functions. For some of them the number d of variables is small; however, there is a host of important applications involving functions of hundreds, thousands or even much more variables. For instance, in a mortgage-backed securities problem d = 360, and in path integrals formally d = 00. Unfortunately, classical algorithms are inadequate for such problems since typically their costs increase exponentially (or superexponentially) fast with d. The situation is even more challenging since under the commonly made assumptions on the classes of functions, the corresponding multivariate problems are intractable (Le., too expensive to solve) or unsolvable (Le., impossible to solve). This is why new assumptions and new approaches need to be devised to guarantee an existence of efficient algorithms. This is why the proposed research will concentrate on tractability of multivariate problems. Although a significant progress has recently been made, much more is needed. For instance, there are many classes of multivariate problems for which only existence of efficient algorithms is known. The research will provide algorithms for solving d-variate problems in time polynomial in d (tractability), or even in cost independent of d (strong tractability). Worst case tractability for weighted tensor product spaces is relatively well understood; however, little is known about problems with low effective dimension. Since such problems are typical for some important applications (e.g., finance), significant effort will be devoted to the tractability study of problems with low effective dimensions. Because worst case intractability can often be overcome by switching to other settings, tractability in the average case and randomized settings will be investigated as well. Majority of numerical methods and tractability results deal with functions over bounded domains. A primary example is the classical integration problem of approximating J[O,l]d f(x) dx. On the other hand, many important problems (e.g., in finance) call for approximating weighted integrals of the form JJRd f{x) p(x) dx. Commonly used approaches for such integrals are ad hoc and often far from optimal (e.g., a reduction of an unbounded domain via a change of variables induces singularity!). This is why a significant part of the research will deal with problems defined over classes of functions with unbounded domains; the worst case, the average case, and the randomized settings will be studied. This will enrich understanding of the complexity of such problems and will provide new algorithms that are (almost) optimal. Path integrals are of importance to quantum physics and chemistry, mathematical finance, and computational mathematics. Continuation of already initiated research on path integration will results in new efficient methods. Theoretical work will yield new and efficient algorithms for a host of important problems. These algorithms will be developed and thoroughly tested with stability and efficiency as goals. Intellectual Merit: The proposed research will significantly enhance the understanding of the complexity of multivariate problems and their tractability. It will also result in new assumptions concerning input functions as well as new algorithms that will provide very efficient ways to solve problems that cannot be solved by the classical methods. The PI is qualified to conduct the research; support in the last 5 years resulted in 26 papers and many presentations including 19 international ones. He received the Information-Based Complexity Prize for 2001. BroaderImpact: Research will involve both graduate and undergraduate students. Strong effort will be made to hire students from underrepresented groups by combining resources from this Grant with special University-wide fellowships (e.g., Lyman T. Johnson and Graduate Fellowship for Women). New results/methods will be presented in two numerical courses (CS 321 and CS 537) taught by the PI. Since the results will pertain to problems that are important in a host of different areas, the results will be presented at various electronic digests (e.g., CAC-NET-Digest and MCQMC-Digest) and multidisciplinary conferences and journals; see the end of the proposal description for more. Also, a special web page will be maintained to disseminate promptly research results and software. Finally, it should be stressed that the University of Kentucky is an EPSCoR institution.