Low-rank tensor structure of linear diffusion operators in the TT and QTT formats

Open access
Date
2012-05Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
We consider a class of multilevel matrices, which arise from the discretization of linear diffusion operators in a $d$-dimensional hypercube. Under certain assumptions on the structure of the diffusion tensor (motivated by financial models), we derive an explicit representation of such a matrix in the recently introduced Tensor Train (TT) format with the $TT$ ranks bounded from above by $2 + \lfloor \frac{d}{2}\rfloor$. We also show that if the diffusion tensor is constant and semiseparable of order $r < \lfloor \frac{d}{2}\rfloor$, the representation can be refined and the bound on the TT ranks can be sharpened to $2 + r$ (we do this in a more general setting, for non-constant diffusion tensors of a certain structure). As a result, when $n$ degrees of freedom are used in each dimension, such a matrix is represented in the $TT$ format through $ O (d^3 n^2)$ and $ O(dn^2 r^2)$ parameters resp. instead of its $n^{2d}$ entries. We also discuss the representation of such a matrix in the Quantized Tensor Train $(QTT)$ decomposition in terms of $O(d^3 \log n)$ and $O(dr^2 \log n)$,parameters resp. Furthermore, we show that the assumption of semiseparability of order $r$ can be relaxed to that of quasi-separability of order $r$. We establish the direct relation $r_k = s_k +2$ between the $d -1$ $TT$ ranks $s_k$ of the matrix in question and the matrix ranks $r_k$ of the $d-1$ leading off-diagonal submatrices of the diffusion tensor. Show more
Permanent link
https://doi.org/10.3929/ethz-a-010395841Publication status
publishedExternal links
Journal / series
SAM Research ReportVolume
Publisher
Seminar for Applied Mathematics, ETH ZurichSubject
Low-rank representation; Diffusion operator; Tensor Train (TT); Virtual levels; Quantized Tensor Train (QTT); Semiseparable matrices; Quasi-separable matricesOrganisational unit
03435 - Schwab, Christoph / Schwab, Christoph
Funding
247277 - Automated Urban Parking and Driving (EC)
Related publications and datasets
Is previous version of: http://hdl.handle.net/20.500.11850/65735
More
Show all metadata
ETH Bibliography
yes
Altmetrics