Dmitry V. Savostyanov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Dmitry V. Savostyanov has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Sergey Dolgov
Department of Mathematical Sciences, University of Bath, Bath, UK
5 shared publications - Ivan Oseledets
Artificial Intelligence Research Institute (AIRI)
3 shared publications E. E. Tyrtyshnikov
Institute of Numerical Mathematics RAS, Gubkina 8, 119333 Moscow, Russia
2 shared publications- Eugene E. Tyrtyshnikov
Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russia
2 shared publications N. L. Zamarashkin
Institute of Numerical Mathematics of Russian Academy of Sciences Gubkina 8 119333 Moscow Russia
2 shared publications- Boris N. Khoromskij
Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany
1 shared publication
Latest Publications
- 31 October 2014
- Published by Springer Nature
- p. 335-343
Corrected One-Site Density Matrix Renormalization Group and Alternating Minimal Energy Algorithm
- 31 October 2014
- Published by Springer Nature
- p. 335-343
Corrected One-Site Density Matrix Renormalization Group and Alternating Minimal Energy Algorithm
- Open Access
One-site density matrix renormalization group and alternating minimum energy algorithm
Given in the title are two algorithms to compute the extreme eigenstate of a high-dimensional Hermitian matrix using the tensor train (TT) / matrix product states (MPS) representation. Both methods empower the traditional alternating direction scheme with the auxiliary (e.g. gradient) information, which substantially improves the convergence in many difficult cases. Being conceptually close, these methods have different derivation, implementation, theoretical and practical properties. We emphasize the differences, and reproduce the numerical example to compare the performance of two algorithms.
Open AccessOne-site density matrix renormalization group and alternating minimum energy algorithm
Given in the title are two algorithms to compute the extreme eigenstate of a high-dimensional Hermitian matrix using the tensor train (TT) / matrix product states (MPS) representation. Both methods empower the traditional alternating direction scheme with the auxiliary (e.g. gradient) information, which substantially improves the convergence in many difficult cases. Being conceptually close, these methods have different derivation, implementation, theoretical and practical properties. We emphasize the differences, and reproduce the numerical example to compare the performance of two algorithms.
- Open Access
On the decay of elements of inverse triangular Toeplitz matrix
We consider half-infinite triangular Toeplitz matrices with slow decay of the elements and prove under a monotonicity condition that elements of the inverse matrix, as well as elements of the fundamental matrix, decay to zero. We also provide a quantitative description of the decay of the fundamental matrix in terms of p-norms. Finally, we prove that for matrices with slow log-convex decay the inverse matrix has fast decay, i.e. is bounded. The results are compared with the classical results of Jaffard and Veccio and illustrated by numerical example.
Open AccessOn the decay of elements of inverse triangular Toeplitz matrix
We consider half-infinite triangular Toeplitz matrices with slow decay of the elements and prove under a monotonicity condition that elements of the inverse matrix, as well as elements of the fundamental matrix, decay to zero. We also provide a quantitative description of the decay of the fundamental matrix in terms of p-norms. Finally, we prove that for matrices with slow log-convex decay the inverse matrix has fast decay, i.e. is bounded. The results are compared with the classical results of Jaffard and Veccio and illustrated by numerical example.
- Open Access
Quasioptimality of maximum-volume cross interpolation of tensors
We consider a cross interpolation of high-dimensional arrays in the tensor train format. We prove that the maximum-volume choice of the interpolation sets provides the quasioptimal interpolation accuracy, that differs from the best possible accuracy by the factor which does not grow exponentially with dimension. For nested interpolation sets we prove the interpolation property and propose greedy cross interpolation algorithms. We justify the theoretical results and test the speed and accuracy of the proposed algorithm with convincing numerical experiments.
Open AccessQuasioptimality of maximum-volume cross interpolation of tensors
We consider a cross interpolation of high-dimensional arrays in the tensor train format. We prove that the maximum-volume choice of the interpolation sets provides the quasioptimal interpolation accuracy, that differs from the best possible accuracy by the factor which does not grow exponentially with dimension. For nested interpolation sets we prove the interpolation property and propose greedy cross interpolation algorithms. We justify the theoretical results and test the speed and accuracy of the proposed algorithm with convincing numerical experiments.
- Open Access
Computation of extreme eigenvalues in higher dimensions using block tensor train format
We consider an approximate computation of several minimal eigenpairs of large Hermitian matrices which come from high--dimensional problems. We use the tensor train format (TT) for vectors and matrices to overcome the curse of dimensionality and make storage and computational cost feasible. Applying a block version of the TT format to several vectors simultaneously, we compute the low--lying eigenstates of a system by minimization of a block Rayleigh quotient performed in an alternating fashion for all dimensions. For several numerical examples, we compare the proposed method with the deflation approach when the low--lying eigenstates are computed one-by-one, and also with the variational algorithms used in quantum physics.
Open AccessComputation of extreme eigenvalues in higher dimensions using block tensor train format
We consider an approximate computation of several minimal eigenpairs of large Hermitian matrices which come from high--dimensional problems. We use the tensor train format (TT) for vectors and matrices to overcome the curse of dimensionality and make storage and computational cost feasible. Applying a block version of the TT format to several vectors simultaneously, we compute the low--lying eigenstates of a system by minimization of a block Rayleigh quotient performed in an alternating fashion for all dimensions. For several numerical examples, we compare the proposed method with the deflation approach when the low--lying eigenstates are computed one-by-one, and also with the variational algorithms used in quantum physics.
- Open Access
Alternating minimal energy methods for linear systems in higher dimensions. Part II: Faster algorithm and application to nonsymmetric systems
In this paper we accomplish the development of the fast rank-adaptive solver for tensor-structured symmetric positive definite linear systems in higher dimensions. In [arXiv:1301.6068] this problem is approached by alternating minimization of the energy function, which we combine with steps of the basis expansion in accordance with the steepest descent algorithm. In this paper we combine the same steps in such a way that the resulted algorithm works with one or two neighboring cores at a time. The recurrent interpretation of the algorithm allows to prove the global convergence and to estimate the convergence rate. We also propose several strategies, both rigorous and heuristic, to compute new subspaces for the basis enrichment in a more efficient way. We test the algorithm on a number of high-dimensional problems, including the non-symmetrical Fokker-Planck and chemical master equations, for which the efficiency of the method is not fully supported by the theory. In all examples we observe a convincing fast convergence and high efficiency of the proposed method.
Open AccessAlternating minimal energy methods for linear systems in higher dimensions. Part II: Faster algorithm and application to nonsymmetric systems
In this paper we accomplish the development of the fast rank-adaptive solver for tensor-structured symmetric positive definite linear systems in higher dimensions. In [arXiv:1301.6068] this problem is approached by alternating minimization of the energy function, which we combine with steps of the basis expansion in accordance with the steepest descent algorithm. In this paper we combine the same steps in such a way that the resulted algorithm works with one or two neighboring cores at a time. The recurrent interpretation of the algorithm allows to prove the global convergence and to estimate the convergence rate. We also propose several strategies, both rigorous and heuristic, to compute new subspaces for the basis enrichment in a more efficient way. We test the algorithm on a number of high-dimensional problems, including the non-symmetrical Fokker-Planck and chemical master equations, for which the efficiency of the method is not fully supported by the theory. In all examples we observe a convincing fast convergence and high efficiency of the proposed method.
- Open Access
Alternating minimal energy methods for linear systems in higher dimensions. Part I: SPD systems
We introduce a family of numerical algorithms for the solution of linear system in higher dimensions with the matrix and right hand side given and the solution sought in the tensor train format. The proposed methods are rank--adaptive and follow the alternating directions framework, but in contrast to ALS methods, in each iteration a tensor subspace is enlarged by a set of vectors chosen similarly to the steepest descent algorithm. The convergence is analyzed in the presence of approximation errors and the geometrical convergence rate is estimated and related to the one of the steepest descent. The complexity of the presented algorithms is linear in the mode size and dimension and the convergence demonstrated in the numerical experiments is comparable to the one of the DMRG--type algorithm.
Open AccessAlternating minimal energy methods for linear systems in higher dimensions. Part I: SPD systems
We introduce a family of numerical algorithms for the solution of linear system in higher dimensions with the matrix and right hand side given and the solution sought in the tensor train format. The proposed methods are rank--adaptive and follow the alternating directions framework, but in contrast to ALS methods, in each iteration a tensor subspace is enlarged by a set of vectors chosen similarly to the steepest descent algorithm. The convergence is analyzed in the presence of approximation errors and the geometrical convergence rate is estimated and related to the one of the steepest descent. The complexity of the presented algorithms is linear in the mode size and dimension and the convergence demonstrated in the numerical experiments is comparable to the one of the DMRG--type algorithm.
- Open Access
Superfast solution of linear convolutional Volterra equations using QTT approximation
We address a linear fractional differential equation and develop effective solution methods using algorithms for inversion of triangular Toeplitz matrices and the recently proposed QTT format. The inverses of such matrices can be computed by the divide and conquer and modified Bini's algorithms, for which we present the versions with the QTT approximation. We also present an efficient formula for the shift of vectors given in QTT format, which is used in the divide and conquer algorithm. As the result, we reduce the complexity of inversion from the fast Fourier level $O(n\log n)$ to the speed of superfast Fourier transform, i.e., $O(\log^2 n).$ The results of the paper are illustrated by numerical examples.Open AccessSuperfast solution of linear convolutional Volterra equations using QTT approximation
We address a linear fractional differential equation and develop effective solution methods using algorithms for inversion of triangular Toeplitz matrices and the recently proposed QTT format. The inverses of such matrices can be computed by the divide and conquer and modified Bini's algorithms, for which we present the versions with the QTT approximation. We also present an efficient formula for the shift of vectors given in QTT format, which is used in the divide and conquer algorithm. As the result, we reduce the complexity of inversion from the fast Fourier level $O(n\log n)$ to the speed of superfast Fourier transform, i.e., $O(\log^2 n).$ The results of the paper are illustrated by numerical examples. - 30 May 2012
- Published by Springer Nature in Journal of Fourier Analysis and Applications
- Vol. 18 (5) , 915-953
Superfast Fourier Transform Using QTT Approximation
- 30 May 2012
- Published by Springer Nature in Journal of Fourier Analysis and Applications
- Vol. 18 (5) , 915-953
Superfast Fourier Transform Using QTT Approximation
- 1 February 2011
- Published by Wiley in Numerical Linear Algebra with Applications
- Vol. 19 (1) , 103-111
Fast truncation of mode ranks for bilinear tensor operations
SUMMARY: We propose a fast algorithm for mode rank truncation of the result of a bilinear operation on 3‐tensors given in the Tucker or canonical form. If the arguments and the result have mode sizes n and mode ranks r, the computation costs (nr3 + r4). The algorithm is based on the cross approximation of Gram matrices, and the accuracy of the resulted Tucker approximation is limited by square root of the machine precision. We apply the proposed algorithms for the evaluation of the Hadamard square of the electron density and demonstrate that it outperforms previously used methods for this purpose. We also check the accuracy of the resulted Tucker approximation and show that one iteration of the Tucker‐ALS method improves it almost up to the machine precision. Copyright © 2011 John Wiley & Sons, Ltd.
- 1 February 2011
- Published by Wiley in Numerical Linear Algebra with Applications
- Vol. 19 (1) , 103-111
Fast truncation of mode ranks for bilinear tensor operations
SUMMARY: We propose a fast algorithm for mode rank truncation of the result of a bilinear operation on 3‐tensors given in the Tucker or canonical form. If the arguments and the result have mode sizes n and mode ranks r, the computation costs (nr3 + r4). The algorithm is based on the cross approximation of Gram matrices, and the accuracy of the resulted Tucker approximation is limited by square root of the machine precision. We apply the proposed algorithms for the evaluation of the Hadamard square of the electron density and demonstrate that it outperforms previously used methods for this purpose. We also check the accuracy of the resulted Tucker approximation and show that one iteration of the Tucker‐ALS method improves it almost up to the machine precision. Copyright © 2011 John Wiley & Sons, Ltd.