PDEs in vielen Dimensionen

Ich weiß, dass die meisten Methoden, um ungefähre Lösungen für PDEs zu finden, schlecht mit der Anzahl der Dimensionen skalieren und dass Monte Carlo für Situationen verwendet wird, in denen ~ 100 Dimensionen erforderlich sind.

Was sind gute Methoden, um PDEs in ~ 4-10 Dimensionen effizient numerisch zu lösen? 10-100?

Gibt es neben Monte Carlo noch andere Methoden, die mit der Anzahl der Dimensionen gut übereinstimmen?

pde monte-carlo high-dimensional Dan
quelle

Es kann hilfreich sein, ein bisschen mehr Informationen über die Art des Problems bereitzustellen, das Sie lösen. Die meisten in der Computerwissenschaft behandelten PDEs sind in der Regel höchstens vierdimensional (Zeit plus drei räumliche Dimensionen). Sind die Variablen räumliche oder zeitliche Variablen oder gibt es andere Abhängigkeiten, die Sie einbeziehen?

Aeismail

Raumvariablen. In der Quantenmechanik ist die Wellenfunktion

dimensional, wenn Sie die Näherungen, die Sie in der Dichtefunktionaltheorie oder in Hartree-Fock verwenden, nicht verwenden möchten , wobei

die Anzahl der Elektronen ist. Selbst kleine Atome und Moleküle benötigen eine große Anzahl von Dimensionen, um richtig zu arbeiten.

3 n

$3n$

n

$n$

Dan

Es hängt sehr davon ab, welche Informationen Sie über die Lösung wissen möchten. Über eine

Elektronenwellenfunktion will man kaum jedes Detail wissen . Man muss also die Rechentechnik auf die tatsächlich gewünschte Information zuschneiden.

n

$n$

Arnold Neumaier

Bitte geben Sie eine Referenz für die Monte-Carlo-Lösung einer elektronischen Schrödinger-Gleichung in 100 Dimensionen an.

Arnold Neumaier

Ich habe keine Referenz. Ich habe nur von Simulationen in so vielen Dimensionen gehört, die für QCD verwendet werden. Ich habe nur versucht, eine Schrödinger-Simulation in 4-5 Dimensionen durchzuführen, aber ich habe mich gefragt, ob etwas anderes als Monte Carlo mit der Anzahl der Dimensionen gut skaliert ist, und 100 schien eine schöne, große runde Zahl zu sein, um die asymptotische Skalierung zu erhalten.

Dan

Antworten:

Eine strukturiertere Art, eine Basis oder Quadratur (die in vielen Fällen MC ersetzen kann) in mehreren Dimensionen bereitzustellen , ist die von spärlichen Gittern , bei denen eine Familie eindimensionaler Regeln unterschiedlicher Ordnung so kombiniert wird, dass lediglich ein exponentielles Wachstum entsteht Dimension, , anstatt zu haben, dass Dimension ein Exponent der Auflösung . $2^d$ $N^d$

Dies geschieht durch eine sogenannte Smolyak-Quadratur, die eine Reihe eindimensionaler Regeln as kombiniert $Q^1_l$

$Q^d_n = \displaystyle\sum^{n}_{l}(Q^{1}_i - Q^{1}_{i-1})\otimes Q^{d-1}_{m-i+1}$

Dies entspricht dem Tensorprodukt-Quadraturraum, bei dem die hohen gemischten Ordnungen aus dem Raum entfernt wurden. Wenn dies streng genug durchgeführt wird, kann die Komplexität stark verbessert werden. Damit dies jedoch möglich ist und eine gute Approximation aufrechterhalten werden kann, muss die Regelmäßigkeit der Lösung ausreichend verschwundene gemischte Derivate aufweisen.

Für Dinge wie die Schrödinger-Gleichung im Konfigurationsraum und andere hochdimensionale Dinge wurden spärliche Gitter von der Griebel-Gruppe mit ziemlich guten Ergebnissen zu Tode geprügelt . In der Anwendung können die verwendeten Basisfunktionen ziemlich allgemein sein, solange Sie sie verschachteln können. Zum Beispiel sind ebene Wellen oder hierarchische Basen üblich.

Es ist auch ziemlich einfach, sich selbst zu kodieren. Aus meiner Erfahrung heraus ist es jedoch sehr schwierig, es tatsächlich für diese Probleme zum Laufen zu bringen. Ein gutes Tutorial existiert.

Für Probleme, deren Lösungen in speziellen Sobolev-Räumen mit schnell verendenden Derivaten auftreten, kann der Ansatz mit dünnem Gitter möglicherweise noch bessere Ergebnisse liefern .

Siehe auch Acta Numerica Review Paper, Sparse Tensor Discretizations von hochdimensionalen parametrischen und stochastischen PDEs .

Peter Brune
quelle

Gibt es bekannte Beispiele, bei denen spärliche Gitter nicht anwendbar sind?

MRocklin

Sie brauchen wirklich die Regelmäßigkeit zu halten. Auch wenn Sie böse hochdimensionale Höcker haben (wie in QM), müssen Sie vorsichtig sein. Ich hörte einige Geschichten über die Sparse Grid - Clique (mit Beweisen selbst) zuzugestehen beginnt , dass es nicht , dass viel besser als Monte-Carlo, kann aber nicht eine gute Referenz finden.

Peter Brune

Nun, das Papier über das spärliche Gitter für Schrödinger, von dem Sie sprachen, behandelt nur 2 Elektronen. Wie viele Elektronen können mit der Methode tatsächlich erfasst werden?

Arnold Neumaier

In der Regel ist es leicht zu verstehen, warum reguläre Gitter nicht viel mehr als drei- oder vierdimensionale Probleme können: Wenn Sie in d-Dimensionen ein Minimum von N Punkten pro Koordinatenrichtung haben möchten, erhalten Sie N ^ d Punkte insgesamt. Selbst für relativ nette Funktionen in 1d benötigen Sie mindestens N = 10 Rasterpunkte, um sie überhaupt aufzulösen, sodass die Gesamtpunktzahl 10 ^ d beträgt - dh selbst auf den größten Computern ist es unwahrscheinlich, dass Sie über d hinausgehen = 9, und wird wahrscheinlich nicht viel über das hinausgehen je . In einigen Fällen können spärliche Gitter helfen, wenn die Lösungsfunktion bestimmte Eigenschaften aufweist. Im Allgemeinen müssen Sie jedoch mit den Konsequenzen des Fluchs der Dimensionalität leben und sich für MCMC-Methoden entscheiden.

Wolfgang Bangerth
quelle

Wofür steht MCMC?

Dan

Markov-Kette Monte Carlo: de.wikipedia.org/wiki/Markov_chain_Monte_Carlo

Jack Poulson

$d=4,...,100$ $d=100,101,...\infty$

Paul
quelle

O (\sqrt{N})

$O(\sqrt{N})$

10^{7}

$10^7$

C^{k, α}

$C^{k,\alpha}$