Search

Recently the rank-structured tensor approach suggested a progress in the numerical treatment of the long-range electrostatic potentials in many-particle systems and the respective interaction energy and forces [39,40,2]. In this paper, we outline the prospects for tensor-based numerical modeling of the collective electrostatic potential on lattices and in many-particle systems of general type. We generalize the approach initially introduced for the rank-structured grid-based calculation of the collective potentials on 3D lattices [39] to the case of many-particle systems with variable charges placed on $L^{\otimes d}$ lattices and discretized on fine $n^{\otimes d}$ Cartesian grids for arbitrary dimension $d$. As result, the interaction potential is represented in a parametric low-rank canonical format in $O(d L n)$ complexity. The energy is then calculated in $O(d L)$ operations. Electrostatics in large biomolecules is modeled by using the novel range-separated (RS) tensor format [2], which maintains the long-range part of the 3D collective potential of the many-body system represented on $n\times n \times n$ grid in a parametric low-rank form in $O(n)$-complexity. We show that the force field can be easily recovered by using the already precomputed electric field in the low-rank RS format. The RS tensor representation of the discretized Dirac delta [45] enables the efficient energy preserving regularization scheme for solving the 3D elliptic PDEs with strongly singular right-hand side arising in bio-sciences. We conclude that the rank-structured tensor-based approximation techniques provide the promising numerical tools for applications to many-body dynamics, protein docking and classification problems and for low-parametric interpolation of scattered data in data science., Comment: 30 pages, 23 figures

In this paper, we present a new regularization scheme for the linearized Poisson--Boltzmann equation (PBE) which models the electrostatic potential of biomolecules in a solvent. This scheme is base...

In the present paper we propose and analyze a class of tensor approaches for the efficient numerical solution of a first order differential equation ψ ′ ⁢ ( t ) + A ⁢ ψ = f ⁢ ( t ) {\psi^{\prime}(t)+A\psi=f(t)} with an unbounded operator coefficient A. These techniques are based on a Laguerre polynomial expansions with coefficients which are powers of the Cayley transform of the operator A. The Cayley transform under consideration is a useful tool to arrive at the following aims: (1) to separate time and spatial variables, (2) to switch from the continuous “time variable” to “the discrete time variable” and from the study of functions of an unbounded operator to the ones of a bounded operator, (3) to obtain exponentially accurate approximations. In the earlier papers of the authors some approximations on the basis of the Cayley transform and the N-term Laguerre expansions of the accuracy order 𝒪 ⁢ ( e - N ) {\mathcal{O}(e^{-N})} were proposed and justified provided that the initial value is analytical for A. In the present paper we combine the Cayley transform and the Chebyshev–Gauss–Lobatto interpolation and arrive at an approximation of the accuracy order 𝒪 ⁢ ( e - N ) {\mathcal{O}(e^{-N})} without restrictions on the input data. The use of the Laguerre expansion or the Chebyshev–Gauss–Lobatto interpolation allows to separate the time and space variables. The separation of the multidimensional spatial variable can be achieved by the use of low-rank approximation to the Cayley transform of the Laplace-like operator that is spectrally close to A. As a result a quasi-optimal numerical algorithm can be designed.

Most important computational problems nowadays are those related to processing of the large data sets and to numerical solution of the high-dimensional integral-differential equations. These problems arise in numerical modeling in quantum chemistry, material science, and multiparticle dynamics, as well as in machine learning, computer simulation of stochastic processes and many other applications related to big data analysis. Modern tensor numerical methods enable solution of the multidimensional partial differential equations (PDE) in ℝ d {\mathbb{R}^{d}} by reducing them to one-dimensional calculations. Thus, they allow to avoid the so-called “curse of dimensionality”, i.e. exponential growth of the computational complexity in the dimension size d, in the course of numerical solution of high-dimensional problems. At present, both tensor numerical methods and multilinear algebra of big data continue to expand actively to further theoretical and applied research topics. This issue of CMAM is devoted to the recent developments in the theory of tensor numerical methods and their applications in scientific computing and data analysis. Current activities in this emerging field on the effective numerical modeling of temporal and stationary multidimensional PDEs and beyond are presented in the following ten articles, and some future trends are highlighted therein.

We consider a one-dimensional second-order elliptic equation with a high-dimensional parameter in a hypercube as a parametric domain. Such a problem arises, for example, from the Karhunen–Loeve expansion of a stochastic PDE posed in a one-dimensional physical domain. For the discretization in the parametric domain we use the collocation on a tensor-product grid. The paper is focused on the tensor-structured solution of the resulting multiparametric problem, which allows to avoid the curse of dimensionality owing to the use of the separation of parametric variables in the tensor train and quantized tensor train formats. We suggest an efficient tensor-structured preconditioning of the entire multiparametric family of one-dimensional elliptic problems and arrive at a direct solution formula. We compare this method to a tensor-structured preconditioned GMRES solver in a series of numerical experiments.

