## Grants and Contracts Details

### Description

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.

Status | Finished |
---|---|

Effective start/end date | 9/15/05 → 8/31/06 |

## Fingerprint

Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.