DSDmitry V. Savostyanov

Dmitry V. Savostyanov

*This is an algorithmically generated author record based on publicly available information.

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


Dmitry V. Savostyanov has a total of 13 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    One-site density matrix renormalization group and alternating minimum energy algorithm

    by Sergey V. Dolgov, Dmitry V. Savostyanov

    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

    by Neville Ford, D. V. Savostyanov, N. L. Zamarashkin

    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

    by Dmitry V. Savostyanov

    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

    by Sergey V. Dolgov, Boris N. Khoromskij, Ivan V. Oseledets, Dmitry V. Savostyanov

    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

    by Sergey V. Dolgov, Dmitry V. Savostyanov

    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

    by Sergey V. Dolgov, Dmitry V. Savostyanov

    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

    by Jason A. Roberts, Dmitry V. Savostyanov, Eugene E. Tyrtyshnikov

    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.


  • Fast truncation of mode ranks for bilinear tensor operations

    by D. V. Savostyanov, E. E. Tyrtyshnikov, N. L. Zamarashkin

    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.