Řídká mřížka - Sparse grid

Řídké mřížky jsou numerické techniky pro reprezentaci, integraci nebo interpolaci vysokých dimenzionální funkce. Byly původně vyvinuty ruština matematik Sergej A. Smolyak, student Lazar Lyusternik, a jsou založeny na řídké konstrukci tenzorového produktu. Počítačové algoritmy pro efektivní implementaci těchto sítí byly později vyvinuty Michael Griebel a Christoph Zenger.

Prokletí dimenzionality

Standardní způsob reprezentace vícerozměrných funkcí jsou tenzorové nebo plné mřížky. Počet základních funkcí nebo uzlů (bodů mřížky), které je třeba uložit a zpracovat závisí exponenciálně na počtu rozměrů. I při dnešním výpočetním výkonu není možné zpracovat funkce s více než 4 nebo 5 rozměry.

The prokletí dimenzionality je vyjádřeno v pořadí integrační chyby, která je provedena kvadraturou úrovně ${ displaystyle l}$, s ${ displaystyle N_ {l}}$ bodů. Funkce má pravidelnost ${ displaystyle r}$, tj. je ${ displaystyle r}$ krát diferencovatelné. Počet rozměrů je ${ displaystyle d}$.

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

Smolyakovo pravidlo kvadratury

Smolyak našel výpočetně efektivnější metodu integrace vícerozměrných funkcí založenou na jednorozměrném kvadraturním pravidle ${ displaystyle Q ^ {(1)}}$. The ${ displaystyle d}$-dimenzionální Smolyakův integrál ${ displaystyle Q ^ {(d)}}$ funkce ${ displaystyle f}$ lze psát jako rekurzní vzorec s tenzorový produkt.

${ displaystyle Q_ {l} ^ {(d)} f = left ( sum _ {i = 1} ^ {l} left (Q_ {i} ^ {(1)} - Q_ {i-1} ^ {(1)} vpravo) otimes Q_ {l-i + 1} ^ {(d-1)} vpravo) f}$

Index do ${ displaystyle Q}$ je úroveň diskretizace. A ${ displaystyle 1-d}$ integrace na úrovni ${ displaystyle i}$ se počítá z hodnocení ${ displaystyle O (2 ^ {i})}$ bodů. Odhad chyby pro funkci pravidelnosti ${ displaystyle r}$ je:

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

Reference

• Paměťově efektivní datová struktura pro běžné řídké mřížky
• Kód pro generování (a předem vygenerovaných) uzlů a vah pro kvadraturu
• Schéma konečných rozdílů na řídkých mřížkách
• Vizualizace na řídkých sítích
• Datamining na řídkých sítích, J.Garcke, M.Griebel (pdf)

• Jochen Garcke: „Řídké mřížky v kostce“ (pdf)
• Paul Constantine: „Zkušenosti s řídkými mřížkami a aproximacemi typu Smolyak“ (pdf)
• Christoph Zenger: "Sparse Grids" (pdf)
• Garcke, Jochen (ed.) A Griebel, Michael (ed.): „Sparse Grids and Applications“, Springer, ISBN  978-3-642-31702-6 (2013).
• J. Brumm a S. Scheidegger: „Použití adaptivních řídkých mřížek k řešení vysokodimenzionálních dynamických modelů“, (2013) (pdf)
• „Kvadratura na řídkých sítích“

Tento matematická analýza –Příbuzný článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.