Search

Tensor numerical methods, based on the rank-structured tensor representation of $d$-variate functions and operators, are designed to provide $O(dn)$ complexity of numerical calculations on $n^{\otimes d }$ grids contrary to $O(n^d)$ scaling by conventional grid-based methods. However, multiple tensor operations may lead to enormous increase in the tensor ranks (curse of ranks) of the target data, making calculation intractable. Therefore one of the most important steps in tensor calculations is the robust and efficient rank reduction procedure which should be performed many times in the course of various tensor transforms in multidimensional operator and function calculus. The rank reduction scheme based on the Reduced Higher Order SVD (RHOSVD) introduced in [33] played a significant role in the development of tensor numerical methods. Here, we briefly survey the essentials of RHOSVD method and then focus on some new theoretical and computational aspects of the RHOSVD demonstrating that this rank reduction technique constitutes the basic ingredient in tensor computations for real-life problems. In particular, the stability analysis of RHOSVD is presented. We introduce the multilinear algebra of tensors represented in the range-separated (RS) tensor format. This allows to apply the RHOSVD rank-reduction techniques to non-regular functional data with many singularities, for example, to the rank-structured computation of the collective multi-particle interaction potentials in bio-molecular modeling, as well as to complicated composite radial functions. The new theoretical and numerical results on application of the RHOSVD in scattered data modeling are presented. RHOSVD proved to be the efficient rank reduction technique in numerous applications ranging from numerical treatment of multi-particle systems up to a numerical solution of PDE constrained control problems., Comment: 32 pages, 15 figures

The Poisson-Boltzmann equation (PBE) is an implicit solvent continuum model for calculating the electrostatic potential and energies of ionic solvated biomolecules. However, its numerical solution remains a significant challenge due strong singularities and nonlinearity caused by the singular source terms and the exponential nonlinear terms, respectively. An efficient method for the treatment of singularities in the linear PBE was introduced in \cite{BeKKKS:18}, that is based on the RS tensor decomposition for both electrostatic potential and the discretized Dirac delta distribution. In this paper, we extend this regularization method to the nonlinear PBE. We apply the PBE only to the regular part of the solution corresponding to the modified right-hand side via extraction of the long-range part in the discretized Dirac delta distribution. The total electrostatic potential is obtained by adding the long-range solution to the directly precomputed short-range potential. The main computational benefit of the approach is the automatic maintaining of the continuity in the Cauchy data on the solute-solvent interface. The boundary conditions are also obtained from the long-range component of the precomputed canonical tensor representation of the Newton kernel. In the numerical experiments, we illustrate the accuracy of the nonlinear regularized PBE (NRPBE) over the classical variant., Comment: 26 pages, 15 figures

In this paper, we propose and analyze the numerical algorithms for fast solution of periodic elliptic problems in random media in $\mathbb{R}^d$, $d=2,3$. We consider the stochastic realizations using checkerboard configuration of the equation coefficients built on a large $L \times L \times L$ lattice, where $L$ is the size of representative volume elements. The Kronecker tensor product scheme is introduced for fast generation of the stiffness matrix for FDM discretization on a tensor grid. We describe tensor techniques for the construction of the low Kronecker rank spectrally equivalent preconditioner in periodic setting to be used in the framework of PCG iteration. In our construction the diagonal matrix of the discrete Laplacian inverse represented in the Fourier basis is reshaped into a 3D tensor, which is then approximated by a low-rank canonical tensor, calculated by the multigrid Tucker-to-canonical tensor transform. The FDM discretization scheme on a tensor grid is described in detail, and the computational characteristics in terms of $L$ for the 3D Matlab implementation of the PCG iteration are illustrated. The present work continues the developments in [22], where the numerical primer to study the asymptotic convergence rate vs. $L$ for the homogenized matrix for 2D elliptic PDEs with random coefficients was investigated numerically. The presented elliptic problem solver can be applied for calculation of long sequences of stochastic realizations in numerical analysis of 3D stochastic homogenization problems, for solving 3D quasi-periodic geometric homogenization problems, as well as in the numerical simulation of dynamical many body interaction processes and multi-particle electrostatics., Comment: 25 pages, 18 figures.arXiv admin note: text overlap with arXiv:1903.12227

