On Fast Computations with the Inverse to Harmonic Potential Operators via Domain Decomposition

In this paper a method for fast computations with the inverse to weakly singular, hypersingular and double layer potential boundary integral operators associated with the Laplacian on Lipschitz domains is proposed and analyzed. It is based on the representation formulae suggested for above-mentioned boundary operations in terms of the Poincare-Steklov interface mappings generated by the special decompositions of the interior and exterior domains. Computations with the discrete counterparts of these formulae can be efficiently performed by iterative substructuring algorithms provided some asymptotically optimal techniques for treatment of interface operators on subdomain boundaries. For both two- and three-dimensional cases the computation cost and memory needs are of the order O(N log^p N) and O(N log² N), respectively, with 1 ≤ p ≤ 3, where N is the number of degrees of freedom on the boundary under consideration (some kinds of polygons and polyhedra). The proposed algorithms are well suited for serial and parallel computations.     

Fast solution of three-dimensional elliptic equations with randomly generated jumping coefficients by using tensor-structured preconditioners

In this paper, we propose and analyze the numerical algorithms for fast solution of periodic elliptic problems in random media in ${ℝ}^d$, $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\times L$, or $L\times L\times L$ lattice, respectively. The finite element method discretization procedure on a 3D $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\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$ and the grid-size, $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.