Opened 14 months ago
Last modified 4 months ago
#31991 new enhancement
Meta-ticket: Efficient numerical computations with tensor trains — at Version 13
Reported by: | gh-honglizhaobob | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.7 |
Component: | linear algebra | Keywords: | |
Cc: | mkoeppe, egourgoulhon, dimpase | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Following the progress with Ticket #30307, we propose to add computational functionalities with tensors via the tensor train decomposition, which is an idea originally named "Density Matrix Renormalization Group (DMRG)" and later popularized by Prof. Ivan Oseledets.
This functionality is especially useful for high dimensional tasks to prevent the curse of dimensionality (such as in Riemannian optimization), currently supported in MATLAB, Python, and C++. The MATLAB version is currently most versatile and robust.
We may consider internalizing this computational library for Sage, as an effort to formalize the currently available implementations. This addition can either be an additional child class under tensor
, and overwrite the arithmetics; or a separate module. The backend is currently proposed to be TensorFlow?, however this may change / be flexible based on how the refactoring of Components
progresses.
One can look at this github page for an example implementation in MATLAB (https://github.com/oseledets/TT-Toolbox).
Ideally after the implementation of this ticket, users can specify a fixed rank tensor for a general manifold using tensor.modules
, specify a ring and a frame, and perform useful and normally computationally intractable tasks using tensor train as a backend. Based on the progress of this ticket, one may also consider implementing other backends for storing a numerical tensor such as tensor rings and quantized tensor train.
For alternative tensor decomposition formats, please see the following survey papers:
- Tucker format: (Falcó, Hackbusch, Nouy, Tree-based tensor formats, https://arxiv.org/abs/1810.01262)
- Tensor ring: (https://arxiv.org/abs/1807.02513)
- Quantized tensor train (see section 3.5.1): (https://refubium.fu-berlin.de/handle/fub188/3366)
For the theory behind why one can reduce a normally exponential (in the number of dimensions) task to a linear task, see Oseledets, Tensor-Train Decomposition, SIAM J. Sci. Comput., 33(5), 2295–2317 (https://epubs.siam.org/doi/abs/10.1137/090752286?journalCode=sjoce3).
Change History (13)
comment:1 Changed 14 months ago by
- Description modified (diff)
comment:2 Changed 14 months ago by
- Cc egourgoulhon added
comment:3 Changed 14 months ago by
- Cc egourgoulhon removed
- Description modified (diff)
comment:4 Changed 14 months ago by
- Cc egourgoulhon added
comment:5 Changed 14 months ago by
comment:6 follow-up: ↓ 7 Changed 14 months ago by
- Cc dimpase added
(This is with gfortran 11.1 on macOS; this may be similar to the many issues that we had when gfortran 10 came along - #29456)
comment:7 in reply to: ↑ 6 Changed 14 months ago by
Replying to mkoeppe:
(This is with gfortran 11.1 on macOS; this may be similar to the many issues that we had when gfortran 10 came along - #29456)
I didn't have an issue with downloading since I wasn't using pip but directly cloned the code on github. Based on their github's commit history it doesn't seem to be frequently maintained.. The MATLAB version is what I now use for my projects. I will update the MATLAB link in the ticket description.
comment:8 Changed 14 months ago by
- Description modified (diff)
comment:9 follow-up: ↓ 11 Changed 14 months ago by
Waouh! This looks promising!
comment:10 Changed 14 months ago by
I have opened an upstream issue for the compilation errors: https://github.com/oseledets/ttpy/issues/82
comment:11 in reply to: ↑ 9 Changed 14 months ago by
Replying to egourgoulhon:
Waouh! This looks promising!
To make it clear: the above comment was about the ticket main goal and was not some ironical statement about the ttpy issue with gfortran ;-)
comment:12 Changed 14 months ago by
- Description modified (diff)
comment:13 Changed 14 months ago by
- Description modified (diff)
- Summary changed from Efficient numerical computations with tensor trains to Meta-ticket: Efficient numerical computations with tensor trains
Is
ttpy
still being maintained? I tried to install it (usingsage -pip install ttpy
) and ran into a Fortran issue: