Search

In this paper, we propose and analyze the numerical algorithms for fast solution of periodic elliptic problems in random media in ℝd$$ {\mathbb{R}}^d $$, d=2,3$$ d=2,3 $$. Both the two‐dimensional (2D) and three‐dimensional (3D) elliptic problems are considered for the jumping equation coefficients built as a checkerboard type configuration of bumps randomly distributed on a large L×L$$ L\times L $$, or L×L×L$$ L\times L\times L $$ lattice, respectively. The finite element method discretization procedure on a 3D n×n×n$$ n\times n\times n $$ uniform tensor grid is described in detail, and the Kronecker tensor product approach is proposed for fast generation of the stiffness matrix. We introduce tensor techniques for the construction of the low Kronecker rank spectrally equivalent preconditioner in a periodic setting to be used in the framework of the preconditioned conjugate gradient iteration. The discrete 3D periodic Laplacian pseudo‐inverse is first diagonalized in the Fourier basis, and then the diagonal matrix is reshaped into a fully populated third‐order tensor of size n×n×n$$ n\times n\times n $$. The latter is approximated by a low‐rank canonical tensor by using the multigrid Tucker‐to‐canonical tensor transform. As an example, we apply the presented solver in numerical analysis of stochastic homogenization method where the 3D elliptic equation should be solved many hundred times, and where for every random sampling of the equation coefficient one has to construct the new stiffness matrix and the right‐hand side. The computational characteristics of the presented solver in terms of a lattice parameter L$$ L $$ and the grid‐size, nd$$ {n}^d $$, in both 2D and 3D cases are illustrated in numerical tests. Our solver can be used in various applications where the elliptic problem should be solved for a number of different coefficients for example, in many‐particle dynamics, protein docking problems or stochastic modeling. [ABSTRACT FROM AUTHOR]

