Efficient Sketching-Based Summation of Tucker Tensors

Titel: Efficiënte schetsgebaseerde sommatie van Tucker-tensoren

Auteurs: R. Smith, M. Pasha, A. Galindo-Olarte, H. Al Daas, G. Ballard, J. Nakao, J. Qiu, W. Taitano.

---

1. Het Probleem

In wetenschappelijk rekenen, vooral bij het oplossen van hoog-dimensionale partiële differentiaalvergelijkingen (PDE's) en kinetische simulaties, worden tensoren gebruikt om data te representeren. Om de "vloek van de dimensionaliteit" te bestrijden, worden vaak lage-rang decomposities gebruikt, zoals de Tucker-decompositie.

Een fundamenteel probleem ontstaat bij het uitvoeren van sommatie (optellen) van tensoren in dit gecomprimeerde formaat:

• Rank-explosie: Wanneer $d$ tensoren worden opgeteld, wordt de rang van het resultaat in theorie de som van de individuele rangen ($d \times r$).
• Middelenprobleem: In iteratieve algoritmen (zoals GMRES voor lineaire systemen) moet deze sommatie herhaaldelijk plaatsvinden. Traditionele methoden vereisen het expliciet vormen van een enorme, dichtbevolkte tussenliggende kern (core tensor) met rang $d \times r$ voordat deze weer kan worden afgerond (getruncatiseerd) naar een acceptabele tolerantie.
• Geheugen- en rekentijd: Het vormen van deze tussenliggende structuren leidt tot een exponentiële toename in geheugengebruik en rekentijd, wat grote simulaties onuitvoerbaar maakt. Bestaande methoden die vaak afronden na elke stap ("eager rounding") kunnen leiden tot onomkeerbare verlies van nauwkeurigheid door dynamische bereikverschuivingen.

2. Methodologie

De auteurs stellen een randomized sketching-framework voor dat sommatie en afronding combineert zonder de tussenliggende hoge-rang tensor expliciet te vormen. De kern van de methode ligt in het benutten van de algebraïsche structuur van Khatri-Rao-producten (KRP) en Kronecker-producten.

Belangrijkste stappen in het algoritme:

1. Structuurbehoudende Schetsing: In plaats van de volledige tensoren op te tellen, worden willekeurige projectiematrices (sketches) direct toegepast op de factor matrices van de individuele sommanden.
   • Er worden twee benaderingen gebruikt:
     • Kronecker Sketching: Gebruikt het Kronecker-product van willekeurige matrices.
     • Khatri-Rao Sketching (KRP): Gebruikt het Khatri-Rao-product, wat vaak efficiënter is bij het hergebruiken van factoren.
2. Implicit Sommatie: De schetsoperatoren worden toegepast op de factor matrices voordat de producten worden gevormd. Dit resulteert in een lage-dimensionale "surrogaat" van de som, waarbij de grote kern nooit wordt gegenereerd.
3. Effectieve Rang Schatting: Om de grootte van de schets (de doelrang) te bepalen zonder de volledige som te berekenen, gebruiken de auteurs een heuristiek gebaseerd op de spectrale verval van een energie-gewogen Gram-matrix van de samengevoegde factor matrices. Dit bepaalt hoeveel rang er daadwerkelijk nodig is om de energie van de som te behouden.
4. Sequential Truncated HOSVD (ST-HOSVD): Na het schetsen en het vinden van een nieuwe orthonormale basis, wordt de kern geprojecteerd en uiteindelijk afgerond via ST-HOSVD om een compacte Tucker-decompositie te verkrijgen die voldoet aan de gebruikerstolerantie.

3. Belangrijkste Bijdragen

• Nieuw Sommatie-algoritme: Een algoritme dat sommatie uitvoert binnen de gecomprimeerde Tucker-representatie, waardoor het expliciet vormen van grote tussenliggende tensoren wordt voorkomen.
• Gebruik van Structuur: Het benutten van de specifieke eigenschappen van Khatri-Rao en Kronecker-producten om schetsoperatoren efficiënt toe te passen op factor matrices in plaats van op de volledige tensor.
• Rang-schatting Heuristiek: Een nieuwe methode om de effectieve rang te schatten vóór het schetsen, wat zorgt voor een robuuste keuze van de schetsdimensies en voorkomt dat er te weinig of te veel wordt geschaald.
• Complexiteitsanalyse: Een theoretische analyse die aantoont dat de deterministische methode een complexiteit heeft van $O(d^{N+1})$ (waarbij $d$ het aantal sommanden en $N$ de orde van de tensor is), terwijl de geschatte methode lineair schaalt met $d$ ($O(d)$), wat een enorme winst oplevert voor grote $d$.

4. Resultaten

De methode is getest op vier scenario's:

1. Synthetische Testcases:
   • De schetsmethodes (zowel Kronecker als KRP) tonen een lineaire schaling in rekentijd met het aantal sommanden, terwijl de deterministische methode exponentieel vertraagt.
   • De nauwkeurigheid blijft machineprecisie ($\sim 10^{-15}$) behouden ten opzichte van de deterministische baseline.
   • Vermijden van "Eager Rounding": Een test met tegenwerkende ruis toonde aan dat traditionele methoden die na elke stap afronden, de ware signaalcomponenten kunnen vernietigen door tijdelijke norm-inflatie. De schetsmethode behoudt de nauwkeurigheid perfect.
2. Parametrische PDE ("Cookie Problem"):
   • Een stationaire warmtevergelijking met geometrische inbeddingen.
   • De KRPSum-Tucker methode (Khatri-Rao) boekte tot 11x snelheidswinst ten opzichte van de standaard afronding, met relatieve fouten rond $10^{-5}$.
   • De Kronecker-methode presteerde minder goed bij sterk scheefgetrokken modi (ruimtelijke dimensie veel groter dan parameterdimensie), wat de noodzaak benadrukt van de juiste heuristiek voor schetsdimensies.
3. Lineair Transportprobleem (NDG):
   • Een 1D lineair behoudswet opgelost met de Nodal Discontinuous Galerkin (NDG) methode.
   • De schetsmethodes leverden snelheidswinsten op van 5x tot 30x naarmate de orde van de basis of de resolutie van het parameterrooster toenam.
   • De fouten waren ononderscheidbaar van de deterministische methode, maar met aanzienlijk minder rekentijd.

5. Betekenis en Conclusie

Dit werk biedt een oplossing voor een van de grootste knelpunten in high-performance computing met tensoren: het optellen van gecomprimeerde data zonder de compressie te verliezen.

• Efficiëntie: Het elimineert de "rank-explosie" die traditionele methoden beperkt, waardoor iteratieve methoden (zoals GMRES) en tijdsstap-methoden veel schaalbaarder worden.
• Nauwkeurigheid: Het voorkomt de numerieke valkuilen van vroegtijdige afronding (zoals het verliezen van kleine signalen door grote ruis).
• Toepassingsgebied: De methode is cruciaal voor toepassingen zoals parametrische PDE's, kinetische theorie (neutronenvervoer, plasma) en andere domeinen waar herhaalde tensor-sommatie voorkomt.

De auteurs concluderen dat deze randomised sketching-technieken een fundamentele doorbraak zijn die het mogelijk maakt om hoog-dimensionale simulaties uit te voeren die eerder onuitvoerbaar waren vanwege geheugen- en rekentijdbeperkingen.