Parallel algorithms for tensor arithmetic in low-rank formats and applications

  • Parallele Algorithmen für Tensorarithmetik in Niedrigrangformaten und Anwendungen

Löbbert, Christian; Grasedyck, Lars (Thesis advisor); Börm, Steffen (Thesis advisor)

Aachen (2019)
Doktorarbeit

Dissertation, RWTH Aachen University, 2019

Kurzfassung

Ziel dieser Arbeit ist die Entwicklung paralleler Algorithmen für Tensorarithmetik (wie z.B. Skalarprodukte, Tensorkürzungen oder Hadamardprodukte) im Hierarchischen Tuckerformat (HT-Format), welches ein Niedrigrangformat für Tensoren ist, das auf einer Hierarchie der Tensorrichtungen gemäß eines binären Baumes basiert. Dazu wird zunächst eine Einführung zu Tensoren und verschiedenen Tensorformaten gegeben und erläutert, weshalb das HT-Format für unsere Zwecke besonders geeignet ist. In sequentieller Implementierung hat die in dieser Arbeit behandelte Tensorarithmetik eine Komplexität, welche linear mit der Tensorordnung d wächst. Bei geeigneter Wahl des zugrundeliegenden binären Baumes lässt sich diese Komplexität mittels Parallelisierung auf O(log(d)) reduzieren. Dies belegen Laufzeittests, welche für die implementierten Algorithmen durchgeführt wurden. Die Algorithmen wurden in C++ unter Verwendung des MPI Standards für die Parallelisierung und der blaze-lib für Matrixarithmetik geschrieben. Insbesondere unterstützen die im Rahmen dieser Arbeit entwickelten Algorithmen die verteilte Speicherung eines Tensors im HT-Format auf mehreren Computerknoten. Eine Veröffentlichung der Algorithmen ist geplant. Am Ende der Arbeit wird eine Anwendung der parallelen Tensorarithmetik präsentiert: Zusammen mit Lukas Juschka wurden Algorithmen entwickelt, mithilfe derer die Maximumnorm eines Niedrigrangtensors approximiert werden kann und ein entsprechender Tensorindex gefunden werden kann, welcher den Absolutbetrag maximiert. Die Approximation der Maximumnorm basiert auf einer Vektoriteration, welche die Berechnung von Skalarprodukten und Hadamardprodukten beinhaltet, und somit im HT-Format die O(d)-Komplexität der Tensorarithmetik erbt. Die in dieser Arbeit entwickelte parallele Implementierung führt zu einer Reduzierung der Komplexität auf O(log(d)). Das Finden eines entsprechenden maximierenden Tensorindex geschieht über eine binäre Suche, welche selbst O(d) Anwendungen der Maximumnormapproximation benötigt. Dies führt in sequentieller Implementierung zu einer O(d²)-Komplexität, welche mithilfe der parallelen Tensorarithmetik auf O(d*log(d)), also quasilineare Komplexität, reduziert werden kann.

Identifikationsnummern

Downloads