When high-dimensional
problems are concerned, not much algorithms can break the curse of
dimensionality, and solve them efficiently and reliably. Among those, tensor
product algorithms, which implement the idea of separation of variables for
multi-index arrays (tensors), seem to be the most general and also very
promising. They originated in quantum physics and chemistry and descent broadly
from the density matrix renormalization group (DMRG) and matrix
product states (MPS) formalisms. The same tensor formats were recently
re-discovered in the numerical linear algebra (NLA) community as the tensor
train (TT) format.
Algorithms developed in the quantum physics community are based on the
optimisation in tensor formats, that is performed subsequently for all
components of a tensor format (i.e. all sites or modes).
The DMRG/MPS schemes are very efficient but very difficult to analyse, and at
the moment only local convergence results for the simplest algorithm are
available. In the NLA community, a common approach is to use a classical
iterative scheme (e.g. GMRES) and enforce the compression to a tensor format at
every step. The formal analysis is quite straightforward, but tensor ranks of
the vectors which span the Krylov subspace grow rapidly with iterations, and
the methods are struggling in practice.
The first attempt to merge classical iterative algorithms and DMRG/MPS methods
was made by White (2005), where the second Krylov vector is used to expand the
search space on the optimisation step.
The idea proved to be useful, but the implementation was based on the fair
amount of physical intuition, and the algorithm is not completely justified.
We have recently proposed the AMEn algorithm for linear systems, that also
injects the gradient direction in the optimisation step, but in a way that
allows to prove the global convergence of the resulted scheme. The
scheme can be easily applied for the computation of the ground state --- the
differences to the algorithm of S. White are emphasized in Dolgov and
Savostyanov (2013).
The AMEn scheme is already acknowledged in the NLA community --- for example it
was recently applied for the computation of extreme eigenstates by Kressner,
Steinlechner and Uschmajew (2013), using the block-TT format proposed by in
Dolgov, Khoromskij, Oseledets and Savostyanov (2014).
At the moment, AMEn algorithm was applied
- to simulate the NMR spectra of large molecules (such as ubiquitin),
- to solve the Fokker-Planck equation for the non-Newtonian polymeric
flows,
- to the chemical master equation describing the mesoscopic model of gene
regulative networks,
- to solve the Heisenberg model problem for a periodic spin chain.
We aim to extend this framework and the analysis to other problems of NLA:
eigenproblems, time-dependent problems, high-dimensional interpolation, and
matrix functions; as well as to a wider list of high-dimensional
problems.
This is a joint work with Sergey Dolgov the from Max-Planck Institute for
Mathematics in the Sciences, Leipzig, Germany.
Seminar series
Date
Thu, 27 Feb 2014
Time
14:00 -
15:00
Location
Rutherford Appleton Laboratory, nr Didcot
Speaker
Dr Dmitry Savostyanov
Organisation
University of Southampton