G
C14 schrieb:
Was optimal ist, hängt bestimmt davon ab, was du eigentlich am Ende des Tages berechnen willst.
Kannst du noch etwas mehr zum Problem sagen?
Das Problem ist eindimensional, richtig?
Wie groß ist das Teilinterval größenordnungsmäßig verglichen mit dem Gesamtinterval und der Abtastrate?
Welche Berechnung stellst du mit der Funktion in dem Teilintervall an?
(an welchen Stellen brauchst du dafür den Funktionswert?
Brauchst du den überhaupt oder vielleicht eher Skalarprodukte mit anderen Funktionen, die du evtl. direkter approximieren kannst?)
Ich habe eigentlich versucht, das Gesamtproblem auf das Wesentliche zu reduzieren, aber hier noch etwas mehr dazu:
Das Problem ist eigentlich dreidimensional. Ich habe eine periodische Funktion und muss deren Werte und Ableitungen auf Kugeloberflächen kennen. Die (nicht-überlappenden) Kugeln sind hierbei im Realraum innerhalb einer repräsentierenden Periode der Funktion gegeben. Um die Werte und Ableitungen der Funktion auf der Kugeloberfläche zu bekommen, wird momentan eine Rayleigh-Entwicklung von ebenen Wellen nach Kugelflächenfunktionen durchgeführt.
Der Punkt ist jetzt die Zeitkomplexität bei der Skalierung des Problems. Die Skalierung des Problems ist im Wesentlichen eine Vergrößerung des periodisch fortgesetzten Bereichs. Hierbei wächst auch die Anzahl der Kugeln N_K innerhalb dieses Bereichs. Es gibt innerhalb des periodisch fortgesetzten Bereichs etwa 1000*N_K Abtastpunkte, bzw. die Anzahl der ebenen Wellen, mit denen ich die Funktion im Frequenzraum beschreibe, ist auch 1000*N_K.
Wenn ich nun für alle Kugeln diese Rayleigh-Entwicklung durchführe, dann skaliert das also wie 1000*N_K^2. Dieses quadratische Skalierungsverhalten ist eigentlich nicht wirklich zu rechtfertigen, weil ich durch die Vergrößerung des periodischen Bereichs lokal keine zusätzlichen Informationen über die Funktion erhalte und an jeder Kugel nur das lokale Verhalten der Funktion benötige. Das Ganze sollte eigentlich mehr oder weniger linear mit der Problemgröße skalieren.
Die Rayleigh-Entwicklung beruht darauf, dass man die Funktion als Linearkombination ebener Wellen gegeben hat. Der Ausgangspunkt für diese Entwicklung ist also eine Darstellung im Frequenzraum. Die Idee ist jetzt, dass ich die ursprüngliche Frequenzraumdarstellung mittels einer schnellen Fouriertransformation in O(N_K*log(N_K)) in den Realraum transformiere, dort um jede Kugeln herum in O(N_K) durch lokale Hilfsfunktionen ersetze und dann für jede Kugel die Hilfsfunktion in O(N_K) zurück in den Frequenzraum transformiere. Die Rayleigh-Entwicklungen würden dann zusammen in O(N_K) ablaufen, da der lokale Bereich für jede Kugel nicht mit der Problemgröße skaliert. Durch so einen Ansatz würde ich insgesamt also von einem quadratischen Skalierungsverhalten hin zu einem O(N_K*log(N_K)) Verhalten kommen, wobei es einen additiven linearen Term gibt, der die Zeitkomplexität für die relevanten Problemgrößen (100 < N_K < 10000++) dominieren sollte. Der O(N_K*log(N_K)) Beitrag zur Skalierung kommt nur dadurch, dass die Funktion ursprünglich in einer Frequenzraumdarstellung gegeben ist, davon wird man nicht wegkommen.
Ich brauche am Schluss keine Skalarprodukte, sondern wirklich das Verhalten der Funktion und ihrer Ableitungen auf der Kugeloberfläche. Punktweise und auf mehrere Stellen genau.