Masterproef T701 : Efficiënte blokgebaseerde multilineaire matrix-tensorvermenigvuldiging

Informatie:	Nick Van Nieuwenhoven	Karl Meerbergen
Promotoren:	Karl Meerbergen	Raf Randebril
Begeleider:	Nick Van Nieuwenhoven

Numerieke Approximatie en Lineaire Algebra Groep

Meerdimensionale data komt op natuurlijke wijze voor in een aantal toepassingsdomeinen, zoals psychometrie (factoranalyse), chemometrie (spectrometrie), data mining en patroonherkenning. Om de data afkomstig van deze toepassingen te analyseren, zijn compressietechnieken onmisbaar. Voor tweedimensionale data is de singuliere waardenontbinding hiervoor een geschikte kandidaat. De overeenkomstige techniek voor meerdimensionale data is de hogere-orde singuliere waardenontbinding (HOSVD). Om deze ontbinding te berekenen bestaan er verschillende algoritmen waarin multilineaire matrix-tensorvermenigvuldigingen frequent berekend moeten worden. Zo'n vermenigvuldiging wordt hieronder schematisch weergegeven. Een tensor met dimensies n₁xn₂xn₃ wordt er vermenigvuldigd met drie matrices van dimensies r₁xn1, r₂xn₂ en r₃xn₃, respectievelijk, om zo een nieuwe tensor van dimensie r₁xr₂xr₃ te bekomen.

Het efficiënt implementeren van het multilineaire matrix-tensor product door middel van het efficiënt uitbuiten van een blokstructuur. Daarnaast moet ook de volgorde waarin de matrixvermenigvuldigingen worden uitgevoerd, geoptimaliseerd worden.

De focus ligt op het implementeren van enkele mogelijke strategieën om het algoritme op een blokgebaseerde manier uit te voeren. De verschillende technieken worden met elkaar vergeleken en theoretisch geanalyseerd. De student vergelijkt de prestaties met enkele klassieke implementaties van dit algoritme en verklaart de behaalde versnellingsfactor. Indien hiervoor interesse bestaat, kan dit algoritme ook geparallelliseerd worden voor multicore machines.

Relevante Literatuur:

• Van Balen, N. Multithreading voor tensorontbindingen (Masterproef) KU Leuven, 2012
• T.G. Kolda and B.W. Bader, Tensor decompositions and applications
• L. De Lathauwer, B. De Moor, and J. Vandewalle, A Multilinear Singular Value Decomposition

Daar er tot heden weinig onderzoek verricht werd naar zulke performante algoritmen is dit eindwerk eerder praktisch van aard; er is weinig relevante literatuur om te bestuderen. De student is geïnteresseerd in het optimaliseren van de prestaties van algoritmen en is in staat om efficiënte code te produceren in C++.

Deze masterproef is voor 1 student.