In this article we consider the iterative schemes to compute the canonical (CP) approximation of quantized data generated by a function discretized on a large uniform grid in an interval on the real line. This paper continues the research on the QTT method [16] developed for the tensor train (TT) approximation of the quantized images of function related data. In the QTT approach the target vector of length $2^{L}$ is reshaped to a $L^{th}$ order tensor with two entries in each mode (Quantized representation) and then approximated by the QTT tenor including $2r^2 L$ parameters, where $r$ is the maximal TT rank. In what follows, we consider the Alternating Least-Squares (ALS) iterative scheme to compute the rank-$r$ CP approximation of the quantized vectors, which requires only $2 r L\ll 2^L$ parameters for storage. In the earlier papers [17] such a representation was called Q$_{Can}$ format, while in this paper we abbreviate it as the QCP representation. We test the ALS algorithm to calculate the QCP approximation on various functions, and in all cases we observed the exponential error decay in the QCP rank. The main idea for recovering a discretized function in the rank-$r$ QCP format using the reduced number the functional samples, calculated only at $O(2rL)$ grid points, is presented. The special version of ALS scheme for solving the arising minimization problem is described. This approach can be viewed as the sparse QCP-interpolation method that allows to recover all $2r L$ representation parameters of the rank-$r$ QCP tensor. Numerical examples show the efficiency of the QCP-ALS type iteration and indicate the exponential convergence rate in $r$.

In this paper, we introduce a new interpolation scheme to approximate the density of states (DOS) for a class of rank-structured matrices with application to the Tamm–Dancoff approximation (TDA) of the Bethe–Salpeter equation (BSE). The presented approach for approximating the DOS is based on two main techniques. First, we propose an economical method for calculating the traces of parametric matrix resolvents at interpolation points by taking advantage of the block-diagonal plus low-rank matrix structure described in [6] , [3] for the BSE/TDA problem. This allows us to overcome the computational difficulties of the traditional schemes since we avoid the construction of the matrix inverse and hence the need of stochastic sampling. Second, we show that a regularized or smoothed DOS discretized on a fine grid of size N can be accurately represented in a low rank quantized tensor train (QTT) format that can be determined through a least squares fitting procedure. The QTT tensor provides good approximation properties for strictly oscillating DOS functions with multiple gaps, in contrast to interpolation by problem independent functions like polynomials, trigonometric functions, etc. Moreover, the QTT approximant requires asymptotically much fewer (e.g., O ( log ⁡ N ) ) functional calls compared with the full grid size N. Numerical tests indicate that the QTT approach yields accurate recovery of DOS associated with problems that contain relatively large spectral gaps. The QTT tensor rank only weakly depends on the size of a molecular system that paves the way for treatment of large-scale spectral problems.

We introduce the tensor numerical method for solution of the d-dimensional optimal control problems ( d = 2 , 3 ) with spectral fractional Laplacian type operators in constraints discretized on large n ⊗ d tensor-product Cartesian grids. The approach is based on the rank-structured approximation of the matrix valued functions of the corresponding fractional finite difference Laplacian. We solve the equation for the control function, where the system matrix includes the sum of the spectral fractional d-dimensional Laplacian and its inverse. The matrix valued functions of discrete Laplace operator on a tensor grid are diagonalized by using the fast Fourier transform (FFT). Then the low rank approximation of the d-dimensional tensors obtained by folding of the corresponding large diagonal matrices of eigenvalues are computed, which allows to solve the governing equation for the control function in a tensor-structured format. The existence of low rank canonical approximation to the class of matrix valued functions involved is justified by using the sinc quadrature approximation method applied to the Laplace transform of the generating function. The linear system of equations for the control function is solved by the PCG iterative method with the rank truncation at each iteration step, where the low Kronecker rank preconditioner is pre-computed. The right-hand side, the solution vector, and the governing system matrix are maintained in the rank-structured tensor format which beneficially reduces the numerical cost to O ( n log ⁡ n ) , outperforming the standard FFT based methods of complexity O ( n 3 log ⁡ n ) for 3D case. Numerical tests for the 2D and 3D control problems confirm the linear complexity scaling of the method in the univariate grid size n.

The Bethe-Salpeter equation (BSE) is a reliable model for estimating the absorption spectra in molecules and solids on the basis of accurate calculation of the excited states from first principles. This challenging task includes calculation of the BSE operator in terms of two-electron integrals tensor represented in molecular orbital basis, and introduces a complicated algebraic task of solving the arising large matrix eigenvalue problem. The direct diagonalization of the BSE matrix is practically intractable due to $O(N^6)$ complexity scaling in the size of the atomic orbitals basis set, $N$. In this paper, we present a new approach to the computation of Bethe-Salpeter excitation energies which can lead to relaxation of the numerical costs up to $O(N^3)$. The idea is twofold: first, the diagonal plus low-rank tensor approximations to the fully populated blocks in the BSE matrix is constructed, enabling easier partial eigenvalue solver for a large auxiliary system relying only on matrix-vector multiplications with rank-structured matrices. And second, a small subset of eigenfunctions from the auxiliary eigenvalue problem is selected to build the Galerkin projection of the exact BSE system onto the reduced basis set. We present numerical tests on BSE calculations for a number of molecules confirming the $\varepsilon$-rank bounds for the blocks of BSE matrix. The numerics indicates that the reduced BSE eigenvalue problem with small matrices enables calculation of the lowest part of the excitation spectrum with sufficient accuracy.

We prove by counterexample that the bound on the rounding error given in Theorem 5.2 of [Dolgov and Khoromskij, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 593--623] does not hold in general. A correct version of the error bound as well as a modified rounding algorithm for which the original bound holds are presented.

