Search

We propose a new method for the solution of discretised elliptic PDE eigenvalue problems. The new method combines ideas of domain decomposition, as in the automated multi-level substructuring (short AMLS), with the concept of hierarchical matrices (short $$\fancyscript{H}$$ -matrices) in order to obtain a solver that scales almost optimal in the size of the discrete space. Whereas the AMLS method is very effective for PDEs posed in two dimensions, it is getting very expensive in the three-dimensional case, due to the fact that the interface coupling in the domain decomposition requires dense matrix operations. We resolve this problem by use of data-sparse hierarchical matrices. In addition to the discretisation error our new approach involves a projection error due to AMLS and an arithmetic error due to $$\fancyscript{H}$$ -matrix approximation. A suitable choice of parameters to balance these errors is investigated in examples. [ABSTRACT FROM AUTHOR]

Abstract: We derive and analyse a scheme for the approximation of order d tensors in the hierarchical (-) Tucker format, a dimension-multilevel variant of the Tucker format and strongly related to the TT (tensor train) format. For a fixed rank parameter k, the storage complexity of a tensor in -Tucker format is and we present a (heuristic) algorithm that finds an approximation to a tensor in the -Tucker format in by inspection of only entries. Under mild assumptions, tensors in the -Tucker format are reconstructed. For general tensors we derive error bounds that are based on the approximability of matrices (matricizations of the tensor) by few outer products of its rows and columns. The construction parallelizes with respect to the order d and we also propose an adaptive approach that aims at finding the rank parameter for a given target accuracy automatically. [Copyright &y& Elsevier]

SUMMARY In this paper, we propose a method for the numerical solution of linear systems of equations in low rank tensor format. Such systems may arise from the discretisation of PDEs in high dimensions, but our method is not limited to this type of application. We present an iterative scheme, which is based on the projection of the residual to a low dimensional subspace. The subspace is spanned by vectors in low rank tensor format which-similarly to Krylov subspace methods-stem from the subsequent (approximate) application of the given matrix to the residual. All calculations are performed in hierarchical Tucker format, which allows for applications in high dimensions. The mode size dependency is treated by a multilevel method. We present numerical examples that include high-dimensional convection-diffusion equations.Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We consider the Sylvester equation AX -XB+C = 0, where the matrix C ϶ Rn×m is of low rank and the spectra of A ϶ Rn×n and B ϶ Rm×m are separated by a line. The solution X can be approximated in a data-sparse format, and we develop a multigrid algorithm that computes the solution in this format. For the multigrid method to work, we need a hierarchy of discretizations. Here the matrices A and B each stem from the discretization of a partial differential operator of elliptic type. The algorithm is of complexity O(n+m), or, more precisely, if the solution can be represented with (n + m)k data (k ∼ log(n + m)), then the complexity of the algorithm is O((n + m)k2). [ABSTRACT FROM AUTHOR]

Hierarchical matrices provide a data-sparse way to approximate fully populated matrices. In this paper we exploit H-matrix techniques to approximate the LU-decompositions of stiffness matrices as they appear in (finite element or finite difference) discretizations of convectiondominated elliptic partial differential equations. These sparse H-matrix approximations may then be used as preconditioners in iterative methods. Whereas the approximation of the matrix inverse by an H-matrix requires some modification in the underlying index clustering when applied to convectiondominant problems, the H-LU-decomposition works well in the standard H-matrix setting even in the convection dominant case. We will complement our theoretical analysis with some numerical examples. [ABSTRACT FROM AUTHOR]