PDE w wielu wymiarach

Wiem, że większość metod znajdowania przybliżonych rozwiązań PDE skaluje się słabo wraz z liczbą wymiarów i że Monte Carlo jest używane w sytuacjach wymagających ~ 100 wymiarów.

Jakie są dobre metody skutecznego numerycznego rozwiązywania PDE w ~ 4-10 wymiarach? 10-100?

Czy są jakieś metody oprócz Monte Carlo, które dobrze skalują się z liczbą wymiarów?

pde monte-carlo high-dimensional

— Dan
źródło

Może pomóc podać nieco więcej informacji na temat rodzaju rozwiązywanego problemu. Większość PDE obsługiwanych w nauce obliczeniowej jest zazwyczaj maksymalnie czterowymiarowa (czas plus trzy wymiary przestrzenne). Czy zmienne są zmienne przestrzenne lub czasowe, czy też uwzględniacie inne zależności?

— aeismail

Zmienne przestrzenne. W mechanice kwantowej, jeśli nie chcesz, aby przybliżeń, które można używać w gęstości funkcjonalnej teorii lub Hartree-Focka, Funkcja falowa jest

wymiarowej, gdzie

jest liczbą elektronów. Dlatego nawet małe atomy i cząsteczki wymagają dużej liczby wymiarów, aby poprawnie się nimi posługiwać.

3 n

$3n$

n

$n$

— Dan

Wiele zależy od tego, jakie informacje chcesz wiedzieć o rozwiązaniu. Nie chce się znać każdego szczegółu na temat funkcji fali

elektronowej. Trzeba więc zastosować technikę obliczeniową do faktycznie pożądanej informacji.

n

$n$

— Arnold Neumaier

Przywołaj odniesienie do rozwiązania Monte Carlo elektronicznego równania Schroedingera w 100 wymiarach.

— Arnold Neumaier

Nie mam referencji Słyszałem tylko o symulacjach w tak wielu wymiarach używanych w QCD. Chcę tylko przeprowadzić symulację Schroingerera w 4-5 wymiarach, ale zastanawiałem się, czy oprócz monte carlo dobrze skalował się z liczbą wymiarów, a 100 wydawało się ładną, dużą okrągłą liczbą, aby uzyskać skalowanie asymptotyczne.

— Dan

Odpowiedzi:

Bardziej ustrukturyzowanym sposobem zapewnienia podstawy lub kwadratury (która może zastąpić MC w wielu przypadkach) w wielu wymiarach jest siatka rzadka , która łączy pewną rodzinę jednowymiarowych reguł o różnym porządku w taki sposób, aby uzyskać jedynie wykładniczy wzrost wymiar , zamiast być tak, że wymiar jest wykładnikiem rozdzielczości . $2^d$ $N^d$

Odbywa się to poprzez tak zwaną kwadraturę Smolyaka, która łączy szereg jednowymiarowych reguł jako $Q^1_l$

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

Jest to równoważne przestrzeni kwadratury produktu tensora z usuniętymi wysokimi rzędami mieszanymi . Jeśli zostanie to wykonane w wystarczająco poważny sposób, złożoność może zostać znacznie poprawiona. Jednak, aby ktoś mógł to zrobić i zachować dobre przybliżenie, regularność roztworu musi mieć wystarczająco zanikające mieszane pochodne.

Rzadkie siatki zostały pobite na śmierć przez grupę Griebel za takie rzeczy jak równanie Schrödingera w przestrzeni konfiguracyjnej i inne wysokowymiarowe rzeczy z całkiem dobrymi wynikami. W aplikacji używane funkcje podstawowe mogą być dość ogólne, o ile można je zagnieżdżać. Na przykład fale płaskie lub podstawy hierarchiczne są powszechne.

Kodowanie jest również dość proste. Z mojego doświadczenia wynika jednak, że przygotowanie go do rozwiązania tych problemów jest bardzo trudne. Istnieje dobry samouczek .

W przypadku problemów, których rozwiązania występują w wyspecjalizowanych przestrzeniach Sobolewa z pochodnymi, które szybko giną, podejście z rzadką siatką może potencjalnie przynieść jeszcze lepsze wyniki .

Zobacz także artykuł przeglądowy Acta Numerica, Rzadkie dyskretyzacje tensorów wysokowymiarowych parametrycznych i stochastycznych PDE .

— Peter Brune
źródło

Czy istnieją dobrze znane przykłady, w których rzadkie siatki nie mają zastosowania?

— MRocklin,

Naprawdę potrzebujesz regularności. Ponadto, jeśli masz paskudne, wysoko wymiarowe guzki (jak w QM), musisz być ostrożny. Słyszałem kilka opowieści o klice Sparse Grid, która zaczyna przyznawać się (nawet z dowodami), że nie jest tak dużo lepsza niż Monte-Carlo, ale nie może znaleźć dobrego odniesienia.

— Peter Brune,

Cóż, artykuł o rzadkiej siatce dla Schroingerera, o którym mówiłeś, dotyczy tylko 2 elektronów. Ile elektronów jest faktycznie podatnych na tę metodę?

— Arnold Neumaier

Zasadniczo łatwo jest zrozumieć, dlaczego zwykłe siatki nie mogą wykraczać daleko poza problemy 3 lub 4-wymiarowe: w wymiarach d, jeśli chcesz mieć co najmniej N punktów na kierunek współrzędnych, otrzymasz N ^ d punkty ogółem. Nawet dla stosunkowo fajnych funkcji na 1d potrzebujesz co najmniej N = 10 punktów siatki, aby je w ogóle rozwiązać, więc ogólna liczba punktów wyniesie 10 ^ d - tj. Nawet na największych komputerach raczej nie wykroczysz poza d = 9, i prawdopodobnie nie będzie pójść znacznie poza kiedykolwiek . Rzadkie siatki mogą w niektórych okolicznościach pomóc, jeśli funkcja rozwiązania ma pewne właściwości, ale ogólnie będziesz musiał żyć z konsekwencjami przekleństwa wymiarowości i stosować metody MCMC.

— Wolfgang Bangerth
źródło

Co oznacza skrót MCMC?

— Dan

Markov chain Monte Carlo: en.wikipedia.org/wiki/Markov_chain_Monte_Carlo

— Jack Poulson

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

— Paweł
źródło

O (\sqrt{N})

$O(\sqrt{N})$

10^{7}

$10^7$

C^{k, α}

$C^{k,\alpha}$