In this paper, we introduce the operator dependent range-separated (RS) tensor approximation of the discretized Dirac delta function (distribution) in R d . It is constructed by application of the elliptic operator to the RS tensor representation of the associated Green kernel discretized on the d-dimensional Cartesian grid. The proposed local-global decomposition of the Dirac delta can be applied for solving the potential equations in a non-homogeneous medium when the density in the right-hand side is given by a large sum of pointwise singular charges. As an example of applications, we describe the regularization scheme for solving the Poisson-Boltzmann equation that models the electrostatics in bio-molecules. We show how the idea of the operator dependent RS tensor decomposition of the Dirac delta can be generalized to the closely related problem on range-separated tensor representation of the elliptic resolvent. This approach paves the way for application of tensor numerical methods to elliptic problems with non-regular data. Numerical tests confirm the expected localization properties of the RS tensor approximation of the Dirac delta represented on a tensor grid in 3D.

We introduce and analyze the new range-separated (RS) canonical/Tucker tensor format which aims for numerical modeling of the 3D long-range interaction potentials in multiparticle systems. The main idea of the RS tensor format is the independent grid-based low-rank representation of the localized and global parts in the target tensor, which allows the efficient numerical approximation of $N$-particle interaction potentials. The single-particle reference potential, described by the radial basis function $p(\|x\|)$, $x \in \mathbb{R}^d$, say $p(\|x\|)=1/\|x\|$ for $d=3$, is split into a sum of localized and long-range low-rank canonical tensors represented on a fine 3D $n\times n\times n$ Cartesian grid. The smoothed long-range contribution to the total potential sum is represented on the 3D grid in $O(n)$ storage via the low-rank canonical/Tucker tensor. We prove that the Tucker rank parameters depend only logarithmically on the number of particles $N$ and the grid size $n$. Agglomeration of the short-rang...

We propose a new method for the efficient approximation of a class of highly oscillatory weighted integrals where the oscillatory function depends on the frequency parameter ω ≥ 0 ${\omega \ge 0}$ , typically varying in a large interval. Our approach is based, for a fixed but arbitrary oscillator, on the pre-computation and low-parametric approximation of certain ω-dependent prototype functions whose evaluation leads in a straightforward way to recover the target integral. The difficulty that arises is that these prototype functions consist of oscillatory integrals which makes them difficult to evaluate. Furthermore, they have to be approximated typically in large intervals. Here we use the quantized-tensor train (QTT) approximation method for functional M-vectors of logarithmic complexity in M in combination with a cross-approximation scheme for TT tensors. This allows the accurate approximation and efficient storage of these functions in the wide range of grid and frequency parameters. Numerical examples illustrate the efficiency of the QTT-based numerical integration scheme on various examples in one and several spatial dimensions.

Summary In this paper, we present a method for fast summation of long-range potentials on 3D lattices with multiple defects and having non-rectangular geometries, based on rank-structured tensor representations. This is a significant generalization of our recent technique for the grid-based summation of electrostatic potentials on the rectangular L × L × L lattices by using the canonical tensor decompositions and yielding the O(L) computational complexity instead of O(L3) by traditional approaches. The resulting lattice sum is calculated as a Tucker or canonical representation whose directional vectors are assembled by the 1D summation of the generating vectors for the shifted reference tensor, once precomputed on large N × N × N representation grid in a 3D bounding box. The tensor numerical treatment of defects is performed in an algebraic way by simple summation of tensors in the canonical or Tucker formats. To diminish the considerable increase in the tensor rank of the resulting potential sum, the ϵ-rank reduction procedure is applied based on the generalized reduced higher-order SVD scheme. For the reduced higher-order SVD approximation to a sum of canonical/Tucker tensors, we prove the stable error bounds in the relative norm in terms of discarded singular values of the side matrices. The required storage scales linearly in the 1D grid-size, O(N), while the numerical cost is estimated by O(NL). The approach applies to a general class of kernel functions including those for the Newton, Slater, Yukawa, Lennard-Jones, and dipole-dipole interactions. Numerical tests confirm the efficiency of the presented tensor summation method; we demonstrate that a sum of millions of Newton kernels on a 3D lattice with defects/impurities can be computed in seconds in Matlab implementation. The tensor approach is advantageous in further functional calculus with the lattice potential sums represented on a 3D grid, like integration or differentiation, using tensor arithmetics of 1D complexity. Copyright © 2015 John Wiley & Sons, Ltd.

We present a brief survey on the modern tensor numerical methods for multidimensional stationary and time-dependent partial differential equations (PDEs). The guiding principle of the tensor approach is the rank-structured separable approximation of multivariate functions and operators represented on a grid. Recently, the traditional Tucker, canonical, and matrix product states (tensor train) tensor models have been applied to the grid-based electronic structure calculations, to parametric PDEs, and to dynamical equations arising in scientific computing. The essential progress is based on the quantics tensor approximation method proved to be capable to represent (approximate) function related d-dimensional data arrays of size Nd with log-volume complexity, O(dlog N). Combined with the traditional numerical schemes, these novel tools establish a new promising approach for solving multidimensional integral and differential equations using low-parametric rank-structured tensor formats. As the main example, we describe the grid-based tensor numerical approach for solving the 3D nonlinear Hartree-Fock eigenvalue problem, that was the starting point for the developments of tensor-structured numerical methods for large-scale computations in solving real-life multidimensional problems. We also discuss a new method for the fast 3D lattice summation of electrostatic potentials by assembled low-rank tensor approximation capable to treat the potential sum over millions of atoms in few seconds. We address new results on tensor approximation of the dynamical Fokker-Planck and master equations in many dimensions up to d = 20. Numerical tests demonstrate the benefits of the rank-structured tensor approximation on the aforementioned examples of multidimensional PDEs. In particular, the use of grid-based tensor representations in the reduced basis of atomics orbitals yields an accurate solution of the Hartree-Fock equation on large N × N × N grids with a grid size of up to N = 105.

