Abstract of Lutz Kämmerer

High dimensional sparse fast Fourier transforms
A straightforward discretisation of high dimensional problems often leads to an exponential growth in the number of degrees of freedom. So, computational costs of even efficient algorithms increase similarly. Sparse frequency grids like hyperbolic crosses allow for a good approximative representation of functions of appropriate smoothness and decrease the number of used Fourier coefficients strongly. As a matter of course, an important issue is the customisation of efficient algorithms to these thinner discretisations. Their total complexity should be within logarithmic factors linear in the total problem size. We discuss hyperbolic cross fast Fourier transforms with different sampling schemes. Besides the sparse grid, we consider lattices known from quadrature formulas as dedicated sampling nodes.


Lars Grasedyck (MPI Leipzig, Germany)
Wolfgang Hackbusch (MPI Leipzig, Germany)
Boris Khoromskij (MPI Leipzig, Germany)