Search

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 solution of inhomogeneous partial differential equations by boundary element methods requires the evaluation of volume potentials. A direct standard computation of the classical Newton potentials is possible but expensive. Here, a fast evaluation of the Newton potentials by using the fast multipole method is described and analyzed. In particular, an approximation by the fast multipole method is investigated and related error estimates are given. Furthermore, an indirect evaluation of the normal derivative of the Newton potential is presented. A numerical analysis is presented for all approaches mentioned above. Numerical results are presented for the Poisson equation and for the system of linear elastostatics.

In this paper, we describe and analyze a novel tensor approximation method for discretized multidimensional functions and operators in $\mathbb{R}^d$, based on the idea of multigrid acceleration. The approach stands on successive reiterations of the orthogonal Tucker tensor approximation on a sequence of nested refined grids. On the one hand, it provides a good initial guess for the nonlinear iterations to find the approximating subspaces on finer grids; on the other hand, it allows us to transfer from the coarse-to-fine grids the important data structure information on the location of the so-called most important fibers in directional unfolding matrices. The method indicates linear complexity with respect to the size of data representing the input tensor. In particular, if the target tensor is given by using the rank-$R$ canonical model, then our approximation method is proved to have linear scaling in the univariate grid size $n$ and in the input rank $R$. The method is tested by three-dimensional (3D) electronic structure calculations. For the multigrid accelerated low Tucker-rank approximation of the all electron densities having strong nuclear cusps, we obtain high resolution of their 3D convolution product with the Newton potential. The accuracy of order $10^{-6}$ in max-norm is achieved on large $n\times n\times n$ grids up to $n=1.6\cdot10^4$, with the time scale in several minutes.

A new version of the fast multipole method (FMM) for potential fields is presented. We introduce a new representation of potentials, in which most translation operators are diagonal. As a result, for double precision calculations in two dimensions we obtain an improvement of a factor of two to four in speed, compared to previously published algorithms; the improvement is expected to be much greater in three dimensions. The performance of the method is illustrated with several numerical examples.