We introduce the tensor numerical method for solving optimal control problems that are constrained by fractional 2D and 3D elliptic operators with variable coefficients. We solve the governing equation for the control function which includes a sum of the fractional operator and its inverse, both discretized over large 3D $n\times n \times n$ spacial grids. Using the diagonalization of the arising matrix valued functions in the eigenbasis of the 1D Sturm-Liouville operators, we construct the rank-structured tensor approximation with controllable precision for the discretized fractional elliptic operators and the respective preconditioner. The right-hand side in the constraining equation (the optimal design function) is supposed to be represented in a form of a low-rank canonical tensor. Then the equation for the control function is solved in a tensor structured format by using preconditioned CG iteration with the adaptive rank truncation procedure that also ensures the accuracy of calculations, given an $\varepsilon$-threshold. This method reduces the numerical cost for solving the control problem to $O(n \log n)$ (plus the quadratic term $O(n^2)$ with a small weight), which is superior to the approaches based on the traditional linear algebra tools that yield at least $O(n^3 \log n)$ complexity in the 3D case. The storage for the representation of all 3D nonlocal operators and functions involved is also estimated by $O(n \log n)$. This essentially outperforms the traditional methods operating with fully populated $n^3 \times n^3$ matrices and vectors in $\mathbb{R}^{n^3}$. Numerical tests for 2D/3D control problems indicate the almost linear complexity scaling of the rank truncated PCG iteration in the univariate grid size $n$., Comment: 46 figures

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

We describe the numerical scheme for the discretization and solution of 2D elliptic equations with strongly varying piecewise constant coefficients arising in the stochastic homogenization of multiscale composite materials. An efficient stiffness matrix generation scheme based on assembling the local Kronecker product matrices is introduced. The resulting large linear systems of equations are solved by the preconditioned CG iteration with a convergence rate that is independent of the grid size and the variation in jumping coefficients (contrast). Using this solver we numerically investigate the convergence of the Representative Volume Element (RVE) method in stochastic homogenization that extracts the effective behavior of the random coefficient field. Our numerical experiments confirm the asymptotic convergence rate of systematic error and standard deviation in the size of RVE rigorously established in [6]. The asymptotic behavior of covariances of the homogenized matrix in the form of a quartic tensor is also studied numerically. Our approach allows laptop computation of sufficiently large number of stochastic realizations even for large sizes of the RVE., Comment: 29 pages, 23 figures

In this paper, we apply the range-separated (RS) tensor format [6] for the construction of new regularization scheme for the Poisson-Boltzmann equation (PBE) describing the electrostatic potential in biomolecules. In our approach, we use the RS tensor representation to the discretized Dirac delta [21] to construct an efficient RS splitting of the PBE solution in the solute (molecular) region. The PBE then needs to be solved with a regularized source term, and thus black-box solvers can be applied. The main computational benefits are due to the localization of the modified right-hand side within the molecular region and automatic maintaining of the continuity in the Cauchy data on the interface. Moreover, this computational scheme only includes solving a single system of FDM/FEM equations for the smooth long-range (i.e., regularized) part of the collective potential represented by a low-rank RS-tensor with a controllable precision. The total potential is obtained by adding this solution to the directly precomputed rank-structured tensor representation for the short-range contribution. Enabling finer grids in PBE computations is another advantage of the proposed techniques. In the numerical experiments, we consider only the free space electrostatic potential for proof of concept. We illustrate that the classical Poisson equation (PE) model does not accurately capture the solution singularities in the numerical approximation as compared to the new approach by the RS tensor format., Comment: 25 pages, 31 figures

