Source-linked AI summary
Computation of extreme eigenvalues in higher dimensions using block tensor train format
Sergey V. Dolgov, Boris N. Khoromskij, Ivan V. Oseledets, Dmitry V. Savostyanov
TL;DR
Computing several low-lying eigenpairs of high-dimensional Hermitian matrices is difficult because standard approaches face rapidly growing complexity. This paper uses block tensor trains and alternating block-Rayleigh-quotient minimization; tests show it handles highly multiple states, beats DMRG on one ground-state computation, and is competitive with available DMRG implementations.
Problem
Standard numerical methods face exponentially growing complexity on high-dimensional problems, motivating tractable computation of several low-lying eigenpairs.
Source: §1 · pp. 1–2Method
Results
The method finds highly multiple particle-in-a-box states, computes the Henon-Heiles ground state faster than DMRG, and is competitive with state-of-the-art public DMRG implementations on the Heisenberg spin chain.
Source: §7 · pp. 15–16Takeaways & Limitations
The proposed one-site rank-adaptive method has mode-size complexity linear for sparse matrices and quadratic for dense matrices, better than DMRG.
Source: §7 · p. 15The moving block index can permit TT ranks to grow exponentially during iterations, so efficient optimization requires measures to keep ranks moderate.
Source: §2 · p. 5
Abstract
from arXiv · showhide
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.
1 Introduction
High-dimensional problems become intractable for standard methods as complexity grows exponentially with the number of degrees of freedom. This paper extends tensor-train eigenvalue computation to several eigenpairs at once using block Rayleigh minimization and alternating optimization.
1 Introduction
- High-dimensional problems challenge standard numerical techniques because complexity grows exponentially with the number of degrees of freedom.Monte Carlo accuracy can be difficult to achieve, while sparse grids still suffer from the curse of dimensionality and can be inapplicable for d ≳10.Source: §1 · pp. 1–2
- The TT format is equivalent to the MPS format, enabling DMRG ideas to be applied to numerical-analysis problems.The paper situates its work as an extension of computing a single extreme eigenvalue in TT format to several eigenpairs simultaneously.Source: §1 · p. 2
- The block-TT approach represents several eigenstates simultaneously and minimizes their block Rayleigh quotient by alternating optimization.The eigenstate index is associated with the currently optimized TT core, yielding a local block eigenvalue problem at each step.Source: §1 · pp. 2–3
- The proposed algorithm improves asymptotic complexity with respect to mode size while adapting TT ranks during iterations, as in DMRG.The authors note this can be particularly important for high-dimensional problems with large mode sizes.Source: §1 · p. 3
- The paper compares its method with one-by-one deflation and quantum-physics variational algorithms across several numerical examples.The experiments cover a particle in a box, the Henon–Heiles potential, and the Heisenberg model.Source: §1 · p. 3
2 Notation, definitions and preliminaries
The paper represents high-dimensional vectors and matrices in tensor-train form, then extends the vector representation to a block format for multiple eigenvectors. The block index moves between TT cores during optimization, so rank control and orthogonalization are important.
2 Notation, definitions and preliminaries
- A vector is represented through a product of TT cores, while a matrix has a corresponding higher-dimensional TT representation.In the TT network, bonds denote summed auxiliary indices.Source: §2 · pp. 4, 6, Figure 1 · p. 4
- The block-TT format represents multiple eigenvectors simultaneously by attaching the eigenvector index to one TT core.The core carrying that index is four-indexed, and the frame matrix maps a TT core to the full vector.Source: §2 · p. 4, Figure 2 · p. 5
- Moving the eigenvector index between cores changes the TT rank, which can grow as large as rB and requires rank-control measures.The paper uses approximate low-rank decomposition for truncation; orthogonalizing the surrounding cores makes the frame matrix orthogonal and supports accuracy control.Source: §2 · pp. 5–6
- The algorithm sweeps across cores, solves local problems, truncates ranks, and transfers the block index to the next core.Its stated procedure includes left-to-right and right-to-left half-sweeps.Source: §2 · p. 7
3 Minimization of the block Rayleigh quotient in the block–TT format
The method replaces optimization over the full tensor space with alternating local optimization over one TT core at a time. Rank adaptation controls the block representation, and the resulting complexity is linear in mode size for sparse matrices and quadratic for dense matrices.
3 Minimization of the block Rayleigh quotient in the block–TT format
- Freezing all but one TT core reduces the block Rayleigh quotient minimization to a smaller local block eigenproblem.The local problem is organized into sweeps, with the number of unknowns linear in the mode size.Source: §3 · p. 7
- SVD-based low-rank approximation can be the slowest step when n and B are both large, while cross interpolation or incomplete Cholesky can reduce its cost to O(Br^3n).The reduced cost is stated to be at the level of the algorithm's other steps.Source: §3 · p. 8
- When TT rank grows with the number of eigenstates B, the stated overall work is O(dBr^3r_An).This is the asymptotic regime the authors identify as more likely for large B and r.Source: §3 · p. 8
- The paper reports DMRG complexity O(dBr^3n^3) and variational NRG complexity O(Br^3 + dr^3n^3).The DMRG cost is cubic in n because each step optimizes over two modes.Source: §3 · p. 8
4 Laplace operator (particle in a box)
The Laplace-operator test compares block-TT and deflation on a discretized particle-in-a-box problem with known eigenpairs and highly degenerate excited levels. For d=5 and B=30, block-TT recovers all tested states accurately, whereas deflation misses intermediate states and multiplicities.
4 Laplace operator (particle in a box)
- The test discretizes a particle in a d-dimensional box on a uniform tensor grid, yielding a Kronecker-sum Laplacian with analytical eigenvalues that are sums of one-dimensional eigenvalues.The corresponding high-dimensional eigenvectors are tensor products of the one-dimensional eigenvectors.Source: §4 · p. 9
- Excited energy levels have multiplicities, and the paper groups eigenvectors with equal eigenvalues into invariant eigenspaces, making this an instructive test for eigensolver convergence.The reported run uses mode size n=16.Source: §4 · p. 9
- For d=5 and B=30, block-TT recovered all 30 eigenstates accurately, while deflation accurately found only the ground state and two vectors in X1.Figure 4 compares eigenvalue and vector errors across truncation thresholds; the block-method errors rapidly reach machine precision.Source: Figure 4 · p. 10, §4 · pp. 10–11
- The deflation comparison computes eigenstates one at a time under orthogonality constraints, but may converge to an eigenpair with a larger energy level.The authors state that the block algorithm can compute lower-lying states for B ≲ 100.Source: §4 · p. 10
- Deflation's remaining vectors fell into subspaces above X4, so it did not recover the multiplicity or intermediate states; the block algorithm was reliable for large multiplicities and small spectral gaps.The angle-error floor is sqrt(machine precision) because of the acos function.Source: §4 · pp. 10–11
5 Henon–Heiles potential
The Henon–Heiles experiments test block-TT eigenpair computation with Hermite-DVR discretization. They report dimension-stable eigenvalue errors, accuracy limits from truncation, and costs shaped by mode size and TT-ranks.
5 Henon–Heiles potential
- The Henon–Heiles example is a benchmark for high-dimensional quantum molecular dynamics, with the wavefunction satisfying a stationary Schrödinger equation.The potential's anharmonic contribution is controlled by λ = 0.111803.Source: §5 · p. 11
- The Hermite-DVR discretization collocates the potential and wavefunction at Hermite-polynomial nodes, with accuracy of the same order as Galerkin discretization.The discretized Laplacian has TT-ranks no larger than two, and the potential has TT-ranks no larger than seven, allowing Alg. 1 to be applied.Source: §5 · pp. 11–12
- Eigenvalue errors do not grow with dimension, while convergence is quadratic in truncation threshold ε and computational cost grows mildly with dimension and eigenstate count B.The experiments use a random block-TT initial guess and report that energy levels can be computed with high accuracy.Source: §5 · p. 12
- Block-TT and DMRG require the same CPU time despite block-TT's lower mode-size cost, because larger excited-state TT-ranks increase the local eigenproblem complexity.The comparison uses at least B = 2 block-TT eigenstates against DMRG targeting one lowest eigenpair.Source: §5 · p. 12
- Eigenvalue error decreases exponentially with mode size n only until O(ε^2), while CPU-time growth balances O(n) truncation and O(n^2) dense matrix-vector multiplication.Figure 6 plots errors and CPU times against n and ε for B = 2 and d = 30; its reference uses ε = 10^-7 and n = 28.Source: Figure 6 · p. 12, §5 · p. 13
6 Heisenberg model
On the Heisenberg spin chain, block TT has timing comparable to ITensor and is faster than ALPS, while computing multiple eigenstates. Its costs scale polynomially, and its memory use supports more targets than ALPS in the reported tests.
6 Heisenberg model
- The comparison uses ALPS, which can compute several excited states, and ITensor, which targets the ground state; block TT is run with B = 2 against ITensor at B = 1.The software was compiled with Intel C/Fortran 2013 and optimized MKL libraries and run on one four-core Intel Xeon processor at 2 GHz.Source: §6 · p. 13
- All methods show polynomial CPU-time scaling with spin count d and target count B; block-TT time grows as O(B^β), with β ≈ 2.5.The expected work is O(B^4) if TT-ranks scale as B; non-uniform ranks explain why the estimate exceeds observed computation time.Source: §6 · p. 14, Figure 7 · p. 14, Figure 8 · p. 14
- ALPS runs out of memory above 12 targets, whereas the block-TT implementation readily computes more than 20 eigenstates.Source: §6 · p. 14
- The accuracy parameter ε is not equivalent across methods: block TT truncates eigenvectors, whereas the other packages threshold eigenvalue accuracy using ε^2.Source: §6 · pp. 14–15
- Block TT performance is comparable to ITensor, while ALPS is significantly slower; comparing eigb eigenvalues with those from the other two methods demonstrates O(ε^2) eigenvalue accuracy.Source: §6 · p. 15
7 Conclusions
The paper proposes a one-site rank-adaptive method that represents several eigenstates simultaneously in block tensor train format. Tests include high-multiplicity particle-in-a-box eigenstates, the Henon–Heiles problem, and a Heisenberg spin chain, where the method is competitive with publicly available DMRG implementations.
7 Conclusions
- The proposed one-site rank-adaptive algorithm computes several extreme eigenvalues of high-dimensional Hermitian matrices using block tensor train representations.Its complexity is linear in mode size for sparse matrices and quadratic for dense matrices, better than DMRG; its asymptotics in eigenstate count, TT ranks, and dimension match DMRG and NRG.Source: §7 · p. 15
- Tests show the algorithm can find high-multiplicity eigenstates of the high-dimensional Laplace matrix describing a particle in a box.It is also applied to the stationary Schrödinger equation with the Henon–Heiles potential.Source: §7 · p. 15
- The Heisenberg spin-chain method is competitive with state-of-the-art publicly available DMRG implementations.Source: §7 · p. 16
- The framework can also be applied to a wider class of problems formulated via subspace optimization.Source: §7 · p. 16
Software implementation
The main algorithm is implemented in Fortran, with interfaces to Python and MATLAB.
Software implementation
- The main algorithm is implemented in Fortran with Python and MATLAB interfaces.The code is available online.Source: Software implementation · p. 16