Algorithms for Numerical Analysis in High Dimensions. Part I: Definitions, linear algebra and basic algorithms

Martin Mohlenkamp
Ohio University

When an algorithm in dimension one is extended to
dimension d , in nearly every case its computational cost is taken to the power d . This fundamental difficulty is the single greatest impediment to solving many important problems, and has been dubbed the "Curse of Dimensionality". We have developed a way to bypass the curse for many numerical analysis applications, by using a generalization of separation of variables that allows us to control accuracy. Basic linear algebra operations can be performed in this representation using one-dimensional operations, thus avoiding the exponential scaling with respect to the dimension. These methods not only speed up computations in dimensions 2,\,3 and 4 , but also allow computations in much higher dimensions that would otherwise be impossible.

Presentation (PDF File)

Back to MGA Workshop II: Multiscale Geometry in Scientific Computing