Efficient Algorithms for Multivariate Problems

There are many computational problems dealing with functions of very many variables. The number d of variables is in hundreds, thousands, or even unbounded. For instance, d = 360 in the mortgage-backed securities problem, and formally d = 00 in path integrals, important e.g., in quantum physics and chemistry, mathematical finance, and computational mathematics. The classical algorithms are inadequate for such problems since 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 (i.e., too expensive to solve) or unsolvable (i.e., impossible to solve). This is why new assumptions and new approaches need to be devised to guarantee an existence of efficient algorithms with much weaker dependence on d. A part of the proposed research will deal with 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 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 and efficient algorithms in the average case and randomized settings will be investigated as well. The randomized setting is of a special interest since very recent results seem to indicate the existence of very efficient randomized algorithms for a host of linear problems as long as the class of input functions is a reproducing kernel Hilbert space. Majority of numerical methods and tractability results deal with functions over bounded domains, whereas many important problems (e.g., in finance) call for approximating weighted integrals of the form JIRd f(x) p(x) dx. Commonly used approaches for such integrals are ad hoc and often far from optimal. This is why a part of the research will deal with problems defined over classes of functions with unbounded domains. 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 22 papers and many presentations including over 20 international ones. He received the Information-Based Complexity Prize for 2001. Broader Impact: 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) and Women in Engineering Program. 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.