cuadrícula dispersa

Las mallas dispersas son técnicas numéricas para representar, integrar o interpolar funciones de alta dimensión . Fueron desarrolladas originalmente por el matemático ruso Sergey A. Smolyak , alumno de Lazar Lyusternik , y se basan en una construcción de producto tensorial disperso. Posteriormente, Michael Griebel , Christoph Zenger y Dirk Pflüger desarrollaron algoritmos informáticos para la implementación eficiente de dichas mallas .

La forma estándar de representar funciones multidimensionales son los tensores o las cuadrículas completas. El número de funciones base o nodos (puntos de la cuadrícula) que deben almacenarse y procesarse depende exponencialmente del número de dimensiones.

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

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

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

${\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 de${\displaystyle Q}$es el nivel de la discretización . Si una integración de 1 dimensión en el nivel${\displaystyle i}$se calcula mediante la evaluación de${\displaystyle O(2^{i})}$puntos, la estimación del error para una función de regularidad${\displaystyle r}$será ${\displaystyle |E_{l}|=O\left(N_{l}^{-r}\left(\log N_{l}\right)^{(d-1)(r+1)}\right)}$

• Pflüger, D.; Peherstorfer, B.; Bungartz, H. (2010). "Mallas dispersas espacialmente adaptativas para problemas de datos de alta dimensión". Journal of Complexity . 26 (5): 508– 522. doi : 10.1016/j.jco.2010.04.001 .
• Brumm, J.; Scheidegger, S. (2017). "Uso de cuadrículas dispersas adaptativas para resolver modelos dinámicos de alta dimensión" (PDF) . Econometrica . 85 (5): 1575– 1612. doi : 10.3982/ECTA12216 .
• Garcke, Jochen (2012). "Rejillas escasas en pocas palabras" (PDF) . En Garcke, Jochen; Griebel, Michael (eds.). Aplicaciones y redes dispersas . Saltador. págs. 57 a 80. ISBN  978-3-642-31702-6.
• Zenger, Christoph (1991). "Cuadrículas dispersas" (PDF) . En Hackbusch, Wolfgang (ed.). Algoritmos paralelos para ecuaciones diferenciales parciales . Vereg. págs. 241-251 . ISBN  3-528-07631-3.

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