Research Group of Boris Khoromskij

Tensor-structured Numerical Methods in High Dimensional Scientific Computing

Group members
      • PD DrSci. Boris Khoromskij. Scientific Group Leader.

      • Dr. Venera Khoromskaia. Post Doctoral researcher.
        Multilevel Tucker approximation,
        tensor calculation of 3D and 6D integral operators in 1D complexity (in quantum chemistry),
        tensor-structured numerical solution of the Hartree-Fock equation,
        grid-based calculation of two-electron integrals,
        post-HF models.

      • Dipl.-Math. Sergej Dolgov. PhD student.
        The Focker-Planck dynamics,
        DMRG, parametric PDEs, preconditioning.

      • Dipl.-Math. Christian Schindler. PhD student.
        Tensor-structured elliptic inverse,
        optimization on tensor manifolds.

      • Dr. Ivan Oseledets. Visiting researcher.
        DMRG, stochastic PDEs, molecular dynamics,
        tensor-train format.

    Field of research
      The most challenging problems of numerical computations nowadays are those of higher dimensions (in Rd ), for example,
      • modelling of multi-particle interactions in large molecular systems such as proteins, biomolecules,
      • modelling of large atomic (metallic) clusters,
      • stochastic and parametric equations,
      • multidimensional dynamical systems,
      • entanglement based quantum computing, DMRG method for studying extended quantum systems,
      • machine learning, data mining and information technologies.

      Numerical treatment of arising high-dimensional partial differential equations and optimization problems requires nonstandard approaches since the computational complexity of traditional numerical methods scales exponentially in the dimension refered as the "curse of dimensionality", O(nd ).

      The breaking-through idea is based on the use of low-parametric data formats generated by the separable tensor product representations, which allow linear complexity scaling in the dimension, O( n d).

      Now we focus on development of the novel O(d log n ) -complexity numerical methods for the efficient solution of high-dimensional steady-state and dynamical integral-differential equations. They are based on the low rank tensor-product approximation of multivariate functions and operators in quantized tensor spaces leading to numerical schemes of log-volume complexity, O( d log n ).

      The tensor-structured methods are initially developed for the grid-based numerical solution of Hartree-Fock equation in a general basis. These include fast and accurate tensor calculation of 3D and 6D convolution operators with the Newton kernel, as well as the core Hamiltonian, Hartree and exchange operators, in 1D complexity. The novel method of factorized redundancy-free calculation of the two-electron integrals tensor opens the way for efficient simulation of large molecular systems in electronic structure calculations.

      Tensor methods also gainfully apply to the large scale problems arising in molecular and the Focker-Planck dynamics, and parametric/stochastic PDEs, and approximation of multivariate functions.

      Numerical efficiency and accuracy of the developed tensor algorithms is confirmed on real-life problems by comparison with existing alternative approaches (model reduction, analytically based and Monte Carlo methods).

    Main results (in chronological order)
    • Low-rank tensor-product representation of a class of multi-dimensional nonlocal operators:
      constructive approximation by sinc-interpolation and quadratures, error analysis, analytic rank optimization.
      [Gavrilyuk, Hackbusch, Khoromskij '02, 03, '05],
      [Hackbusch, Khoromskij, Tyrtyshnikov '03, '04', '05],
      [Bertoglio, Khoromskij '08]

    • Structured hierarchical dimension splitting and Tucker decomposition of function related tensors.
      [Khoromskij '06]

    • Functional Tucker approximation, canonical-to-Tucker decomposition.
      Starting the development of tensor algebra MATLAB library for the calculation of 3D integral operators .
      [Khoromskij '06]
      [Khoromskij, Khoromskaia '06]

    • Theory and numerical algorithms for multidimensional tensor convolution
      in canonical-Tucker format with applications.
       [Khoromskij '08]

    • Efficient multigrid canonical-to-Tucker-to-canonical (C2T+T2C) tensor rank reduction for 3D tensors in 1D complexity
      based on the two-level (combined) Tucker-to-canonical decomposition on a sequence of grids,
      reduced higher order SVD for the canonical tensors and concept of most important fibers.
      [Khoromksij, Khoromskaia '08]

    • Tensor methods in applications to Boltzmann and Kohn-Sham equations.
      [Khoromskij'04]
      [Khoromskij'06]

    • Tensor-structured calculation of 3D and 6D integrals in the Fock operator in 1D complexity.
      [Khoromksij, Khoromskaia '08]

    • Computation of the Hartree-Fock (HF) exchange by the tensor-structured methods.
      [Khoromskaia '09]

    • Grid-based solution of the Hartree-Fock equation by multilevel tensor-structured methods.
      3D "black-box" EVP solver for the HF euqation, in 1D complexity.
      [Khoromksij, Khoromskaia, Flad '09]
      [Khoromskaia '10]

    • Tensor methods for stochastic and parametric PDEs.
      [Khoromskij, Litvinenko, Matthias, '08]
      [Khoromskij, Schwab, '09]
      [Khoromskij, Oseledets, '10]
      [Dolgov, Kazeev, Khoromskij, '12]

    • Novel concept of quantized vector/tensor format of O(d log n ) (log-volume) complexity.
      Approximation theory by low-rank quantized-canonical and quantized-TT (QTT) representation of functional tensors.
      [Khoromskij,'09]

    • Super-compressed representation to multivariate polynomials,
      operator exponential, and QTT-DMRG spectral solvers.
      [Khoromskij,'09]
      [Khoromskij, Oseledets '09, '10]

    • Tensor-structured preconditioning R in Rd .
      [Khoromskij '09]
      [Dolgov, Khoromskij, Oseledets, Tyrtyshnikov '09]

    • QTT-compression method applied to the d-dimensional elliptic operator inverse,
      convolution transform, FFT and other operations in quantized tensor spaces
      providing log-scaling complexity.
      [Kazeev, Khoromskij '10],
      [Dolgov, Khoromskij, Savostyanov '11],
      [Kazeev, Khoromskij, Tyrtyshnikov '11]
      [Khoromskaia, Khoromskij, Schneider '11].

    • Quantum molecular dynamics on tensor manifolds and related spectral calculations by QTT-DMRG and QTT-Cayley-transform iteration.
      Dynamics on tensor manifold by the Dirac-Frenkel variational principle.
      [Khoromskij, Oseledets '10]
      [Gavrilyuk, Khoromskij '11]
      [Khoromskij, Oseledets, Schneider '12]

    • Time-dependent Fokker-Planck equation.
      [Dolgov, Khoromskij, Oseledets '11]

    • Tensor-structured grid-based calculation of the 3D Laplace and nuclear potential parts in the Fock operator.
      [Khoromskaia, Andrae, Khoromskij '12]

    • Efficient grid-based tensor calculation of the two-electron integrals and the Fock operator in a general basis.
      [Khoromskaia, Khoromskij, Schneider '12]

    •  Since 2006: development of the MATLAB library implementing  multi-linear algebra and 
the rank-structured tensor approximations to a class of multivariate functions, 
integral transforms and Hamiltonians (electronic structure calculations), many-particle 
modeling, as well as  the fast tensor-truncated iterative solution methods 
for high-dimensional stationary and dynamical equations in scientific computing.

    1. I. V. Oseledets, B. N. Khoromskij and R. Schneider.
      Efficient Time-stepping Scheme for Dynamics on TT-manifolds.
      Preprint 24/2012, MPI MIS Leipzig, 2012.

    2. V. Khoromkaia, B. N. Khoromskij and R. Schneider.
      Grid-based Calculation of Two-electron Integrals in Tensor-structured Formats.
      MPI MIS Leipzig, 2012.

    3. S. Dolgov and B. N. Khoromskij.
      Two-level Tucker-TT-QTT format for optimized tensor calculus.
      Preprint 19/2012, MPI MIS Leipzig, 2012.

    4. V. Khoromkaia, D. Andrae and B. N. Khoromskij.
      Fast and Accurate Tensor Calculation of the Fock Operator in a General Basis.
      Preprint 4/2012, MPI MIS Leipzig, 2012.

    5. S.V. Dolgov, B.N. Khoromskij, and I. Oseledets.
      Fast solution of multi-dimensional parabolic problems in the TT/QTT formats with initial application to the Fokker-Planck equation.
      Preprint 80/2011 MPI MiS Leipzig, 2011,
      submitted to SISC.

    6. I. P. Gavrilyuk, and B. N. Khoromskij.
      Quantized-TT-Cayley transform to compute dynamics and spectrum of high-dimensional Hamiltonians.
      Preprint 43/2011 MPI MiS Leipzig, 2011.
      Comp. Meth. in Applied Math., v.11 (2011), No. 3, 273-290.

    7. B. N. Khoromskij, S. A. Sauter, and A. Veit.
      Fast Quadrature Techniques for Retarded Potentials Based on TT/QTT Tensor Approximation.
      Preprint 42/2011 MPI MiS Leipzig, 2011.
      Comp. Meth. in Applied Math., v.11 (2011), No. 3, 342 - 362.

    8. S. V. Dolgov, B. N. Khoromskij, and D. Savostyanov.
      Superfast Fourier Transform Using QTT Approximation.
      Preprint 18/2011 MPI MiS Leipzig, 2011, submitted.

    9. V. Khoromkaia, B. N. Khoromskij and R. Schneider.
      QTT Representation of the Hartree and Exchange Operators in Electronic Structure Calculations.
      Preprint 37/2011 MPI MiS Leipzig, 2011.
      Comp. Meth. in Applied Math., v.11 (2011), No. 3, 327-341.

    10. V. Kazeev, B. N. Khoromskij, and E. E. Tyrtyshnikov.
      Multilevel Toeplitz matrices generated by QTT tensor-structured vectors and convolution with logarithmic complexity.
      Preprint 36/2011 MPI MiS Leipzig, 2011,
      submitted.

    11. S. V. Dolgov, B. N. Khoromskij, I. Oseledets, and E. E. Tyrtyshnikov.
      Low-rank Tensor Structure of Solutions to Elliptic Problems with Jumping Coefficients.
      Preprint 12/2011 MPI MiS Leipzig, 2011.
      J. of Comput. Math. v. 30, No. 1, 2012, 14-23.

    12. B. N. Khoromskij.
      Introduction to Tensor Numerical Methods in Scientific Computing.
      Lecture notes, Preprint 06-2011, University of Zuerich, Institute of Mathematics, 2011, pp.1-238.
      (pdf)

    13. V. Kazeev and B. N. Khoromskij.
      On Explicit QTT Representation of the Laplace Operator and its Inverse.
      Preprint 75/2010, MPI MiS, Leipzig 2010.
      SIMAX, submitted.

    14. B.N. Khoromskij, and I. Oseledets.
      DMRG + QTT approach to the computation of ground state for the molecular Schroedinger operator.
      Preprint 69/2010, MPI MiS, Leipzig 2010.
      Numer. Math., submitted.

    15. B. N. Khoromskij.
      Tensors-structured Numerical Methods in Scientific Computing: Survey on Recent Advances.
      Preprint MPI MIS Leipzig 21/2010..
      Chemometr. Intell. Lab. Syst. 110 (2012), 1-19.

    16. B.N. Khoromskij, and I. Oseledets.
      Quantics-TT Collocation Approximation of Parameter-dependent and Stochastic Elliptic PDEs.
      Preprint 37/2010, MPI MIS Leipzig 2010.
      Comp. Meth. in Applied Math., 10(4), 2010, 376-394.

    17. S. V. Dolgov, B. N. Khoromskij, I. Oseledets, and E. E. Tyrtyshnikov.
      A reciprocal preconditioner for structured matrices arising from elliptic problems with jumping coefficients.
      Preprint 55/2010, MPI MiS, Leipzig 2010.
      Linear Algebra Appl. (2011), DOI: 10.1016/j.laa.2011.09.010

    18. B. N. Khoromskij and I. Oseledets.
      Quantics-TT Approximation of Elliptic Solution Operators in Higher Dimensions.
      Preprint 79/2009, MPI MIS Leipzig, 2009.
      Russ. J. Numer. Anal. Math. Modelling, v. 26(3), pp. 303-322 (2011).

    19. B. N. Khoromskij.
      O(d log n)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling.
      Preprint 55/2009, MPI MIS Leipzig, 2009.
      J. Constr. Approx., v. 34(2), 257-289 (2011).

    20. V. Khoromskaia.
      Numerical Solution of the Hartree-Fock Equation by Multilevel Tensor-structured methods.
      PhD Dissertation, TU Berlin, December 2010.
      http://opus.kobv.de/tuberlin/volltexte/2011/2948/

    21. B. N. Khoromskij, V. Khoromskaia, and H.-J. Flad.
      Numerical Solution of the Hartree-Fock Equation in Multilevel Tensor-Structured Format.
      Preprint 44/2009, MPI MIS Leipzig, 2009.
      SIAM J. Sci. Comp., v. 33(1), 2011, pp. 45-65.

    22. B. N. Khoromskij.
      Tensor-structured Preconditioners and Approximate Inverse of Elliptic Operators in Rd .
      Preprint 82/2008, MPI MIS Leipzig, 2008.
      J. Constructive Approximation, 30:599-620 (2009).

    23. B. N. Khoromskij and Ch. Schwab.
      Tensor-Structured Galerkin Approximation of Parametric and Stochastic Elliptic PDEs.
      Preprint 9/2010, MPI MIS Leipzig, 2010.
      SIAM J. Sci. Comp. 33(1), 2011, 364-385.

    24. T. Blesgen, V. Gavini and V. Khoromskaia.
      Approximation of the Electron Density of Aluminium Clusters in Tensor-Product Format,
      Preprint 66/2009, MPI MIS Leipzig, 2009.
      Journal of Computational Physics, (2011), doi: 10.1016/j.jcp.2011.12.009 .

    25. V. Khoromskaia.
      Computation of the Hartree-Fock Exchange by the Tensor-Structured Methods.
      Preprint 25/2009, MPI MIS Leipzig,
      Computational Methods in Applied Mathematics, vol. 10, No 2, pp.204-218, 2010.

    26. C. Bertoglio, and B. N. Khoromskij.
      Low Rank quadrature-based tensor approximation of the Galerkin projected Newton/Yukawa kernels.
      Preprint 79/2008, MPI MIS Leipzig, 2008.
      Comp. Phys. Communications, v. 183(4), 904-912 (2012).

    27. H.-J. Flad, B. N. Khoromskij, D. Savostianov and E. Tyrtyshnikov.
      Verification of the Cross 3d Algorithm on Quantum Chemistry Data.
      Preprint 80/2008, MPI MIS Leipzig, 2008.
      Rus. J. Numer. Anal. and Math. Modelling, 23 (2008) 4, 329-344.

    28. B. N. Khoromskij and V. Khoromskaia.
      Multigrid Accelerated Tensor Approximation of Function Related Multi-dimensional Arrays.
      Preprint 40/2008, MPI MIS Leipzig, 2008,
      SIAM J. Sci. Comp., vol. 31, No. 4, pp. 3002-3026.

    29. B. N. Khoromskij.
      Fast and Accurate Tensor Approximation of a Multivariate Convolution with Linear Scaling in Dimension.
      Preprint 36/2008, MPI MIS Leipzig, 2008.
      J. Comp. Appl. Math., 234 (2010) 3122-3139.

    30. H.-J. Flad, W. Hackbusch, B. N. Khoromskij and R. Schneider.
      Concepts of Data-Sparse Tensor-Product Approximation in Many-Particle Modeling.
      Preprint 3/2008, MPI MIS Leipzig, 2008.
      In: Matrix Methods: Theory, Algorithms and Applications, (dedicated to the Memory of Gene Golub)
      V. Olshevsky, E. Tyrtyshnikov eds., World Scientific, 2010, pp.313-347.

    31. B. N. Khoromskij.
      On Tensor Approximation of Green Iterations for Kohn-Sham equations.
      Preprint 4/2008, MPI MIS Leipzig, 2008.
      Computing and Visualisation in Science , (2008) 11:259-271.

    32. B. N. Khoromskij, V. Khoromskaia, S.R. Chinnamsetty and H.-J. Flad.
      Tensor Decomposition in Electronic Structure Calculations on 3D Cartesian Grids.
      Preprint 65/2007, MPI MIS Leipzig, 2007.
      J. Comp. Phys., 228, (2009) 5749-5762.

    33. W. Hackbusch, B. N. Khoromskij, S. Sauter and E. Tyrtyshnikov.
      Use of Tensor Formats in Elliptic Spectral Problems.
      Preprint 78/2008, MPI MIS Leipzig, 2008.
      Numer. Lin. Alg. Appl., v. 19(1), 2012, 133-151.

    34. S.R. Chinnamsetty, M. Espig, B.N. Khoromskij, W. Hackbusch and H.-J. Flad.
      Tensor Product Approximation with Optimal Rank in Quantum Chemistry.
      Preprint 105, MPI MIS Leipzig, 2007.
      J. Chem. Phys., 127, 084110 (2007).

    35. B. N. Khoromskij and V. Khoromskaia.
      Low Rank Tucker-Type Tensor Approximation to Classical Potentials.
      Preprint 105/2006, MPI MIS Leipzig, 2006.
      Central European Journal of Mathematics v.5, N.3, 2007, 523-550.

    36. W. Hackbusch and B. N. Khoromskij.
      Tensor-product Approximation to Operators and Functions in High Dimensions.
      Journal of Complexity , (23) 2007, 697-714.

    37. B. N. Khoromskij.
      Structured Data-sparse Approximation to High Order Tensors arising from the Deterministic Boltzmann equation.
      Math. Comp. 76 (2007), pp. 1292-1315.

    38. W. Hackbusch and B. N. Khoromskij.
      Tensor-product Approximation to Multi-dimensional Integral Operators and Green's Functions.
      Preprint 38, MPI MIS, Leipzig 2006.
      SIAM J. Matr. Anal. Appl. , 30, no.3, 1233-1253, 2008.

    39. W. Hackbusch and B. N. Khoromskij.
      Low-rank Kronecker-product Approximation to Multi-dimensional Nonlocal Operators.
      Part I. Separable Approximation of Multi-variate Functions.
      Computing 76 (2006), pp. 177-202.

    40. B. N. Khoromskij.
      Structured Rank- (r1,...,rd) Decomposition of Function-related Tensors in Rd .
      Preprint 6/2006, MPI MIS Leipzig, 2006.
      Comp. Meth. in Appl. Math. , v.6, No.2, (2006), 194-220.

    41. W. Hackbusch and B. N. Khoromskij.
      Low-rank Kronecker-product Approximation to Multi-dimensional Nonlocal Operators.
      Part II. HKT Representation of Certain Operators.
      Computing 76 (2006), pp. 203-225.

    42. W. Hackbusch, B. N. Khoromskij and E. E. Tyrtyshnikov.
      Approximate Iteration for Structured Matrices.
      Preprint 112, MPI MIS, Leipzig, 2005.
      Numer. Math. , 109, 365-383, 2008.

    43. W. Hackbusch, B. N. Khoromskij and E. E. Tyrtyshnikov.
      Hierarchical Kronecker tensor-product approximations.
      Numer. Math. 13 (2005), pp. 119-156.

    44. I.P. Gavrilyuk, W. Hackbusch and B.N. Khoromskij.
      Hierarchical Tensor-Product Approximation to the Inverse and Related Operators in High-Dimensional Elliptic Problems.
      Computing 74 (2005), 131-157.

    45. I. P. Gavrilyuk, W. Hackbusch and B. N. Khoromskij.
      Data-sparse approximation of a class of operator-valued functions.
      Preprint 20/2003, MPI MIS Leipzig, 2003.
      Math. Comp. 74 (2005), pp. 681-708.

    46. I. P. Gavrilyuk, W. Hackbusch and B.N. Khoromskij.
      Data-sparse approximation to the operator-valued functions of elliptic operators.
      Preprint 54/2002, MPI MIS Leipzig, 2002.
      Math. Comp. 73 (2004), pp. 1297-1324.

    External collaborators
      • Prof. Dr. Reinhold Schneider (TU Berlin)
      • Prof. Dr. Eugene Tyrtyshnikov (INM, Academy of Science, Moscow)
      • Dr. Heinz-Juergen Flad (TU Berlin)
      • Prof. Dr. Ivan Gavrilyuk (BA Eisenach)
      • Prof. Dr. Christof Schwab (ETH Zuerich)
      • Prof. Dr. Stefan Sauter (Uni Zuerich)
      • PD Dr. Dirk Andrae (FU Berlin)

    Former members
      • Dr. Dmitrij Savostyanov (Uni Chester, UK)
      • Dipl.-Math. Vladimir Kazeev (PhD student, ETH Zuerich)
      • Dr. Ekaterina Muravleva (Lomonosov Uni, Moscow)
      • Teresa Strauch (Dipl. student, Uni Freiburg)
      • Dipl.-Ing. Christobal Bertolio (PhD student, INRIA, Paris)

last modified 02.02.2012
Webdesign V. Khoromskaia