Schnelle Berechnung von Faltungsintegralen

Üblicherweise verlangt die schnelle exakte Auswertung eines Faltungsintegrals ƒ(y)g(x-y)dy, dass die Funktionen ƒ,g auf einem gleichmäßigen Gitter diskretisiert sind, damit die schnelle Fourier-Transformation anwendbar ist. Im Vortrag gehen wir von lokal verfeinerten Gittern aus und verlangen keine Glattheitseigenschaften von ƒ,g. Die Faltungsfunktion ƒ*g soll exakt in ein gegebenes, lokal verfeinertes Gitter projiziert werden (Bestapproximation im L²-Sinne). Unter bestimmten Annahmen an die Gitterverfeinerung ergeben sich die arithemtischen Kosten wieder als O(N log N), wobei N die Summe der Dimensionen der Unterräme ist, die ƒ, g und die resultierende Faltungsfunktion enthält.