PDE dalam Banyak Dimensi

Saya tahu bahwa sebagian besar metode untuk menemukan solusi perkiraan untuk skala PDE buruk dengan jumlah dimensi, dan bahwa Monte Carlo digunakan untuk situasi yang membutuhkan ~ 100 dimensi.

Apa metode yang baik untuk memecahkan PDE secara numerik secara efisien dalam ~ 4-10 dimensi? 10-100?

Apakah ada metode selain Monte Carlo yang skala dengan jumlah dimensi?

pde monte-carlo high-dimensional Dan
sumber

Mungkin membantu untuk memberikan sedikit lebih banyak informasi tentang jenis masalah yang Anda selesaikan. Sebagian besar PDE yang ditangani dalam ilmu komputasi cenderung paling banyak empat dimensi (waktu ditambah tiga dimensi spasial). Apakah variabelnya variabel spasial atau waktu, atau adakah dependensi lain yang Anda masukkan?

aeismail

Variabel spasial. Dalam mekanika kuantum jika Anda tidak ingin membuat perkiraan yang Anda gunakan dalam teori fungsional kerapatan atau Hartree-Fock, fungsi gelombang adalah

dimensi, di mana

adalah jumlah elektron. Jadi, bahkan atom dan molekul kecil pun membutuhkan sejumlah besar dimensi untuk menangani dengan benar.

3 n

$3n$

n

$n$

Dan

Itu sangat tergantung pada informasi apa yang ingin Anda ketahui tentang solusinya. Seseorang hampir tidak ingin mengetahui setiap detail tentang fungsi gelombang

elektron. Jadi kita harus menggunakan teknik komputasi untuk informasi yang sebenarnya diinginkan.

n

$n$

Arnold Neumaier

Tolong kutip referensi untuk solusi Monte Carlo dari persamaan Schroedinger elektronik dalam 100 dimensi.

Arnold Neumaier

Saya tidak punya referensi. Saya hanya mendengar simulasi dalam banyak dimensi yang digunakan untuk QCD. Saya hanya ingin melakukan simulasi Schroedinger dalam 4-5 dimensi, tetapi saya bertanya-tanya apakah sesuatu selain monte carlo diskalakan dengan baik dengan jumlah dimensi, dan 100 tampak seperti angka bulat yang bagus untuk mendapatkan skala asimptotik.

Dan

Jawaban:

Cara yang lebih terstruktur untuk menyediakan basis atau quadrature (yang dapat menggantikan MC dalam banyak kasus) dalam berbagai dimensi adalah dengan grid yang jarang , yang menggabungkan beberapa keluarga aturan satu dimensi dari urutan yang berbeda-beda sedemikian rupa sehingga hanya memiliki pertumbuhan eksponensial dalam Dimensi, , daripada memilikinya dimensi itu adalah eksponen dari resolusi . $2^d$ $N^d$

Ini dilakukan melalui apa yang dikenal sebagai quadrature Smolyak, yang menggabungkan serangkaian aturan satu dimensi sebagai $Q^1_l$

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

Ini setara dengan ruang quadrature produk tensor dengan pesanan campuran tinggi dihapus dari ruang. Jika ini dilakukan dengan cara yang cukup parah, kompleksitasnya dapat meningkat pesat. Namun, agar seseorang dapat melakukan ini dan mempertahankan perkiraan yang baik, keteraturan dari solusi harus memiliki turunan campuran yang hilang secara memadai.

Jarang grid telah dipukuli sampai mati oleh kelompok Griebel untuk hal-hal seperti persamaan Schrödinger di ruang konfigurasi dan hal-hal dimensi tinggi lainnya dengan hasil yang cukup bagus. Dalam aplikasi, fungsi dasar yang digunakan mungkin cukup umum, selama Anda dapat membuatnya. Sebagai contoh, gelombang bidang atau pangkalan hierarkis adalah umum.

Cukup mudah untuk membuat kode sendiri. Dari pengalaman saya, benar-benar membuatnya bekerja untuk masalah ini, bagaimanapun, sangat sulit. Ada tutorial yang bagus .

Untuk masalah yang solusinya tinggal di ruang Sobolev khusus yang menampilkan turunan yang cepat mati, pendekatan grid jarang berpotensi menghasilkan hasil yang lebih besar .

Lihat juga kertas ulasan Acta Numerica, diskretisasi tensor Jarang parametrik tinggi dan stokastik PDE .

Peter Brune
sumber

Apakah ada contoh terkenal di mana grid jarang tidak berlaku?

MRocklin

Anda benar-benar membutuhkan keteraturan untuk bertahan. Juga, jika Anda memiliki cusps dimensi tinggi yang tidak menyenangkan (seperti pada QM), Anda harus berhati-hati. Saya mendengar beberapa cerita tentang clique Jarang Grid mulai mengakui (dengan bukti bahkan) bahwa tidak yang jauh lebih baik daripada Monte-Carlo, tetapi tidak dapat menemukan referensi yang baik.

Peter Brune

Nah, Makalah tentang grid tipis untuk schroedinger yang Anda sebut hanya memperlakukan 2 elektron. Berapa banyak elektron yang sebenarnya dapat ditelusuri dengan metode ini?

Arnold Neumaier

Sebagai aturan umum, mudah untuk memahami mengapa kisi-kisi biasa tidak bisa melampaui masalah 3 atau 4 dimensi: dalam dimensi d, jika Anda ingin memiliki minimum N poin per arah koordinat, Anda akan mendapatkan N ^ d poin keseluruhan. Bahkan untuk fungsi yang relatif bagus dalam 1d, Anda memerlukan setidaknya N = 10 titik grid untuk menyelesaikannya sama sekali, sehingga jumlah keseluruhan poin akan 10 ^ d - yaitu bahkan pada komputer terbesar Anda tidak mungkin melampaui d = 9, dan mungkin tidak akan jauh melebihi sebelumnya . Grid jarang dapat membantu dalam beberapa keadaan jika fungsi solusi memiliki sifat-sifat tertentu, tetapi secara umum, Anda harus hidup dengan konsekuensi dari kutukan dimensi dan pergi dengan metode MCMC.

Wolfgang Bangerth
sumber

Untuk apa MCMC berdiri?

Dan

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

Jack Poulson

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

Paul
sumber

O (\sqrt{N})

$O(\sqrt{N})$

10^{7}

$10^7$

C^{k, α}

$C^{k,\alpha}$