## Grants and Contracts Details

### Description

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

Effective start/end date | 8/15/06 → 7/31/09 |

- Wasilkowski, Grzegorz (PI)

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.

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

Effective start/end date | 8/15/06 → 7/31/09 |

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.