Cuadrícula dispersa

Las cuadrículas 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 la construcción de un producto tensorial disperso. Michael Griebel y Christoph Zenger desarrollaron posteriormente algoritmos informáticos para implementaciones eficientes de dichas cuadrículas .

La maldición de la dimensionalidad

La forma estándar de representar funciones multidimensionales son las cuadrículas tensoriales o completas. La cantidad de funciones base o nodos (puntos de cuadrícula) que deben almacenarse y procesarse depende exponencialmente de la cantidad de dimensiones.

La maldición de la dimensionalidad se expresa en el orden del error de integración que se comete por una cuadratura de nivel , con puntos. La función tiene regularidad , es decir es veces diferenciable. 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. Si se calcula una integración unidimensional en el nivel mediante la evaluación de puntos, la estimación del error para una función de regularidad será ${\displaystyle Q}$ ${\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)}$

Lectura adicional

• 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–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.

Enlaces externos

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