We apply the Tensor Train (TT) decomposition to construct the tensor product Polynomial Chaos Expansion (PCE) of a random field, to solve the stochastic elliptic diffusion PDE with the stochastic Galerkin discretization, and to compute some quantities of interest (mean, variance, exceedance probabilities). We assume that the random diffusion coefficient is given as a smooth transformation of a Gaussian random field. In this case, the PCE is delivered by a complicated formula, which lacks an analytic TT representation. To construct its TT approximation numerically, we develop the new block TT cross algorithm, a method that computes the whole TT decomposition from a few evaluations of the PCE formula. The new method is conceptually similar to the adaptive cross approximation in the TT format, but is more efficient when several tensors must be stored in the same TT representation, which is the case for the PCE. Besides, we demonstrate how to assemble the stochastic Galerkin matrix and to compute the solution of the elliptic equation and its post-processing, staying in the TT format. We compare our technique with the traditional sparse polynomial chaos and the Monte Carlo approaches. In the tensor product polynomial chaos, the polynomial degree is bounded for each random variable independently. This provides higher accuracy than the sparse polynomial set or the Monte Carlo method, but the cardinality of the tensor product set grows exponentially with the number of random variables. However, when the PCE coefficients are implicitly approximated in the TT format, the computations with the full tensor product polynomial set become possible. In the numerical experiments, we confirm that the new methodology is competitive in a wide range of parameters, especially where high accuracy and high polynomial degrees are required., This is a major revision of the manuscript arXiv:1406.2816 with significantly extended numerical experiments. Some unused material is removed

International audience; The global (patch-wise) geometry map, which describes the computational domain, is a new feature in isogeometric analysis. This map has a global tensor structure, inherited from the parametric spline geometry representation. The use of this global structure in the discretization of partial differential equations may be regarded as a drawback at first glance, as opposed to the purely local nature of (high-order) classical finite elements. In this work we demonstrate that it is possible to exploit the regularity of this structure and to identify the great potential for the efficient implementation of isogeometric discretizations. First, we formulate tensor-product B-spline bases as well as the corresponding mass and stiffness matrices as tensors in order to reveal their intrinsic structure. Second, we derive an algorithm for the the separation of variables in the integrands arising in the discretization. This is possible by means of low rank approximation of the integral kernels. We arrive at a compact, separated representation of the integrals. The separated form implies an expression of Galerkin matrices as Kronecker products of matrix factors with small dimensions. This representation is very appealing, due to the reduction in both memory consumption and computation times. Our benchmarks, performed using the C++ library G+Smo, demonstrate that the use of tensor methods in isogeometric analysis possesses significant advantages.

In this paper, we study and implement the structural iterative eigensolvers for the large-scale eigenvalue problem in the Bethe-Salpeter equation (BSE) based on the reduced basis approach via low-rank factorizations in generating matrices, introduced in the previous paper. The approach reduces numerical costs down to $\mathcal{O}(N_b^2)$ in the size of atomic orbitals basis set, $N_b$, instead of practically intractable $\mathcal{O}(N_b^6)$ complexity scaling for the direct diagonalization of the BSE matrix. As an alternative to rank approximation of the static screen interaction part of the BSE matrix, we propose to restrict it to a small active sub-block, with a size balancing the storage for rank-structured representations of other matrix blocks. We demonstrate that the enhanced reduced-block approximation exhibits higher precision within the controlled numerical cost, providing as well a distinct two-sided error estimate for the BSE eigenvalues. It is shown that further reduction of the asymptotic computational cost is possible due to ALS-type iteration in block tensor train (TT) format applied to the quantized-TT (QTT) tensor representation of both long eigenvectors and rank-structured matrix blocks. The QTT-rank of these entities possesses almost the same magnitude as the number of occupied orbitals in the molecular systems, $N_o$, hence the overall asymptotic complexity for solving the BSE problem can be estimated by $\mathcal{O}(\log(N_o) N_o^{2})$. We confirm numerically a considerable decrease in computational time for the presented iterative approach applied to various compact and chain-type molecules, while supporting sufficient accuracy., Comment: 23 pages, 11 figures

