V moderní numerická algebře se stále častěji setkáváme s problémy,
kde potřebujeme pracovat s vícerozměrnými daty, uloženými jako tenzory.
Při manipulaci a výpočtech s tenzory velkých řádů snadno narazíme na omezení
na straně paměti počítače. Pokusíme-li se takový tenzor naivně uložit jako
prosté vícerozměrné pole, rychle může dojít k vyčerpání dostupné paměti,
které nelze jednoduše vyřešit použitím lepšího počítače. Tento jev je
ve výpočetním světě známý pod anglickým termínem "curse of dimensionality".
Jedním z nástrojů, které umožňují snížit paměťové nároky, je
Tuckerův rozklad tenzoru.
Úspora je ovšem omezena tzv. vektorovou hodností tenzoru a
pro tenzory vyšších řádů není dostatečná.
Cílem této práce je ukázat, že na tenzory, resp. sady tenzorů a jejich
různých vzájemných součinů lze nahlížet jako na specifické neorientované grafy.
Vysvětluje způsob reprezentace tenzorů a další objektů lineární
algebry pomocí těchto grafů.
Takový způsob reprezentace tenzorů označujeme jako tzv. tenzorové sítě.
V práci je dále ukázáno, jak lze tenzor (příliš velkého
řádu na to, aby s ním šlo pracovat přímo)
šikovně rozložit do tenzorové sítě se strukturou binárního stromu, jejíž uzly jsou tvořeny tenzory malých
řádů; konkrétně řádů tři a dva. Navíc počet těchto tenzorů malých řádů
závisí na řádu původního tenzoru lineárně. Tento přístup, tzv. hierarchický Tuckerův rozklad
(HTD, z anglického hierarchical Tucker deceomposition)
může vést k úspoře
paměťových a výpočetních nákladů při ukládání tenzoru, resp. při manipulaci
s tenzorem (násobení tenzoru maticí, lineární kombinace tenzorů) v počítači.
Práce také vysvětluje, jakým způsobem s tenzory uloženými ve tvaru HTD
provádět vybrané základní algebraické operace tak, aby výsledek byl opět tenzor
v podobě hierarchického Tuckerova rozkladu.
Anotace v angličtině
In modern numerical algebra, there quite frequently arise problems, where there is a need to
work with multidimensional data stored in the form of tensors.
While manipulating or calculating with tensors of high order, we often encounter the restricitions
by the memory of the computer. The attempt to store such a tensor can lead to the exhaustion
of the available memory, which can not be improved by the use of a better computer. This problem is
referred as the curse of dimensionality. One of the tools used for the reduction
of the storage requirements is the so-called Tucker decomposition. However, the storage savings by this
decomposition are restricted by the vector-rank of the given tensor and are not sufficient
for tensors of high order.
The aim of this thesis is to explain how tensors, or sets of tensors and tensor products can be interpreted
as specific (undirected) graphs. We explain the way of the representation of tensors and other objects from linear algebra.
Such representation is called the tensor network.
In the text we show the way to decompose the tensor (of order which is too high) into
the tensor network of the binary tree structure. The nodes of such a tree
represent tensors of order two or three.
Moreover, the number of these tensors of low order depends linearly on the order of the original tensor.
This approach, called hierarchical Tucker decomposition (HTD), can lead to storage requirements and
computation savings while storing or manipulating with the tensor, respectively.
The thesis also explains how to do some selected basic arithmetic operations so that the result
is also a tensor in HTD format.
Klíčová slova
multilineární algebra; tenzor; tenzrová síť; (hierarchický) Tuckerův rozklad (HTD); tensor train;
tensor chain; operace s tenzory; low-rank aproximace
V moderní numerická algebře se stále častěji setkáváme s problémy,
kde potřebujeme pracovat s vícerozměrnými daty, uloženými jako tenzory.
Při manipulaci a výpočtech s tenzory velkých řádů snadno narazíme na omezení
na straně paměti počítače. Pokusíme-li se takový tenzor naivně uložit jako
prosté vícerozměrné pole, rychle může dojít k vyčerpání dostupné paměti,
které nelze jednoduše vyřešit použitím lepšího počítače. Tento jev je
ve výpočetním světě známý pod anglickým termínem "curse of dimensionality".
Jedním z nástrojů, které umožňují snížit paměťové nároky, je
Tuckerův rozklad tenzoru.
Úspora je ovšem omezena tzv. vektorovou hodností tenzoru a
pro tenzory vyšších řádů není dostatečná.
Cílem této práce je ukázat, že na tenzory, resp. sady tenzorů a jejich
různých vzájemných součinů lze nahlížet jako na specifické neorientované grafy.
Vysvětluje způsob reprezentace tenzorů a další objektů lineární
algebry pomocí těchto grafů.
Takový způsob reprezentace tenzorů označujeme jako tzv. tenzorové sítě.
V práci je dále ukázáno, jak lze tenzor (příliš velkého
řádu na to, aby s ním šlo pracovat přímo)
šikovně rozložit do tenzorové sítě se strukturou binárního stromu, jejíž uzly jsou tvořeny tenzory malých
řádů; konkrétně řádů tři a dva. Navíc počet těchto tenzorů malých řádů
závisí na řádu původního tenzoru lineárně. Tento přístup, tzv. hierarchický Tuckerův rozklad
(HTD, z anglického hierarchical Tucker deceomposition)
může vést k úspoře
paměťových a výpočetních nákladů při ukládání tenzoru, resp. při manipulaci
s tenzorem (násobení tenzoru maticí, lineární kombinace tenzorů) v počítači.
Práce také vysvětluje, jakým způsobem s tenzory uloženými ve tvaru HTD
provádět vybrané základní algebraické operace tak, aby výsledek byl opět tenzor
v podobě hierarchického Tuckerova rozkladu.
Anotace v angličtině
In modern numerical algebra, there quite frequently arise problems, where there is a need to
work with multidimensional data stored in the form of tensors.
While manipulating or calculating with tensors of high order, we often encounter the restricitions
by the memory of the computer. The attempt to store such a tensor can lead to the exhaustion
of the available memory, which can not be improved by the use of a better computer. This problem is
referred as the curse of dimensionality. One of the tools used for the reduction
of the storage requirements is the so-called Tucker decomposition. However, the storage savings by this
decomposition are restricted by the vector-rank of the given tensor and are not sufficient
for tensors of high order.
The aim of this thesis is to explain how tensors, or sets of tensors and tensor products can be interpreted
as specific (undirected) graphs. We explain the way of the representation of tensors and other objects from linear algebra.
Such representation is called the tensor network.
In the text we show the way to decompose the tensor (of order which is too high) into
the tensor network of the binary tree structure. The nodes of such a tree
represent tensors of order two or three.
Moreover, the number of these tensors of low order depends linearly on the order of the original tensor.
This approach, called hierarchical Tucker decomposition (HTD), can lead to storage requirements and
computation savings while storing or manipulating with the tensor, respectively.
The thesis also explains how to do some selected basic arithmetic operations so that the result
is also a tensor in HTD format.
Klíčová slova
multilineární algebra; tenzor; tenzrová síť; (hierarchický) Tuckerův rozklad (HTD); tensor train;
tensor chain; operace s tenzory; low-rank aproximace
Při manipulaci a výpočtech s tenzory velkých řádů snadno narazíme na omezení na straně paměti počítače. Pokusíme-li se takový tenzor naivně uložit jako prosté vícerozměrné pole, rychle může dojít k vyčerpání dostupné paměti, které nelze jednoduše vyřešit použitím lepšího počítače. Tento jev je ve výpočetním světě známý pod anglickým termínem "curse of dimensionality".
Diplomová práce čtenáři ukáže, že na tenzory, resp. sady tenzorů a jejich různých vzájemných součinů lze jednoduše nahlížet jako na grafy, t. zv. tenzorové sítě. V práci bude dále ukázáno jak lze tenzor příliš velkého řádu na to, aby s ním šlo pracovat přímo, resp. jeho Tuckerovo jádro, šikovně rozložit do tenzorové sítě, jejíž uzly jsou tvořeny tenzory malých řádů. Tento přístup, t. zv. hierarchický Tuckerův rozklad povede k úspoře paměťových a výpočetních nákladů při ukládání tenzoru, resp. při manipulaci s tenzorem (násobení tenzoru maticí, lineární kombinace tenzorů) v počítači.
Požadavky: Základní znalosti z lineární algebry, základní znalost anglického jazyka. Práce by měla být psána tak, aby mohla celá, nebo její části, sloužit jako materiál pro úvod studia dané problematiky. Práce by měla být psaná v LaTeXu, bude-li to v možnostech studenta.
Zásady pro vypracování
Při manipulaci a výpočtech s tenzory velkých řádů snadno narazíme na omezení na straně paměti počítače. Pokusíme-li se takový tenzor naivně uložit jako prosté vícerozměrné pole, rychle může dojít k vyčerpání dostupné paměti, které nelze jednoduše vyřešit použitím lepšího počítače. Tento jev je ve výpočetním světě známý pod anglickým termínem "curse of dimensionality".
Diplomová práce čtenáři ukáže, že na tenzory, resp. sady tenzorů a jejich různých vzájemných součinů lze jednoduše nahlížet jako na grafy, t. zv. tenzorové sítě. V práci bude dále ukázáno jak lze tenzor příliš velkého řádu na to, aby s ním šlo pracovat přímo, resp. jeho Tuckerovo jádro, šikovně rozložit do tenzorové sítě, jejíž uzly jsou tvořeny tenzory malých řádů. Tento přístup, t. zv. hierarchický Tuckerův rozklad povede k úspoře paměťových a výpočetních nákladů při ukládání tenzoru, resp. při manipulaci s tenzorem (násobení tenzoru maticí, lineární kombinace tenzorů) v počítači.
Požadavky: Základní znalosti z lineární algebry, základní znalost anglického jazyka. Práce by měla být psána tak, aby mohla celá, nebo její části, sloužit jako materiál pro úvod studia dané problematiky. Práce by měla být psaná v LaTeXu, bude-li to v možnostech studenta.
Seznam doporučené literatury
T. G. Kolda, B. W. Bader: Tensor Decompositions and Applications.
SIAM Review,
Volume 51 (2009), Number 3, pp. 455--500.
L. Grasedyck: Hierarchical Singular Value Decomposition of Tensors.
SIAM Journal on Matrix Analysis and Applications,
Volume 31 (2010), Number 4, pp. 2029--2054.
I. V. Oseledets: Tensor-Train Decomposition.
SIAM Journal on Scientific Computing,
Volume 33 (2011), Number 5, pp. 2295--2317.
C. Tobler: Low-rank Tensor Methods for Linear Systems and Eigenvalue Problems.
PhD Tesis, Seminar for Applied Mathematics,
Department of Mathematics, ETH Zurich, 2012.
Seznam doporučené literatury
T. G. Kolda, B. W. Bader: Tensor Decompositions and Applications.
SIAM Review,
Volume 51 (2009), Number 3, pp. 455--500.
L. Grasedyck: Hierarchical Singular Value Decomposition of Tensors.
SIAM Journal on Matrix Analysis and Applications,
Volume 31 (2010), Number 4, pp. 2029--2054.
I. V. Oseledets: Tensor-Train Decomposition.
SIAM Journal on Scientific Computing,
Volume 33 (2011), Number 5, pp. 2295--2317.
C. Tobler: Low-rank Tensor Methods for Linear Systems and Eigenvalue Problems.
PhD Tesis, Seminar for Applied Mathematics,
Department of Mathematics, ETH Zurich, 2012.