Warum werden Octrees für die Multipolraumzerlegung verwendet?

18

In den meisten (allen?) Implementierungen der Fast Multipole Method (FMM) werden Octrees verwendet, um die relevante Domäne zu zerlegen. Theoretisch liefern Octrees eine einfache Volumengrenze, die zum Nachweis der O (n) -Laufzeit eines FMM nützlich ist. Gibt es über diese theoretischen Überlegungen hinaus Vorteile bei der Verwendung eines Octree gegenüber anderen Baum- oder Versuchsdatenstrukturen?

Das Ermitteln der Interaktionsliste ist mit einem Octree möglicherweise einfacher, da eine Zelle ihre unmittelbaren Nachbarn kennt. Die Interaktionsliste ist jedoch nicht erforderlich, wenn ein dynamischerer Tree Traversal wie Dual Tree Traversal verwendet wird .

Eine Alternative wäre ein kd-Baum. Ein möglicher theoretischer Nachteil ist, dass die Konstruktion teure Mittelwertsuchoperationen erfordert. Es gibt jedoch Versionen von kd-trees, für die während der Erstellung kein Medianwert ermittelt werden muss - allerdings mit einer weniger effizienten Raumaufteilung. In Bezug auf die Implementierung ist ein kd-Baum sehr einfach.

Eine noch radikalere Alternative könnte ein R-Baum sein .

Meine Frage ist also: Was ist mit Octrees, die sie zur besten Wahl für ein FMM machen?

algorithms Ben Thompson
quelle
4
Ich denke, es macht die Bestimmung der Interaktionslisten (welche Beobachter sich im Fernfeld welcher Quellen befinden) besonders einfach.
Rchilton1980
Das Bestimmen von Interaktionslisten sollte bei jeder Form der hierarchischen Raumzerlegung recht einfach sein.
Ben Thompson
1
Ich stimme Ihnen darin zu, dass Oktobäume theoretisch einfach zu analysieren sind. Andere schnelle Summationsalgorithmen wie Matrizen (algebraische Verallgemeinerungen von FMM) verwenden unterschiedliche Bäume wie geometrische Halbierung oder Cluster-basierte Teilung. H
user2457602
1
Ich bin kein Experte in diesem Bereich, aber vielleicht spielt die Tatsache, dass Octrees mehr "Symmetrie" haben, eine Rolle? Die Partitionen in einem Octree sind regelmäßig angeordnet und haben die gleiche quadratische Form, was dazu beitragen könnte, die mehrpoligen Erweiterungen im Vergleich zu z. B. einem kd-Baum vorzunehmen.
Jannis Teunissen
Octrees sind ein natürliches Ergebnis der Zersetzung von Domänen in drei Dimensionen.
Gpavanb

Antworten:

3

Die obigen Kommentare geben einige sehr gute Gründe für die Verwendung von Octrees (dh die rekursive Halbierung des Berechnungswürfels in jeder Dimension im Gegensatz zu einer allgemeineren orthogonalen Halbierung ). Die Symmetrie und Einfachheit der Berechnung von Interaktionslisten ist ein großes Plus.

Ich würde argumentieren, dass das vielleicht wichtigste Merkmal, das Octrees in die Tabelle bringen, darin besteht, dass der Additionssatz, der das FMM beschreibt, systematisch für Fernzonenwechselwirkungen unabhängig von der Geometrie mit dem extrem einfachen Kriterium der guten Trennung von einem oder mehreren "Puffern" erfüllt wird. Kisten. Mit anderen Worten wird garantiert, dass die FMM-Summenrepräsentation des Potentialfeldes unter nicht pathologischen Umständen mit zunehmender Ordnung konvergiert.

jdm
quelle