We consider an iteration method for solving an elliptic type boundary value problem $\mathcal{A} u=f$, where a positive definite operator $\mathcal{A}$ is generated by a quasi--periodic structure with rapidly changing coefficients (typical period is characterized by a small parameter $\epsilon$) . The method is based on using a simpler operator $\mathcal{A}_0$ (inversion of $\mathcal{A}_0$ is much simpler than inversion of $\mathcal{A}$), which can be viewed as a preconditioner for $\mathcal{A}$. We prove contraction of the iteration method and establish explicit estimates of the contraction factor $q$. Certainly the value of $q$ depends on the difference between $\mathcal{A}$ and $\mathcal{A}_0$. For typical quasi--periodic structures, we establish simple relations that suggest an optimal $\mathcal{A}_0$ (in a selected set of "simple" structures) and compute the corresponding contraction factor. Further, this allows us to deduce fully computable two--sided a posteriori estimates able to control numerical solutions on any iteration. The method is especially efficient if the coefficients of $\mathcal{A}$ admit low rank representations and algebraic operations are performed in tensor structured formats. Under moderate assumptions the storage and solution complexity of our approach depends only weakly (merely linear-logarithmically) on the frequency parameter $1/\epsilon$, providing the FEM approximation of the order of $O(\epsilon^{1+p})$, $p>0$., Comment: 23 pages, 15 figures

In this work, we describe advanced numerical tools for working with multivariate functions and for the analysis of large data sets. These tools will drastically reduce the required computing time and the storage cost, and, therefore, will allow us to consider much larger data sets or finer meshes. Covariance matrices are crucial in spatio-temporal statistical tasks, but are often very expensive to compute and store, especially in 3D. Therefore, we approximate covariance functions by cheap surrogates in a low-rank tensor format. We apply the Tucker and canonical tensor decompositions to a family of Matern- and Slater-type functions with varying parameters and demonstrate numerically that their approximations exhibit exponentially fast convergence. We prove the exponential convergence of the Tucker and canonical approximations in tensor rank parameters. Several statistical operations are performed in this low-rank tensor format, including evaluating the conditional covariance matrix, spatially averaged estimation variance, computing a quadratic form, determinant, trace, loglikelihood, inverse, and Cholesky decomposition of a large covariance matrix. Low-rank tensor approximations reduce the computing and storage costs essentially. For example, the storage cost is reduced from an exponential $\mathcal{O}(n^d)$ to a linear scaling $\mathcal{O}(drn)$, where $d$ is the spatial dimension, $n$ is the number of mesh points in one direction, and $r$ is the tensor rank. Prerequisites for applicability of the proposed techniques are the assumptions that the data, locations, and measurements lie on a tensor (axes-parallel) grid and that the covariance function depends on a distance, $\Vert x-y \Vert$., Comment: 23 pages, 2 diagrams, 2 tables, 9 figures

This is an essentially improved version of the preprint [12]. This manuscript contains all the same numerical experiments, but some inaccuracies in the description of the modeling equations are corrected. Besides, more detailed introduction to the tensor methods is presented. We study the application of the novel tensor formats (TT, QTT, QTT-Tucker) to the solution of d-dimensional chemical master equations, applied mostly to gene regulating networks (signaling cascades, toggle switches, phage- ). For some important cases, e.g. signaling cascade models, we prove good separability properties of the system operator. The Quantized tensor representations (QTT, QTT-Tucker) are employed in both state space and time, and the global state-time (d +1)-dimensional system is solved in the structured form by using the ALS-type iteration. This approach leads to the logarithmic dependence of the computational complexity on the system size. When possible, we compare our approach with the direct CME solution and some previously known approximate schemes, and observe a good potential of the newer tensor methods in simulation of relevant biological systems.

We propose a superfast discrete Haar wavelet transform (SFHWT) as well as its inverse, using the low-rank Quantics-TT (QTT) representation for the Haar transform matrices and input-output vectors. Though the Haar matrix itself does not have a low QTT rank approximation, we show that factor matrices used at each step of the traditional multilevel Haar wavelet transform algorithm have explicit QTT representations of low rank. The SFHWT applies to a vector representing a signal sampled on a uniform grid of size N = 2 d ${N=2^d}$ . We develop two algorithms which roughly require square logarithmic time complexity O ( log 2 N ) ${O(\log ^2 N)}$ with respect to the grid size, hence outperforming the traditional fast Haar wavelet transform (FHWT) of linear complexity O(N). Our approach also applies to the FHWT inverse as well as to the multidimensional wavelet transform. Numerical experiments demonstrate that the SFHWT algorithm is robust in keeping low rank of the resulting output vector and it outperforms the traditional FHWT for grid sizes larger than a certain value depending on the spacial dimension.

We present a tensor-structured method for calculating the Moller–Plesset (MP2) correction to the Hartree–Fock energy with reduced computational cost. The approach originates from the 3D grid-based low-rank factorization of the two-electron integrals tensor performed by the purely algebraic optimization. The computational scheme benefits from fast multilinear algebra implemented on separable representations of transformed two-electron integrals, doubles amplitude tensors, and other fourth order data arrays. The separation rank estimates are discussed. The so-called quantized approximation of the long skeleton vectors comprising tensor factorizations of the main entities allows a reduction in storage costs. A detailed description of tensor algorithms for evaluating the MP2 energy correction is presented. The efficiency of these algorithms is illustrated in the framework of Hartree–Fock calculations for compact molecules, including the amino acids alanine and glycine.

We propose a combined tensor format, which encapsulates the benefits of Tucker, tensor train (TT), and quantized TT (QTT) formats. The structure is composed of subtensors in TT representations, so the approximation problem is proven to be stable. We describe all important algebraic and optimization operations, which are recast to the TT routines. Several examples on explicit function and operator representations are provided. The asymptotic storage complexity is at most cubic in the rank parameter, that is larger than for the global QTT approximation, but the numerical examples manifest that the ranks in the two-level format usually increase more slowly with the approximation accuracy than the QTT ones. In particular, we observe that high rank peaks, which usually occur in the TT/QTT representations, are significantly relaxed. Thus the reduced costs can be achieved.

