elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Performance of high-order SVD approximation: reading the data twice is enough

Röhrig-Zöllner, Melven and Thies, Jonas and Basermann, Achim (2021) Performance of high-order SVD approximation: reading the data twice is enough. In: SIAM Conference on Applied Linear Algebra. SIAM Conference on Applied Linear Algebra, 17.-21. Mai 2021, Online. (Unpublished)

[img] PDF
1MB

Abstract

Performance of high-order SVD approximation: reading the data twice is enough ============================================================================= This talk considers the problem of calculating a low-rank tensor approximation of some large dense data. We focus on the tensor train SVD (TT-SVD) but the approach can be transferred to other low-rank tensor formats such as general tree tensor networks. In the TT-SVD algorithm, the dominant building block consists of singular value decompositions of tall-skinny matrices. Therefore, the computational performance is bound by data transfers on current hardware as long as the desired tensor ranks are sufficiently small. Based on a simple roofline performance model we show that under reasonable assumptions the minimal runtime is of the order of reading the data twice. We present an almost optimal, distributed parallel implementation that is based on a specialized rank-preserving TSQR step. Moreover, we discuss important algorithmic details and compare our results with common implementations that are often about 50x slower than optimal. References: Oseledets: "Tensor-Train Decomposition", SISC 2011 Grasedyck and Hackbusch: "An Introduction to Hierarchical (H-) Rank and TT-Rank of Tensors with Examples", CMAM 2011 Demmel et. al.: "Communication Avoiding Rank Revealing QR Factorization with Column Pivoting", SIMAX 2015 Williams et. al.: "Roofline: An Insightful Visual Performance Model for Multicore Architectures", CACM 2009

Item URL in elib:https://elib.dlr.de/142361/
Document Type:Conference or Workshop Item (Speech)
Title:Performance of high-order SVD approximation: reading the data twice is enough
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Röhrig-Zöllner, MelvenMelven.Roehrig-Zoellner (at) dlr.dehttps://orcid.org/0000-0001-9851-5886
Thies, JonasJonas.Thies (at) dlr.deUNSPECIFIED
Basermann, AchimAchim.Basermann (at) dlr.dehttps://orcid.org/0000-0003-3637-3231
Date:20 May 2021
Journal or Publication Title:SIAM Conference on Applied Linear Algebra
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Status:Unpublished
Keywords:Tensor-Train Decomposition, high-dimensional data, High-Performance-Computing, tall-skinny QR
Event Title:SIAM Conference on Applied Linear Algebra
Event Location:Online
Event Type:international Conference
Event Dates:17.-21. Mai 2021
Organizer:Society for Industrial and Applied Mathematics (SIAM)
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Tasks SISTEC
Location: Köln-Porz
Institutes and Institutions:Institute for Software Technology > High-Performance Computing
Institute for Software Technology
Deposited By: Röhrig-Zöllner, Melven
Deposited On:14 Jun 2021 09:04
Last Modified:14 Jun 2021 09:04

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.