Cuadrícula dispersa - Sparse grid

Las cuadrículas dispersas son técnicas numéricas para representar, integrar o interpolar funciones de alta dimensión . Fueron desarrollados originalmente por el matemático ruso Sergey A. Smolyak , un estudiante de Lazar Lyusternik , y se basan en una construcción de producto tensorial escasa. Más tarde, Michael Griebel y Christoph Zenger desarrollaron algoritmos informáticos para implementaciones eficientes de tales redes .

Maldición de dimensionalidad

La forma estándar de representar funciones multidimensionales es tensor o cuadrículas completas. El número de funciones básicas o nodos (puntos de la cuadrícula) que deben almacenarse y procesarse depende exponencialmente del número de dimensiones. Incluso con el poder computacional actual, no es posible procesar funciones con más de 4 o 5 dimensiones.

La maldición de la dimensionalidad se expresa en el orden del error de integración que se realiza por una cuadratura de nivel , con puntos. La función tiene regularidad , es decir, es diferenciable en el tiempo. El número de dimensiones es . ${\ Displaystyle l}$${\ Displaystyle N_ {l}}$${\ Displaystyle r}$${\ Displaystyle r}$${\ Displaystyle d}$

${\ Displaystyle | E_ {l} | = O (N_ {l} ^ {- {\ frac {r} {d}}})}$

Regla de cuadratura de Smolyak

Smolyak encontró un método computacionalmente más eficiente para integrar funciones multidimensionales basado en una regla de cuadratura univariante . La integral de Smolyak -dimensional de una función se puede escribir como una fórmula de recursión con el producto tensorial . ${\ Displaystyle Q ^ {(1)}}$${\ Displaystyle d}$${\ Displaystyle Q ^ {(d)}}$${\ Displaystyle f}$

${\ Displaystyle Q_ {l} ^ {(d)} f = \ left (\ sum _ {i = 1} ^ {l} \ left (Q_ {i} ^ {(1)} - Q_ {i-1} ^ {(1)} \ right) \ otimes Q_ {l-i + 1} ^ {(d-1)} \ right) f}$

El índice es el nivel de discretización. Una integración a nivel se calcula mediante la evaluación de puntos. La estimación del error para una función de regularidad es: ${\ displaystyle Q}$${\ Displaystyle 1-d}$${\ Displaystyle i}$${\ Displaystyle O (2 ^ {i})}$${\ Displaystyle r}$

${\ Displaystyle | E_ {l} | = O \ left (N_ {l} ^ {- r} \ left (\ log N_ {l} \ right) ^ {(d-1) (r + 1)} \ right )}$

Otras lecturas

• Brumm, J .; Scheidegger, S. (2017). "Uso de cuadrículas dispersas adaptativas para resolver modelos dinámicos de alta dimensión". Econometrica . 85 (5): 1575-1612. doi : 10.3982 / ECTA12216 .
• Garcke, Jochen (2012). "Cuadrículas dispersas en pocas palabras" (PDF) . En Garcke, Jochen; Griebel, Michael (eds.). Aplicaciones y rejillas dispersas . Saltador. págs. 57–80. ISBN 978-3-642-31702-6.
• Zenger, Christoph (1991). "Cuadrículas dispersas" (PDF) . En Hackbusch, Wolfgang (ed.). Algoritmos paralelos para ecuaciones diferenciales parciales . Vieweg. págs. 241-251. ISBN 3-528-07631-3.

enlaces externos

• Una estructura de datos de memoria eficiente para cuadrículas dispersas regulares
• Esquema de diferencias finitas en cuadrículas dispersas
• Visualización en cuadrículas dispersas
• Minería de datos en cuadrículas dispersas, J. Garcke, M. Griebel (pdf)

Este artículo relacionado con el análisis matemático es un fragmento . Puedes ayudar a Wikipedia expandiéndolo .

• v
• t
• mi