PDE en muchas dimensiones

Sé que la mayoría de los métodos para encontrar soluciones aproximadas a PDEs escalan mal con el número de dimensiones, y que Monte Carlo se usa para situaciones que requieren ~ 100 dimensiones.

¿Cuáles son buenos métodos para resolver eficientemente los PDE numéricos en ~ 4-10 dimensiones? 10-100?

¿Hay algún método además de Monte Carlo que se adapte bien al número de dimensiones?

pde monte-carlo high-dimensional Dan
fuente

Puede ser útil proporcionar un poco más de información sobre el tipo de problema que está resolviendo. La mayoría de los PDE manejados en ciencia computacional tienden a ser a lo sumo de cuatro dimensiones (tiempo más tres dimensiones espaciales). ¿Las variables son espaciales o variables de tiempo, o hay otras dependencias que está incluyendo?

aeismail

Variables espaciales. En la mecánica cuántica, si usted no quiere hacer las aproximaciones que se utiliza en la teoría funcional de la densidad o de Hartree-Fock, la función de onda es

dimensional, donde

es el número de electrones. Entonces, incluso los átomos y moléculas pequeños requieren una gran cantidad de dimensiones para manejarse correctamente.

3 n

$3n$

n

$n$

Dan

Depende mucho de la información que desee conocer sobre la solución. Difícilmente se quiere conocer cada detalle sobre una función de onda de electrones

. Entonces uno debe adaptar la técnica computacional a la información realmente deseada.

n

$n$

Arnold Neumaier

Cite una referencia para la solución Monte Carlo de una ecuación electrónica de Schroedinger en 100 dimensiones.

Arnold Neumaier

No tengo una referencia Solo he oído hablar de simulaciones en que muchas dimensiones se utilizan para QCD. Solo estoy buscando hacer una simulación de Schroedinger en 4-5 dimensiones, pero me preguntaba si algo además de monte carlo se ajustaba bien con el número de dimensiones, y 100 parecía un número redondo grande y agradable para obtener el escalado asintótico.

Dan

Respuestas:

Una forma más estructurada de proporcionar una base o una cuadratura (que puede reemplazar a MC en muchos casos) en múltiples dimensiones es la de cuadrículas dispersas , que combina alguna familia de reglas unidimensionales de orden variable de tal manera que tengan un crecimiento meramente exponencial en dimensión, , en lugar de tener que ser esa dimensión es un exponente de la resolución $2^d$ . $N^d$

Esto se hace a través de lo que se conoce como una cuadratura de Smolyak, que combina una serie de reglas unidimensionales $Q^1_l$ como

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

Esto es equivalente al espacio de cuadratura del producto tensorial con los altos órdenes mixtos eliminados del espacio. Si esto se hace de una manera lo suficientemente severa, la complejidad puede mejorar enormemente. Sin embargo, para que uno pueda hacer esto y mantener una buena aproximación, la regularidad de la solución debe tener derivados mixtos que desaparezcan lo suficiente.

Las redes dispersas han sido golpeadas hasta la muerte por el grupo Griebel por cosas como el ecuación de Schrödinger en el espacio de configuración y otras cosas de alta dimensión con muy buenos resultados. En la aplicación, las funciones básicas utilizadas pueden ser bastante generales, siempre que pueda anidarlas. Por ejemplo, las ondas planas o las bases jerárquicas son comunes.

También es bastante simple codificarse usted mismo. Desde mi experiencia, sin embargo, hacer que funcione para estos problemas es muy difícil. Existe un buen tutorial .

Para los problemas cuyas soluciones viven en espacios especializados de Sobolev con derivados que mueren rápidamente, el enfoque de cuadrícula dispersa puede generar resultados aún mayores .

Ver también el artículo de revisión Acta Numerica, Discretizaciones de tensor disperso de PDE paramétricas y estocásticas de alta dimensión .

Peter Brune
fuente

¿Existen ejemplos bien conocidos en los que las cuadrículas dispersas no son aplicables?

MRocklin

Realmente necesitas la regularidad para aguantar. Además, si tiene cúspides desagradables de alta dimensión (como en QM), debe tener cuidado. He oído algunas historias sobre la camarilla Escaso parrilla de salida que reconocer (con las pruebas incluso) que no es que mucho mejor que la de Monte-Carlo, pero no puedo encontrar una referencia buena.

Peter Brune

Bueno, el documento sobre la cuadrícula dispersa para el schroedinger al que te refieres solo trata 2 electrones. ¿Cuántos electrones son realmente manejables por el método?

Arnold Neumaier

Como regla general, es fácil entender por qué las cuadrículas regulares no pueden ir más allá de los problemas de 3 o 4 dimensiones: en d dimensiones, si desea tener un mínimo de N puntos por dirección de coordenadas, obtendrá N ^ d puntos en general. Incluso para funciones relativamente agradables en 1d, necesita al menos N = 10 puntos de cuadrícula para resolverlos, por lo que el número total de puntos será 10 ^ d, es decir, incluso en las computadoras más grandes es poco probable que vaya más allá de d = 9, y probablemente no irá mucho más allá que nunca . Las cuadrículas dispersas pueden ayudar en algunas circunstancias si la función de solución tiene ciertas propiedades, pero en general, tendrá que vivir con las consecuencias de la maldición de la dimensionalidad e ir con los métodos MCMC.

Wolfgang Bangerth
fuente

¿Qué significa MCMC?

Dan

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

Jack Poulson

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

Paul
fuente

Sin embargo, esa no es una declaración muy útil. Por supuesto, la tasa de convergencia es

O (\sqrt{N})

$O(\sqrt{N})$ independiente de la dimensión. Pero la constante frente a ella depende de la dimensión y de maneras muy desagradables. Puede aproximar fácilmente una integral en 3d utilizando 100 puntos de muestra para obtener funciones razonablemente suaves. No puedes hacer lo mismo con

10^{7}

$10^7$ puntos si estás en 100 dimensiones!

Wolfgang Bangerth

Bueno, esto depende de la suavidad. Si todo lo que tienes es un límite finito de Hölder

C^{k, α}

$C^{k,\alpha}$ , entonces se permiten funciones con derivados mixtos ricos y no se puede superar la maldición de la dimensionalidad. Solo podemos hacerlo mejor si los derivados mixtos decaen lo suficientemente rápido, o si existe alguna otra regularidad explotable.

Jed Brown