BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Boris N. Khoromskij

Boris N. Khoromskij appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NANumerical Analysiscond-mat.stat-mechcond-mat.str-elmath.PR

Catalog footprint

What is connected

15works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2022arXiv

Reduced Higher Order SVD: ubiquitous rank-reduction method in tensor-based scientific computing

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tensor Method for Optimal Control Problems Constrained by Fractional 3D Elliptic Operator with Variable Coefficients

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

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tensor product method for fast solution of optimal control problems with fractional multidimensional Laplacian in constraints

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

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tensor-based techniques for fast discretization and solution of 3D elliptic equations with random coefficients

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Range-separated tensor formats for numerical modeling of many-particle interaction potentials

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A fast iteration method for solving elliptic problems with quasiperiodic coefficients

The paper suggests a preconditioning type method for fast solving of elliptic equations with oscillating quasiperiodic coefficients $A_ε$ specified by the small parameter $ε>0$. We use an iteration method generated by an elliptic operator, associated with a certain simplified (e.g., homogenized) problem. On each step of this procedure it is required to solve an auxiliary elliptic boundary value problem with non--oscillating coefficients $A_0$. All the information related to complicated coefficients of the original differential problem is encompasses in the linear functional, which forms the right hand side of the auxiliary problem. Therefore, explicit inversion of the original operator associated with oscillating coefficients is avoided. The only operation used instead is multiplication of the operator by a vector (vector function), which can be efficiently performed due to the low-rank QTT tensor operations with the rank parameter controlled by the given precision $δ>0$ independent on the parameter $ε$. We deduce two--sided a posteriori error estimates that do not use $A^{-1}_ε$ and provide guaranteed two sided bounds of the distance to the exact solution of the original problem for any step of the iteration process. The second part is concerned with realisations of the iteration method. For a wide class of oscillating coefficients, we obtain sharp QTT rank estimates for the stiffness matrix in tensor representation. In practice, this leads to the logarithmic complexity scaling of the approximation and solution process in both the FEM grid-size, and $O(\vert\logε\vert)$ cost in terms of $ε$. Numerical tests in 1D confirm the logarithmic complexity scaling of our method applied to a class of complicated quasiperiodic coefficients.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A reduced basis approach for calculation of the Bethe-Salpeter excitation energies using low-rank tensor factorizations

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Grid-based lattice summation of electrostatic potentials by assembled rank-structured tensor approximation

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Polynomial Chaos Expansion of random coefficients and the solution of stochastic partial differential equations in the Tensor Train format

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Tensor Numerical Methods in Quantum Chemistry: from Hartree-Fock Energy to Excited States

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Tucker tensor method for fast grid-based summation of long-range potentials on 3D lattices with defects

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Computation of the Response Surface in the Tensor Train data format

We apply the Tensor Train (TT) approximation to construct the Polynomial Chaos Expansion (PCE) of a random field, and solve the stochastic elliptic diffusion PDE with the stochastic Galerkin discretization. We compare two strategies of the polynomial chaos expansion: sparse and full polynomial (multi-index) sets. In the full set, the polynomial orders are chosen independently in each variable, which provides higher flexibility and accuracy. However, the total amount of degrees of freedom grows exponentially with the number of stochastic coordinates. To cope with this curse of dimensionality, the data is kept compressed in the TT decomposition, a recurrent low-rank factorization. PCE computations on sparse grids sets are extensively studied, but the TT representation for PCE is a novel approach that is investigated in this paper. We outline how to deduce the PCE from the covariance matrix, assemble the Galerkin operator, and evaluate some post-processing (mean, variance, Sobol indices), staying within the low-rank framework. The most demanding are two stages. First, we interpolate PCE coefficients in the TT format using a few number of samples, which is performed via the block cross approximation method. Second, we solve the discretized equation (large linear system) via the alternating minimal energy algorithm. In the numerical experiments we demonstrate that the full expansion set encapsulated in the TT format is indeed preferable in cases when high accuracy and high polynomial orders are required.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Tensor Numerical Approach to Linearized Hartree-Fock Equation for Lattice-type and Periodic Systems

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

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Tensor Numerical Methods for High-dimensional PDEs: Basic Theory and Initial Applications

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 $N^d$ with log-volume complexity, $O(d \log 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 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\times N \times N$ grids with a grid size of up to $N= 10^{5}$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Computation of extreme eigenvalues in higher dimensions using block tensor train format

We consider an approximate computation of several minimal eigenpairs of large Hermitian matrices which come from high--dimensional problems. We use the tensor train format (TT) for vectors and matrices to overcome the curse of dimensionality and make storage and computational cost feasible. Applying a block version of the TT format to several vectors simultaneously, we compute the low--lying eigenstates of a system by minimization of a block Rayleigh quotient performed in an alternating fashion for all dimensions. For several numerical examples, we compare the proposed method with the deflation approach when the low--lying eigenstates are computed one-by-one, and also with the variational algorithms used in quantum physics.

0 citations0 reviewsNo code linkedOpen access