In this paper, the problem of efficient grid-based computation of the two-electron integrals (TEI) in a general basis is considered. We introduce the novel multiple tensor factorizations of the TEI unfolding matrix which decrease the computational demands for the evaluation of TEI in several aspects. Using the reduced higher-order SVD the redundancy-free product-basis set is constructed that diminishes dramatically the initial number $O(N_b^2)$ of three-dimensional ($3$D) convolutions, defined over cross products of $N_b$ basis functions, to $O(N_b)$ scaling. The tensor-structured numerical integration with the $3$D Newton convolving kernel is performed in one-dimensional ($1$D) complexity, thus enabling high resolution over fine $3$D Cartesian grids. Furthermore, using the quantized approximation of long vectors ensures the logarithmic storage complexity in the grid size. Finally, we present and analyze two approaches to compute the Cholesky decomposition of the TEI matrix based on two types of precomput...

We study the tensor structure of two operations: the transformation of a given multidimensional vector into a multilevel Toeplitz matrix and the convolution of two given multidimensional vectors. We show that the low-rank tensor structure of the input is preserved in the output and propose efficient algorithms for these operations in the newly introduced quantized tensor train (QTT) format. Consider a $d$-dimensional $2n \times\cdots\times 2n$-vector $\boldsymbol{x}$. If it is represented elementwise, the number of parameters is $(2n)^{d}$. However, if we assume that $\boldsymbol{x}$ is given in a QTT representation with ranks bounded by $p$, the number of parameters is reduced to $\mathcal{O}\left(dp^{2} \log n\right)$. Under this assumption we show how the multilevel Toeplitz matrix generated by $\boldsymbol{x}$ can be obtained in the QTT format with ranks bounded by $2p$ in $\mathcal{O}\left(dp^{2} \log n\right)$ operations. We also describe how the convolution $\boldsymbol{x}\star\boldsymbol{y}$ of $\...

The present paper contributes to the construction of a “black-box” 3D solver for the Hartree–Fock equation by the grid-based tensor-structured methods. It focuses on the calculation of the Galerkin matrices for the Laplace and the nuclear potential operators by tensor operations using the generic set of basis functions with low separation rank, discretized on a fine N × N × N Cartesian grid. We prove the C h 2 error estimate in terms of mesh parameter, h = O ( 1 / N ) , that allows to gain a guaranteed accuracy of the core Hamiltonian part in the Fock operator as h → 0 . However, the commonly used problem adapted basis functions have low regularity yielding a considerable increase of the constant C , hence, demanding a rather large grid-size N of about several tens of thousands to ensure the high resolution. Modern tensor-formatted arithmetics of complexity O ( N ) , or even O ( log N ) , practically relaxes the limitations on the grid-size. Our tensor-based approach allows to improve significantly the standard basis sets in quantum chemistry by including simple combinations of Slater-type, local finite element and other basis functions. Numerical experiments for moderate size organic molecules show efficiency and accuracy of grid-based calculations to the core Hamiltonian in the range of grid parameter N 3 ∼ 10 15 .

We propose Fourier transform algorithms using QTT format for data-sparse approximate representation of one- and multi-dimensional vectors (m-tensors). Although the Fourier matrix itself does not have a low-rank QTT representation, it can be efficiently applied to a vector in the QTT format exploiting the multilevel structure of the Cooley-Tukey algorithm. The m-dimensional Fourier transform of an n×⋯×n vector with n=2d has \(\mathcal{O}(m d^{2} R^{3})\) complexity, where R is the maximum QTT-rank of input, output and all intermediate vectors in the procedure. For the vectors with moderate R and large n and m the proposed algorithm outperforms the \(\mathcal{O}(n^{m} \log n)\) fast Fourier transform (FFT) algorithm and has asymptotically the same log-squared complexity as the superfast quantum Fourier transform (QFT) algorithm. By numerical experiments we demonstrate the examples of problems for which the use of QTT format relaxes the grid size constrains and allows the high-resolution computations of Fourier images and convolutions in higher dimensions without the ‘curse of dimensionality’. We compare the proposed method with Sparse Fourier transform algorithms and show that our approach is competitive for signals with small number of randomly distributed frequencies and signals with limited bandwidth.

Tensor-product approximation provides a convenient tool for efficient numerical treatment of high-dimensional problems that arise, in particular, in electronic structure calculations in Rd. In this work we apply tensor approximation to the Galerkin representation of the Newton and Yukawa potentials for a set of tensor-product, piecewise polynomial basis functions. To construct tensor-structured representations, we make use of the well-known Gaussian transform of the potentials, and then approximate the resulting univariate integral in R by special sinc-quadratures. The novelty of the approach lies on the optimisation of the quadrature parameters that allows to reduce dramatically the initial tensor-rank obtained by the standard sinc-quadratures. The numerical experiments show that this approach gives tensor-ranks close to the optimal in 3D computations on large spatial grids and with linear complexity in the univariate grid size. Particularly, this scheme becomes attractive for the multiple calculation of the Yukawa potential when the exponents in Gaussian functions vary during the computational process.