We introduce the tensor numerical method for solution of the $d$-dimensional optimal control problems with fractional Laplacian type operators in constraints discretized on large $n^{\otimes 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 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 precomputed. 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$., Comment: 29 pages

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. Second, we show that a regularized or smoothed DOS discretized on a fine grid of size $N$ can be accurately represented by a low rank quantized tensor train (QTT) tensor that can be determined through a least squares fitting procedure. The latter provides good approximation properties for strictly oscillating DOS functions with multiple gaps, and requires asymptotically much fewer ($O(\log N)$) functional calls compared with the full grid size $N$. This approach allows us to overcome the computational difficulties of the traditional schemes by avoiding both the need of stochastic sampling and interpolation by problem independent functions like polynomials etc. 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 which paves the way for treating large-scale spectral problems., Comment: 26 pages, 25 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

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 multi-particle 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 like $1/\|x\|$ 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 range part in the sum is reduced to an independent treatment of $N$ localized terms with almost disjoint effective supports, calculated in $O(N)$ operations. Thus, the cumulated sum of short range clusters is parametrized by a single low-rank canonical reference tensor with a local support, accomplished by a list of particle coordinates and their charges. The RS canonical/Tucker tensor representations reduce the cost of multi-linear algebraic operations on the 3D potential sums arising in modeling of multi-dimensional data by radial basis functions, say, in computation of the electrostatic potential of a protein, in 3D integration and convolution transforms, computation of gradients, forces and the interaction energy of a many-particle systems, and in low parametric fitting of multi-dimensional scattered data by reducing all of them to 1D calculations., Comment: 39 pages, 27 figures

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

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 resume the recent successes of the grid-based tensor numerical methods and discuss their prospects in real-space electronic structure calculations. These methods, based on the low-rank representation of the multidimensional functions and integral operators, led to entirely grid-based tensor-structured 3D Hartree-Fock eigenvalue solver. It benefits from tensor calculation of the core Hamiltonian and two-electron integrals (TEI) in $O(n\log n)$ complexity using the rank-structured approximation of basis functions, electron densities and convolution integral operators all represented on 3D $n\times n\times n $ Cartesian grids. The algorithm for calculating TEI tensor in a form of the Cholesky decomposition is based on multiple factorizations using algebraic 1D ``density fitting`` scheme. The basis functions are not restricted to separable Gaussians, since the analytical integration is substituted by high-precision tensor-structured numerical quadratures. The tensor approaches to post-Hartree-Fock calculations for the MP2 energy correction and for the Bethe-Salpeter excited states, based on using low-rank factorizations and the reduced basis method, were recently introduced. Another direction is related to the recent attempts to develop a tensor-based Hartree-Fock numerical scheme for finite lattice-structured systems, where one of the numerical challenges is the summation of electrostatic potentials of a large number of nuclei. The 3D grid-based tensor method for calculation of a potential sum on a $L\times L\times L$ lattice manifests the linear in $L$ computational work, $O(L)$, instead of the usual $O(L^3 \log L)$ scaling by the Ewald-type approaches.

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\times L \times L$ lattices by using the canonical tensor decompositions and yielding the $O(L)$ computational complexity instead of $O(L^3)$ 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\times N \times 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 $\varepsilon$-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(N L)$. 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., Comment: arXiv admin note: text updated compared with arXiv:1405.2270

This paper introduces and analyses the new grid-based tensor approach for approximate solution of the eigenvalue problem for linearized Hartree-Fock equation applied to the 3D lattice-structured and periodic systems. The set of localized basis functions over spatial $(L_1,L_2,L_3)$ lattice in a bounding box (or supercell) is assembled by multiple replicas of those from the unit cell. All basis functions and operators are discretized on a global 3D tensor grid in the bounding box which enables rather general basis sets. In the periodic case, the Galerkin Fock matrix is shown to have the three-level block circulant structure, that allows the FFT-based diagonalization. The proposed tensor techniques manifest the twofold benefits: (a) the entries of the Fock matrix are computed by 1D operations using low-rank tensors represented on a 3D grid, (b) the low-rank tensor structure in the diagonal blocks of the Fock matrix in the Fourier space reduces the conventional 3D FFT to the product of 1D FFTs. We describe fast numerical algorithms for the block circulant representation of the core Hamiltonian in the periodic setting based on low-rank tensor representation of arising multidimensional functions. Lattice type systems in a box with open boundary conditions are treated by our previous tensor solver for single molecules, which makes possible calculations on large $(L_1,L_2,L_3)$ lattices due to reduced numerical cost for 3D problems. The numerical simulations for box/periodic $(L,1,1)$ lattice systems in a 3D rectangular "tube" with $L$ up to several hundred confirm the theoretical complexity bounds for the tensor-structured eigenvalue solvers in the limit of large $L$., Comment: This manuscript is the improved version of the preprint: V. Khoromskaia, and B.N. Khoromskij. Tensor Approach to Linearized Hartree-Fock Equation for Lattice-type and Periodic Systems. Preprint 62/2014, MPI MiS, Leipzig 2014

We introduce and study a novel tensor approach for fast and accurate assembled summation of a large number of lattice-allocated potentials represented on 3D $N\times N \times N$ grid with the computational requirements only \emph{weakly dependent} on the number of summed potentials. It is based on the assembled low-rank canonical tensor representations of the collected potentials using pointwise sums of shifted canonical vectors representing the single generating function, say the Newton kernel. For a sum of electrostatic potentials over $L\times L \times L$ lattice embedded in a box the required storage scales linearly in the 1D grid-size, $O(N )$, while the numerical cost is estimated by $O(N L)$. For periodic boundary conditions, the storage demand remains proportional to the 1D grid-size of a unit cell, $n=N/L$, while the numerical cost reduces to $O(N)$, that outperforms the FFT-based Ewald-type summation algorithms of complexity $O(N^3 \log N)$. The complexity in the grid parameter $N$ can be reduced even to the logarithmic scale $O(\log N)$ by using data-sparse representation of canonical $N$-vectors via the quantics tensor approximation. For justification, we prove an upper bound on the quantics ranks for the canonical vectors in the overall lattice sum. The presented approach is beneficial in applications which require further functional calculus with the lattice potential, say, scalar product with a function, integration or differentiation, which can be performed easily in tensor arithmetics on large 3D grids with 1D cost. Numerical tests illustrate the performance of the tensor summation method and confirm the estimated bounds on the tensor ranks., Comment: This paper is an essentially improved version of the preprint of the Max-Planck Institute for Mathematics in the Sciences [48]. arXiv admin note: text overlap with arXiv:1411.1994