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., 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., 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., 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

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., 25 pages, 31 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 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., 26 pages, 25 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., 39 pages, 27 figures

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.

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$., 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

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