In this paper we propose two schemes of using the so-called quantized tensor train (QTT)-approximation for the solution of multidimensional parabolic problems. First, we present a simple one-step implicit time integration scheme using a solver in the QTT-format of the alternating linear scheme (ALS) type. As the second approach, we use the global space-time formulation, resulting in a large block linear system, encapsulating all time steps, and solve it at once in the QTT-format. We prove the QTT-rank estimate for certain classes of multivariate potentials and respective solutions in $(x,t)$ variables. The log-linear complexity of storage and the solution time is observed in both spatial and time grid sizes. The method is applied to the Fokker--Planck equation arising from the beads-springs models of polymeric liquids.

In the present paper, we give a survey of the recent results and outline future prospects of the tensor-structured numerical methods in applications to multidimensional problems in scientific computing. The guiding principle of the tensor methods is an approximation of multivariate functions and operators relying on a certain separation of variables. Along with the traditional canonical and Tucker models, we focus on the recent quantics-TT tensor approximation method that allows to represent N-d tensors with log-volume complexity, O ( d log N ). We outline how these methods can be applied in the framework of tensor truncated iteration for the solution of the high-dimensional elliptic/parabolic equations and parametric PDEs. Numerical examples demonstrate that the tensor-structured methods have proved their value in application to various computational problems arising in quantum chemistry and in the multi-dimensional/parametric FEM/BEM modeling—the tool apparently works and gives the promise for future use in challenging high-dimensional applications.

We focus on the construction of explicit low-rank representations of matrices in the tensor train (TT) and quantized tensor train (QTT) formats which have been proposed recently for the low-parametric structured representation of large-scale tensors. The matrices under consideration are discretizations of the Laplace operator in a hypercube (in one and many dimensions) and their inverses (in one dimension). For these matrices we derive explicit and exact QTT representations of low QTT ranks independent of the numbers $d$ and $n^{2}$ of dimensions and entries in each dimension. This implies that for the matrices considered the storage cost is $\mathcal{O}\left(d\,\log n\right)$, i.e., logarithmic with respect to the total number $n^{2d}$ of entries. The same applies to the computational complexity of the QTT-structured operations with these matrices, which now depends on the QTT ranks of the other operands. The general result of the paper is the notation and technique we introduce in order to examine the Q...

We investigate approximations by finite sums of products of functions with separated variables to eigenfunctions of multivariate elliptic operators, and especially conditions providing an exponential decrease of the error with respect to the number of terms. The results of the consistent use of tensor formats can be regarded as a base for a new class of iterative eigensolvers with almost linear complexity in the univariate problem size. The results of numerical experiments clearly indicate the linear-logarithmic scaling of low-rank tensor method in the univariate problem size. The algorithms work equally well for the computation of both, minimal and maximal eigenvalues of the discrete elliptic operators.

In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high-dimensional applications. We describe the multifolding or quantics-based tensor approximation method of O(dlog N)-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set {1,…,N}⊗d, or briefly N-d tensors of size Nd, and to the respective discretized differential-integral operators in ℝd. As the basic approximation result, we prove that a complex exponential sampled on an equispaced grid has quantics rank 1. Moreover, a Chebyshev polynomial, sampled over a Chebyshev Gauss–Lobatto grid, has separation rank 2 in the quantics tensor format, while for the polynomial of degree m over a Chebyshev grid the respective quantics rank is at most 2m+1. For N-d tensors generated by certain analytic functions, we give a constructive proof of the O(dlog Nlog e−1)-complexity bound for their approximation by low-rank 2-(dlog N) quantics tensors up to the accuracy e>0. In the case e=O(N−α), α>0, our approach leads to the quantics tensor numerical method in dimension d, with the nearly optimal asymptotic complexity O(d/αlog 2e−1). From numerical examples presented here, we observe that the quantics tensor method has proved its value in application to various function related tensors/matrices arising in computational quantum chemistry and in the traditional finite element method/boundary element method (FEM/BEM). The tool apparently works.

We investigate the convergence rate of approximations by finite sums of rank-1 tensors of solutions of multiparametric elliptic PDEs. Such PDEs arise, for example, in the parametric, deterministic reformulation of elliptic PDEs with random field inputs, based, for example, on the $M$-term truncated Karhunen-Loeve expansion. Our approach could be regarded as either a class of compressed approximations of these solutions or as a new class of iterative elliptic problem solvers for high-dimensional, parametric, elliptic PDEs providing linear scaling complexity in the dimension $M$ of the parameter space. It is based on rank-reduced, tensor-formatted separable approximations of the high-dimensional tensors and matrices involved in the iterative process, combined with the use of spectrally equivalent low-rank tensor-structured preconditioners to the parametric matrices resulting from a finite element discretization of the high-dimensional parametric, deterministic problems. Numerical illustrations for the $M$-dimensional parametric elliptic PDEs resulting from sPDEs on parameter spaces of dimensions $M\leq100$ indicate the advantages of employing low-rank tensor-structured matrix formats in the numerical solution of such problems.

In this paper, the tensor-structured numerical evaluation of the Coulomb and exchange operators in the Hartree-Fock equation is supplemented by the usage of recent quantized-TT (QTT) formats. It leads to O(log n) complexity at computationally extensive stages in the rank-structured calculation with the respective 3D Hartree and exchange potentials discretized on large n×n×n Cartesian grids. The numerical examples for some volumetric organic molecules confirm that the QTT ranks of these potentials are nearly independent of the one-dimension grid size n. Thus, paradoxically, the complexity of the grid-based evaluation of the Coulumb and exchange matrices becomes almost independent of the grid size, being regulated only by the structure of a molecular system. As a result, the grid approximation of the Hartree-Fock equation allows to gain the high resolution with a guaranteed accuracy.