Recent progress in understanding of rank-structured tensor decompositions in HT ht and development of related tensor numerical methods enables efficient techniques for solution of the multidimensional problems in scientific computing and data science, avoiding the curse of dimensionality. The relation between the Tucker ranks and the ranks of the factor matrices in the Tucker decomposition have been derived and then the Tucker completion problem was reformulated as a multilinear low rank matrix completion problem. The low Tucker rank tensor completion problem is considered by Quan Yu et al.,[4] where it is simplified to a low rank approximation of the Tucker unfolding matrices. [Extracted from the article]

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 based on the splitting of the target potential into the short- and long-range components localized in the molecular region by using the range-separated (RS) tensor format [P. Benner, V. Khoromskaia, and B. N. Khoromskij, SIAM J. Comput., 2 (2018), pp. A1034{A1062] for representation of the discretized multiparticle Dirac delta [B. N. Khoromskij, J. Comput. Phys., 401 (2020), 108998] constituting the highly singular right-hand side in the PBE. From the computational point of view our regularization approach requires only the modification of the right-hand side in the PBE so that it can be implemented within any open-source grid-based software package for solving PBE that already includes some FEM/FDM disretization scheme for elliptic PDE and solver for the arising linear system of equations. The main computational benefits are twofold. First, one applies the chosen PBE solver only for the smooth long-range (regularized) part of the collective potential with the regular right-hand side represented by a low-rank RS tensor with a controllable precision. Thus, we eliminate the numerical treatment of the singularities in the right-hand side and do not change the interface and boundary conditions. And second, the elliptic PDE need not be solved for the singular part in the right-hand side at all, since the short-range part of the target potential of the biomolecule is precomputed independently on a computational grid by simple one-dimensional tensor operations. The total potential is then obtained by adding the numerical solution of the PBE for the smooth long-range part to the directly precomputed tensor representation for the short-range contribution. Numerical tests illustrate that the new regularization scheme, implemented by a simple modification of the right-hand side in the chosen PBE solver, improves the accuracy of the approximate solution on rather coarse grids. The scheme also demonstrates good convergence behavior on a sequence of refined grids. [ABSTRACT FROM AUTHOR]

Summary: 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 conjugate gradient 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 Gloria et al. 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. [ABSTRACT FROM AUTHOR]

Highlights • An economical method is introduced for calculating the traces of parametric matrix resolvents. • The method takes advantage of the block-diagonal plus low-rank matrix structure. • This technique avoids the need of stochastic sampling for calculating traces of matrix resolvents. • A regularized DOS can be accurately represented by a low rank quantized tensor train (QTT) interpolation. • The QTT tensor approximation avoids interpolation of DOS by problem independent functions. Abstract 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. [ABSTRACT FROM AUTHOR]

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 represen- tation 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 ∊ Rd, 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×n×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 local support, accomplished by a list of particle coordinates and their charges. The RS canonical/Tucker tensor representations defined on the fine n × n × n Cartesian grid reduce the cost of multilinear algebraic operations on the 3D potential sums, arising in modeling of the multidimensional data by radial basis functions. For instance, computation of the electrostatic potential of a large biomolecule and the interaction energy of a many-particle system, 3D integration and convolution transforms as well as low-parametric fitting of multidimensional scattered data all are reduced to 1D calculations. [ABSTRACT FROM AUTHOR]

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. Direct diagonalisation of the BSE matrix is practically intractable due toO(N6) complexity scaling in the size of the atomic orbital basis set,N. In this paper, we introduce and analyse a reduced basis approach to computation of the Bethe–Salpeter excitation energies which can lead to a relaxation of the numerical costs down toO(N3). The BSE operator is specified in terms of the two-electron integrals in the Hartree–Fock molecular orbital basis and the respective energies, calculated by the tensor-based solver described in previous works. The reduced basis method includes two steps. First, the diagonal plus low-rank approximation to fully populated blocks in the BSE matrix is calculated, enabling an easier partial eigenvalue solver for a large auxiliary system relying only on matrix–vector multiplications with rank-structured matrices. Second, a small subset of eigenvectors from the auxiliary eigenvalue problem is selected to build a projection of the exact BSE system onto this reduced basis set. Numerical tests demonstrate the ϵ-rank bounds for the blocks of the BSE matrix on examples of some compact molecules. The accuracy of the reduced basis approach vs. the effective matrix rank is illustrated. [ABSTRACT FROM PUBLISHER]

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( N L). 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. [ABSTRACT FROM AUTHOR]

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. • Low rank tensor approximation of the discrete fractional multidimensional Laplacian. • Rank-structured preconditioner for iterative solving the equation for control function. • Proof of the existence of low rank tensor decomposition for functions of Laplacian. • The O (n log ⁡ n) -solvers for 3D control problems constrained by fractional Laplacian. [ABSTRACT FROM AUTHOR]

We introduce the tensor numerical method for solving optimal control problems that are constrained by fractional two‐ (2D) and three‐dimensional (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×n×n spacial grids. Using the diagonalization of the arising matrix‐valued functions in the eigenbasis of the one‐dimensional 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 ε‐threshold. This method reduces the numerical cost for solving the control problem to O(nlogn) (plus the quadratic term O(n2) with a small weight), which outperforms traditional approaches with O(n3logn) complexity in the 3D case. The storage for the representation of all 3D nonlocal operators and functions involved is also estimated by O(nlogn). This essentially outperforms the traditional methods operating with fully populated n3×n3 matrices and vectors in ℝn3. Numerical tests for 2D/3D control problems indicate the almost linear complexity scaling of the rank truncated preconditioned conjugate gradient iteration in the univariate grid size n. [ABSTRACT FROM AUTHOR]

In this paper, we propose and study two approaches to approximate the solution of the Bethe–Salpeter equation (BSE) by using structured iterative eigenvalue solvers. Both approaches are based on the reduced basis method and low-rank factorizations of the generating matrices. We also propose to represent the static screen interaction part in the BSE matrix by a small active sub-block, with a size balancing the storage for rank-structured representations of other matrix blocks. We demonstrate by various numerical tests that the combination of the diagonal plus low-rank plus reduced-block approximation exhibits higher precision with low numerical cost, providing as well a distinct two-sided error estimate for the smallest eigenvalues of the Bethe–Salpeter operator. The complexity is reduced to O ( N b 2 ) in the size of the atomic orbitals basis set, N b , instead of the practically intractable O ( N b 6 ) scaling for the direct diagonalization. In the second approach, we apply the quantized-TT (QTT) tensor representation to both, the long eigenvectors and the column vectors in the rank-structured BSE matrix blocks, and combine this with the ALS-type iteration in block QTT format. The QTT-rank of the matrix entities possesses almost the same magnitude as the number of occupied orbitals in the molecular systems, N o < N b , hence the overall asymptotic complexity for solving the BSE problem by the QTT approximation is estimated by O ( log ⁡ ( N o ) N o 2 ) . We confirm numerically a considerable decrease in computational time for the presented iterative approaches applied to various compact and chain-type molecules, while supporting sufficient accuracy. [ABSTRACT FROM AUTHOR]