In the present paper, we propose and analyse a class of tensor methods for the efficient numerical computation of the dynamics and spectrum of high-dimensional Hamiltonians. We focus on the complex-time evolution problems. We apply the quantized-TT (QTT) matrix product states type tensor approximation that allows to represent N-d tensors generated by the grid representation of d-dimensional functions and operators with log-volume complexity, O(d log N), where N is the univariate discretization parameter in space. Making use of the truncated Cayley transform method allows us to recursively separate the time and space variables and then introduce the efficient QTT representation of both the temporal and the spatial parts of the solution to the high-dimensional evolution equation. We prove the exponential convergence of the m-term time-space separation scheme and describe the efficient tensor-structured preconditioners for the arising system with multidimensional Hamiltonians. For the class of "analytic" and low QTT-rank input data, our method allows to compute the solution at a fixed point in time t=T>0 with an asymptotic complexity of order O(d log N ln^q (1/ε)), where ε>0 is the error bound and q is a fixed small number. The time-and-space separation method via the QTT-Cayley-transform enables us to construct a global m-term separable (x,t)-representation of the solution on a very fine time-space grid with complexity of order O(dm^4 log N_t log N), where N_t is the number of sampling points in time. The latter allows efficient energy spectrum calculations by FFT (or QTT-FFT) of the autocorrelation function computed on a sufficiently long time interval [0,T]. Moreover, we show that the spectrum of the Hamiltonian can also be represented by the poles of the t-Laplace transform of a solution. In particular, the approach can be an option to compute the dynamics and the spectrum in the time-dependent molecular Schrödinger equation.

In this paper, we describe a novel method for a robust and accurate iterative solution of the self-consistent Hartree-Fock equation in $\mathbb{R}^3$ based on the idea of tensor-structured computation of the electron density and the nonlinear Hartree and (nonlocal) exchange operators at all steps of the iterative process. We apply the self-consistent field (SCF) iteration to the Galerkin discretization in a set of low separation rank basis functions that are solely specified by the respective values on a three-dimensional Cartesian grid. The approximation error is estimated by $O(h^3)$, where $h=O(n^{-1})$ is the mesh size of an $n\times n\times n$ tensor grid, while the numerical complexity to compute the Galerkin matrices scales linearly in $n\log n$. We propose the tensor-truncated version of the SCF iteration using the traditional direct inversion in the iterative subspace scheme enhanced by the multilevel acceleration with the grid-dependent termination criteria at each discretization level. This implies that the overall computational cost scales almost linearly in the univariate problem size $n$. Numerical illustrations are presented for the all electron case of H$_2$O and the pseudopotential case of CH$_4$ and CH$_3$OH molecules. The proposed scheme is not restricted to a priori given rank-1 basis sets, allowing analytically integrable convolution transform with the Newton kernel that opens further perspectives for promotion of the tensor-structured methods in computational quantum chemistry.

In the present paper we present the tensor-product approximation of a multidimensional convolution transform discretized via a collocation-projection scheme on uniform or composite refined grids. Examples of convolving kernels are provided by the classical Newton, Slater (exponential) and Yukawa potentials, 1/@[email protected]?, e^-^@l^@?^x^@? and e^-^@l^@?^x^@?/@[email protected]? with [email protected]?R^d. For piecewise constant elements on the uniform grid of size n^d, we prove quadratic convergence O(h^2) in the mesh parameter h=1/n, and then justify the Richardson extrapolation method on a sequence of grids that improves the order of approximation up to O(h^3). A fast algorithm of complexity O(dR"1R"2nlogn) is described for tensor-product convolution on uniform/composite grids of size n^d, where R"1,R"2 are tensor ranks of convolving functions. We also present the tensor-product convolution scheme in the two-level Tucker canonical format and discuss the consequent rank reduction strategy. Finally, we give numerical illustrations confirming: (a) the approximation theory for convolution schemes of order O(h^2) and O(h^3); (b) linear-logarithmic scaling of 1D discrete convolution on composite grids; (c) linear-logarithmic scaling in n of our tensor-product convolution method on an nxnxn grid in the range [email protected]?16384.

We investigate the convergence rate of the quantics-TT (QTT) stochas- tic collocation tensor approximations to solutions of multiparametric elliptic PDEs and construct efficient iterative methods for solving arising high-dimensional parameter- dependent algebraic systems of equations. Such PDEs arise, for example, in the para- metric, deterministic reformulation of elliptic PDEs with random field inputs, based, for example, on the M-term truncated Karhunen-Loève expansion. We consider both the case of additive and log-additive dependence on the multivariate parameter. The local-global versions of the QTT-rank estimates for the system matrix in terms of the parameter space dimension is proven. Similar rank bounds are observed in numerics for the solutions of the discrete linear system. We propose QTT-truncated iteration based on the construction of solution-adaptive preconditioner that provides robust conver- gence in both additive and log-additive cases. Various numerical tests indicate that the numerical complexity scales almost linearly in the dimension of parametric space M.