Search

In this paper, we consider the Poisson equation on a “long” domain which is the Cartesian product of a one-dimensional long interval with a (d − 1)-dimensional domain. The right-hand side is assumed to have a rank-1 tensor structure. We will present and compare methods to construct approximations of the solution which have tensor structure and the computational effort is governed by only solving elliptic problems on lower-dimensional domains. A zero-th order tensor approximation is derived by using tools from asymptotic analysis (method 1). The resulting approximation is an elementary tensor and, hence has a fixed error which turns out to be very close to the best possible approximation of zero-th order. This approximation can be used as a starting guess for the derivation of higher-order tensor approximations by a greedy-type method (method 2). Numerical experiments show that this method is converging towards the exact solution. Method 3 is based on the derivation of a tensor approximation via exponential sums applied to discretized differential operators and their inverses. It can be proved that this method converges exponentially with respect to the tensor rank. We present numerical experiments which compare the performance and sensitivity of these three methods.

The difference method replaces the derivatives by difference quotients. Section 4.1 describes the difference method applied to the one-dimensional Poisson equation \(-u^{\prime\prime}\;=\;f\). This simple example is chosen to show the generation of the discrete system of equations. The difference equations are complemented by the Dirichlet boundary condition. The equations of the resulting linear system correspond to the inner grid points, while the boundary data appear in the right– hand side of the system.

Here we collect those definitions and statements which are needed in the next chapters. Section 6.1 introduces the normed spaces, Banach and Hilbert spaces as well as the operators as linear and bounded mappings between these spaces. In most of the later applications these spaces will be function spaces, containing for instance the solutions of the differential equations. It will turn out that the Sobolev spaces from Section 6.2 are well suited for the solutions of boundary value problems. The Sobolev space \(H^{k}(\it\Omega)\) and \(H^{k}_{0}(\it\Omega)\) for nonnegative integers k as well as \(H^{s}(\it\Omega)\) for real \(s\geq 0\) are introduced. The definition of the trace (restriction to the boundary Γ) will be essential in §6.2.5 for the interpretation of boundary values. To this end the Sobolev spaces \(H^{s}(\it\Gamma)\) of functions on the boundary Γ must be defined (cf. Theorem 6.57). Sobolev’s Embedding Theorem 6.48 connects Sobolev spaces and classical spaces. Section 6.3 introduces dual spaces and dual mappings. Compactness properties are important for statements about the unique solvability. Compact operators and the Riesz–Schauder theory are presented in Section 6.4. The weak formulation \(H^{s}(\it\Gamma)\) of the boundary-value problem is based on bilinear forms described in Section 6.5. The inf-sup condition in Lemma 6.94 is a necessary and sufficient criterion for the solvability of the weak formulation.

In Section 3.1 the Poisson equation –Δu=f is introduced, and the uniqueness of the solution is proved. The Green function is defined in Section 3.2. It allows the representation (3.6) of the solution, provided it is existing. Concerning the existence, Theorem 3.13 contains a negative statement (cf. Section 3.3): The Poisson equation with a continuous right-hand side f may possess no classical solution. A sufficient condition for a classical solution is the Holder continuity of f as stated in Theorem 3.18. Section 3.4 introduces Green’s function for the ball. In the two-dimensional case, Riemann’s mapping theorem allows the construction of the Green function for a large class of domains. In Section 3.5 we replace the Dirichlet boundary condition by the Neumann condition. The final Section 3.6 is a short introduction into the integral equation method. The solution of the boundary-value problem can indirectly be obtained by solving an integral equation.

The higher-order singular values for a tensor of order $d$ are defined as the singular values of the $d$ different matricizations associated with the multilinear rank. When $d \ge 3$, the singular values are generally different for different matricizations but not completely independent. Characterizing the set of feasible singular values turns out to be difficult. In this work, we contribute to this question by investigating which first-order perturbations of the singular values for a given tensor are possible. We prove that, except for trivial restrictions, any perturbation of the singular values can be achieved for almost every tensor with identical mode sizes. This settles a conjecture from [W. Hackbusch and A. Uschmajew, Numer. Math., 135 (2017), pp. 875--894] for the case of identical mode sizes. Our theoretical results are used to develop and analyze a variant of the Newton method for constructing a tensor with specified higher-order singular values or, more generally, with specified Gramians for th...

The algebraic operations described in Chapter 5 are tools for generating linear iterations. In this chapter we discuss how these tools can be used to build new iterative methods. The product of iterations is recalled in Section 7.1 and refers to later applications in Part III. Many traditional iterations are constructed by the additive splitting technique of Section 7.2. The regular splitting and weakly regular splitting defined in §7.2.2 yield sufficient convergence criteria. Another kind of splitting is the P-regular splitting defined in §7.2.4. A special kind of additive splitting is the incomplete triangular decomposition (ILU) discussed in Section 7.3. The transformations introduced in §5.6 will reappear in Section 7.4 under the name preconditioning.

The semi-iteration comes in three formulations. The first one in Section 8.1 is the most general and associates each semi-iterate with a polynomial. Using the notion of Krylov spaces, we only require that the errors of the semi-iterates \(y^{m}\) be elements of the Krylov space \(x^{0}+N\mathcal {K}_{m}(AN,r^{0})\). In the second formulation of Section 8.2, the polynomials \(p_{m}\) associated with \(y^{m}\) are related either by a two-term or by a three-term recursion. Section 8.3 tries to determine the optimal polynomials. Here the result depends on what quantity we want to minimise. Three minimisation problems are discussed. The last formulation is practically solvable and leads to (transformed) Chebyshev polynomials. The corresponding semi-iteration is called the Chebyshev method (cf. §8.3.4). The Chebyshev method improves the order of convergence. Its convergence speed corresponds to the square root of the spectral condition number (cf. §8.3.5). In Section 8.4 the Chebyshev method is applied to the iterations discussed in Part I. In Section 8.5 we describe the ADI method which is not really of the form discussed above, but it might be seen as a generalisation of semi-iterations (replacing scalar parameters by matrix-valued ones).

In the present survey, we consider a rank approximation algorithm for tensors represented in the canonical format in arbitrary pre-Hilbert tensor product spaces. It is shown that the original approximation problem is equivalent to a finite dimensional l 2 minimization problem. The l 2 minimization problem is solved by a regularized Newton method which requires the computation and evaluation of the first and second derivative of the objective function. A systematic choice of the initial guess for the iterative scheme is introduced. The effectiveness of the approach is demonstrated in numerical experiments.

We propose a possible generalization of Gaussian-type orbital (GTO) bases by means of canonical tensor products. The present work focus on the application of tensor products as an alternative to conventional GTO based density fitting schemes. Tensor product approximation leads to highly nonlinear optimization problems which require sophisticated algorithms. We give a brief description of the optimization problem and algorithm. The present work extends our previous paper [S. R. Chinnamsetty, M. Espig, B. N. Khoromskij, W. Hackbusch and H.-J. Flad, J. Chem. Phys. 127 (2007), 084110], where we discussed tensor product approximations of the electron density and the Hartree potential, to orbital products which are required for the exchange part of Hartree-Fock and in post Hartree-Fock methods. We provide a detailed error analysis for the Coulomb and exchange terms in Hartree-Fock calculations. Furthermore, a comparison is given between all-electron and pseudopotential calculations.

Usually, the fast evaluation of a convolution integral ∫ ℝ f(y)g(x - y)dy requires that the functions f and g have a simple structure based on an equidistant grid in order to apply the fast Fourier transform. Here, we discuss the efficient performance of the convolution of hp-functions in certain locally refined grids. More precisely, the convolution result is projected into some given hp-space (Galerkin approximation). The overall cost is O(p 2 N log N), where N is the sum of the dimensions of the subspaces containing f , g and the resulting function, while p is the maximal polynomial degree.

The Kronecker tensor-product approximation combined with the $\mathcal{H}$-matrix techniques provides an efficient tool to represent integral operators as well as a discrete elliptic operator inverse $A^{-1}\in\mathbb{R}^{N\times N}$ in $\mathbb{R}^{d}$ (the discrete Green's function) with a high spatial dimension $d$. In the present paper we give a survey on modern methods of the structured tensor-product approximation to multidimensional integral operators and Green's functions and present some new results on the existence of low tensor-rank decompositions to a class of function-related operators. The memory space of the considered data-sparse representations is estimated by $\mathcal{O}(dn\log^{q}n)$ with $q$ independent of $d$, retaining the approximation accuracy of order $O(n^{-\delta})$, where $n=N^{1/d}$ is the dimension of the discrete problem in one space direction. In particular, we apply the results to the Newton, Yukawa, and Helmholtz kernels $\frac{1}{|x-y|}$, $\frac{e^{-\lambda|x-y|}}{|x-y|}$, and $\frac{\cos(\lambda|x-y|)}{|x-y|}$, respectively, with $x,y \in \mathbb{R}^{d}$.

Usually, the fast evaluation of a convolution integral $$\int_{{\mathbb{R}}}f(y)g(x-y)\mathrm{d}y$$ requires that the functions f, g are discretised on an equidistant grid in order to apply the fast Fourier transform. Here we discuss the efficient performance of the convolution in locally refined grids. More precisely, the convolution result is projected into some given locally refined grid (Galerkin approximation). Under certain conditions, the overall costs are still $${\mathcal{O}}(N\log N),$$ where N is the sum of the dimensions of the subspaces containing f, g and the resulting function.

In this paper, we discuss the application of hierarchical matrix techniques to the solution of Helmholtz problems with large wave number {kappa} in 2D. We consider the Brakhage–Werner integral formulation of the problem discretized by the Galerkin boundary-element method. The dense n x n Galerkin matrix arising from this approach is represented by a sum of an Formula -matrix and an Formula 2-matrix, two different hierarchical matrix formats. A well-known multipole expansion is used to construct the Formula 2-matrix. We present a new approach to dealing with the numerical instability problems of this expansion: the parts of the matrix that can cause problems are approximated in a stable way by an Formula -matrix. Algebraic recompression methods are used to reduce the storage and the complexity of arithmetical operations of the Formula -matrix. Further, an approximate LU decomposition of such a recompressed Formula -matrix is an effective preconditioner. We prove that the construction of the matrices as well as the matrix-vector product can be performed in almost linear time in the number of unknowns. Numerical experiments for scattering problems in 2D are presented, where the linear systems are solved by a preconditioned iterative method.

The efficiency of hierarchical matrices is based on the approximate evaluation of usual matrix operations. The introduced approximation error may, however, lead to a loss of important matrix properties. In this article we present a technique which preserves the positive definiteness of a matrix independently of the approximation quality. The importance of this technique is illustrated by an elliptic mixed boundary value problem with tiny Dirichlet part. Copyright © 2007 John Wiley & Sons, Ltd.

We consider the Sylvester equation $AX-XB+C=0$, where the matrix $C\in\mathbb{R}^{n\times m}$ is of low rank and the spectra of $A\in\mathbb{R}^{n\times n} $ and $B\in\mathbb{R}^{m\times 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 $\mathcal{O}(n+m)$, or, more precisely, if the solution can be represented with $(n+m)k$ data ($k\sim \log(n+m)$), then the complexity of the algorithm is $\mathcal{O}((n+m)k^{2})$.

In the previous chapters we studied low-rank matrices and model formats with low-rank matrices as matrix blocks. The essential question remains whether and in which cases low-rank matrices may yield a good approximation. In many cases, this property follows from the existence of a separable expansion which is the subject of this chapter.

This article is the second part continuing Part I [16]. We apply the **-matrix techniques combined with the Kronecker tensor-product approximation to represent integral operators as well as certain functions F(A) of a discrete elliptic operator A in a hypercube (0,1) d ∈ ℝ d in the case of a high spatial dimension d. We focus on the approximation of the operator-valued functions A−σ, σ>0, and sign (A) for a class of finite difference discretisations A ∈ ℝN×N. The asymptotic complexity of our data-sparse representations can be estimated by ** (np log qn), p = 1, 2, with q independent of d, where n=N1/d is the dimension of the discrete problem in one space direction.

The Kronecker tensor-product approximation combined with the **-matrix techniques provides an efficient tool to represent integral operators as well as certain functions F(A) of a discrete elliptic operator A in ℝd with a high spatial dimension d. In particular, we approximate the functions A−1 and sign(A) of a finite difference discretisation A∈ℝN×N with a rather general location of the spectrum. The asymptotic complexity of our data-sparse representations can be estimated by ** (np log qn), p = 1, 2, with q independent of d, where n=N1/d is the dimension of the discrete problem in one space direction. In this paper (Part I), we discuss several methods of a separable approximation of multi-variate functions. Such approximations provide the base for a tensor-product representation of operators. We discuss the asymptotically optimal sinc quadratures and sinc interpolation methods as well as the best approximations by exponential sums. These tools will be applied in Part II continuing this paper to the problems mentioned above.

In previous papers, a class of hierarchical matrices (H-matrices) is introduced which are data-sparse and allow an approximate matrix arithmetic of almost optimal complexity. Here, we investigate a new approach to exploit the H-matrix structure for the solution of large scale Lyapunov and Riccati equations as they typically arise for optimal control problems where the constraint is a partial differential equation of elliptic type. This approach leads to an algorithm of linear-logarithmic complexity in the size of the matrices.

Typical panel clustering methods for the fast evaluation of integral operators are based on the Taylor expansion of the kernel function and therefore usually require the user to implement the evaluation of the derivatives of this function up to an arbitrary degree.We propose an alternative approach that replaces the Taylor expansion by simple polynomial interpolation. By applying the interpolation idea to the approximating polynomials on different levels of the cluster tree, the matrix vector multiplication can be performed in only O(npd) operations for a polynomial order of p and an n-dimensional trial space.The main advantage of our method, compared to other methods, is its simplicity: Only pointwise evaluations of the kernel and of simple polynomials have to be implemented.

In boundary element methods, the evaluation of the weakly singular integrals can be performed either a) numerically, b) symbolically, i.e., by explicit expressions, or c) in a combined manner. The explicit integration is of particular interest, when the integrals contain the singularity or if the singularity is rather close to the integration domain. In this paper we describe the explicit expressions for the sixfold volume integrals arising for the Newton potential, i.e., for a 1/r integrand. The volume elements are axi-parallel bricks. The sixfold integrals are typical for the Galerkin method. However, the threefold integral arising from collocation methods can be derived in the same way.

Several types of ℋ-matrices were shown to provide a data-sparse approximation of non-local (integral) operators in FEM and BEM applications. The general construction is applied to the operators with asymptotically smooth kernel function provided that the Galerkin ansatz space has a hierarchical structure. The new class of ℋ-matrices is based on the so-called blended FE and polynomial approximations of the kernel function and leads to matrix blocks with a tensor-product of block-Toeplitz (block-circulant) and rank-k matrices. This requires the translation (rotation) invariance of the kernel combined with the corresponding tensor-product grids. The approach allows for the fast evaluation of volume/boundary integral operators with possibly non-smooth kernels defined on canonical domains/manifolds in the FEM/BEM applications. (Here and in the following, we call domains canonical if they are obtained by translation or rotation of one of their parts, e.g. parallelepiped, cylinder, sphere, etc.) In particular, we provide the error and complexity analysis for blended expansions to the Helmholtz kernel. Copyright © 2002 John Wiley & Sons, Ltd.

An algorithm solving the feedback-vertex-set problem for planar digraphs is described. In particular, planar graphs with a certain additional condition are considered as they arise from solving systems of linear equations obtained from convection-dominated flow problems. The proposed algorithm requires a computational work linear in the size of the graph. Furthermore, a side-product is a decomposition of the graph into subsets that are of interest for block-Gaus-Seidel smoothers in multi-grid methods.

Scattering states with LEED asymptotics are calculated for a general non-muffin tin potential, as e.g. for a pseudopotential with a suitable barrier and image potential part. The latter applies especially to the case of low lying conduction bands. The wave function is described with a reciprocal lattice representation parallel to the surface and a discretization of the real space perpendicular to the surface. The Schroedinger equation leads to a system of linear one-dimensional equations. The asymptotic boundary value problem is confined via the quantum transmitting boundary method to a finite interval. The solutions are obtained basing on a multigrid technique which yields a fast and reliable algorithm. The influence of the boundary conditions, the accuracy and the rate of convergence with several solvers are discussed. The resulting charge densities are investigated., Comment: 5 pages, 4 figures, copyright and acknowledgment added, typos etc. corrected

In this paper we introduce and develop the notion of minimal subspaces in the framework of algebraic and topological tensor product spaces. This mathematical structure arises in a natural way in the study of tensor representations. We use minimal subspaces to prove the existence of a best approximation, for any element in a Banach tensor space, by means of a tensor given in a typical representation format (Tucker, hierarchical, or tensor train). We show that this result holds in a tensor Banach space with a norm stronger than the injective norm and in an intersection of finitely many Banach tensor spaces satisfying some additional conditions. Examples using topological tensor products of standard Sobolev spaces are given.

In the present paper we describe, how to use the Galerkin-method efficiently in solving boundary integral equations. In the first part we show how the elements of the system matrix can be computed in a reasonable time by using suitable coordinate transformations. These techniques can be applied to a wide class of integral equations (including hypersingular kernels) on piecewise smooth surfaces in 3-D, approximated by spline functions of arbitrary degree. In the second part we show, how to use the panel-clustering technique for the Galerkin-method. This technique was developed by Hackbusch and Nowak in [6,7] for the collocation method. In that paper it was shown, that a matrix-vector-multiplication can be computed with a number of $O(n \log^k^+^1n)$ operations by storing $O(n \log^k n)$ sizes. For the panel-clustering-techniques applied to Galerkin-discretizations we get similar asymptotic estimates for the expense, while the reduction of the consumption for practical problems (1 000-15 000 unknowns) turns out to be stronger than for the collocation method.

In this paper, we will present composite boundary elements (CBE) for classical Fredholm boundary integral equations. These new boundary elements allow the low-dimensional discretisation of boundary integral equations where the minimal number of degrees of freedom is independent of the, possibly, huge number of charts which are necessary to describe a complicated surface.The applications are threefold: (a) The coarse-grid discretisation by composite boundary elements allow the use of multigrid algorithms for solving the fine-grid discretisation independently of the number of patches which are necessary to describe the surface. (b) If the accuracy requirements are moderate, the composite boundary elements allow the low-dimensional discretisation of the integral equation. (c) A posteriori error indicators can be applied already to a low-dimensional discretisation, which do not resolve the domain, to obtain a problem-adapted discretisation.

The goal of this work is the presentation of some new formats which are useful for the approximation of (large and dense) matrices related to certain classes of functions and nonlocal (integral, integrodifferential) operators, especially for high-dimensional problems. These new formats elaborate on a sum of few terms of Kronecker products of smaller-sized matrices (cf. [34, 35]). In addition to this we need that the Kronecker factors possess a certain data-sparse structure. Depending on the construction of the Kronecker factors we are led to so-called “profile-low-rank matrices” or hierarchical matrices (cf. [17, 18]). We give a proof for the existence of such formats and expound a gainful combination of the Kronecker-tensor-product structure and the arithmetic for hierarchical matrices. AMS Subject Classification: 65F50, 65F30, 65N38, 65N35, 15A09

The (boundary) integral equation method denotes the transformation of partial differential equations with d spatial variables into an integral equation over a (d-1)-dimensional surface. In §7.4, the method has already been introduced for the two-dimensional Laplace equation. There, results concerning the singular Cauchy kernel were used to find integral equation formulations for the Laplace equation (7.4.1a). According to this approach, the Laplace equation with its close connection to holomorphic functions seems to represent a very particular case (cf. Remark 1.1) and the question remains whether other equations can be treated. The integral equation method or boundary integral method starts from a differential equation Lu = 0 with suitable boundary conditions and looks for an equivalent formulation as integral equation. The numerical treatment of the integral equation, which thus arises, is the subject of the next chapter (§9) entitled «boundary element method».

In the very end of the last century, Erik Ivar Fredholm (Stockholm) investigated those equations, which are now named in honour of him. Together with results of Hilbert, his theory led to the development of functional analysis, which took shape in the beginning of this century.

In §§4.4.2-S and §4.4.7, several possibilities for constructing the discrete analogue K n of an operator K will be described. The general properties of such approximations will be investigated in the following section.

The discretisations derived in Chapter 4 change the Fredholm integral equation into a system of equations. Since this system may consist of a large number of equations involving a full matrix, its solution is not a trivial task. In this chapter, we mainly investigate the solution by the multi-grid method. The multi-grid treatment of equations of the first kind is discussed in §7.3.6 and §9.3.

The following Volterra integral equation of the first kind is due to Abel (1823): $$g(x) = \int\limits_a^x {\frac{{f(y)}} {{\sqrt {x - y} }}dy\;for\;x \geqslant a}$$ (6.1.1) . Since the denominator \(\sqrt {x - y} \) has a zero at y=x, the integral in (1) is to be understood in the improper sense (cf. §6.1.3) and Abel’s integral equation is an example of a weakly singular equation.

To describe the variety of iterative methods applied nowadays, one needs further techniques producing new iterations from already known ones or introducing new features. Techniques of the former kind are the transformations described in §§8.1–3 and the composed methods from §8.4 generated by a secondary iteration, whereas the ILU decomposition from §8.5 is of the latter kind, since it produces a new method.

Various iterative methods can be classified as domain decomposition methods. Although a prototype of this iteration due to H. A. Schwarz (Viertelsjahresschrift der Naturforschenden Gesellschaft in Zurich, Vol. 15, 1870) is already 120 years old, this class of algorithms has attracted the interest of numerical analysts only recently.

We have studied an iterative perturbative approach to optimize Jastrow factors in quantum Monte Carlo calculations. For an initial guess of the Jastrow factor we construct a corresponding model Hamiltonian and solve a first-order perturbation equation in order to obtain an improved Jastrow factor. This process is repeated until convergence. Two different types of model Hamiltonians have been studied for both energy and variance minimization. Our approach can be considered as an alternative to Newton’s method. Test calculations revealed the same fast convergence as for Newton’s method sufficiently close to the minimum. However, for a poor initial guess of the Jastrow factor, the perturbative approach is considerably more robust especially for variance minimization. Usually only two iterations are sufficient in order to achieve convergence within the statistical error. This is demonstrated for energy and variance minimization for the first row atoms and some small molecules. Furthermore, our perturbation an...

Invited Papers.- Multigrid Methods for Steady Euler- and Navier-Stokes Equations Based on Polynomial Flux-Difference Splitting.- Recent Developments for the PSMG Multiscale Method.- An adaptive multigrid approach for the solution of the 2D semiconductor equations.- Multiscale Monte Carlo Algorithms in Statistical Mechanics and Quantum Field Theory.- Two Fast Solvers Based on the Multi-Level Splitting of Finite Element Spaces.- Multigrid Methods for Turbulent Flow Problems.- A survey of Fourier smoothing analysis results.- Contributed Papers.- Multilevel Methods for Fast Solution of N-Body and Hybrid Systems.- Parabolic Multigrid Revisited.- Time-Parallel Multigrid Solution of the Navier-Stokes Equations.- Solution of 3-D Problems using Overlapping Grids and Multi-Grid Methods.- A Multigrid Method for the Solution of a Convection - Diffusion Equation with Rapidly Varying Coefficients.- Parallel Multigrid Solution of 2D and 3D Anisotropic Elliptic Equations: Standard and Nonstandard Smoothing.- Parallel Multigrid Methods on Sparse Grids.- Analysis of multigrid methods for general systems of PDE.- On the convergence of the nonlinear multigrid algorithm for potential operators.- A Multigrid Algorithm with Time-Dependent, Locally Refined Grids for Solving the Nonlinear Diffusion Equation on a Nonrectangular Geometry.- Multigrid Methods for Hyperbolic Equations.- Low-Diffusion Rotated Upwind Schemes, Multigrid and Defect Correction for Steady, Multi-Dimensional Euler Flows.- Multigrid Convergence Acceleration for Complex Flow Including Turbulence.- Time Accurate Multigrid Solutions of the Navier-Stokes Equations.- Mesh-Adaptive Solution of the Navier-Stokes Equations.- A two-grid analysis of the combination of mixed finite elements and Vanka-type relaxation.- Multigrid Applied to Mixed Finite Element Schemes for Current Continuity Equations.- Adaptive Higher Order Multigrid Methods.- Shape from Shading using Parallel Multigrid Relaxation.- Cell-centered Multigrid Methods in Porous Media Flow.- Multigrid Waveform Relaxation for Solving Parabolic Partial Differential Equations.

Tensor product decompositions with optimal separation rank provide an interesting alternative to traditional Gaussian-type basis functions in electronic structure calculations. We discuss various applications for a new compression algorithm, based on the Newton method, which provides for a given tensor the optimal tensor product or so-called best separable approximation for fixed Kronecker rank. In combination with a stable quadrature scheme for the Coulomb interaction, tensor product formats enable an efficient evaluation of Coulomb integrals. This is demonstrated by means of best separable approximations for the electron density and Hartree potential of small molecules, where individual components of the tensor product can be efficiently represented in a wavelet basis. We present a fairly detailed numerical analysis, which provides the basis for further improvements of this novel approach. Our results suggest a broad range of applications within density fitting schemes, which have been recently successfully applied in quantum chemistry.

A new variant of the multi-grid algorithms is presented. It uses multiple coarse-grid corrections with particularly associated prolongations and restrictions. In this paper the robustness with respect to anisotropic problems is considered.

Multi-grid methods are characterized by the simultaneous use of additional auxiliary grids corresponding to coarser step widths. Contrary to usual iterative methods the speed of convergence is very fast and does not tend to one if the step size approaches zero. The computational amount of one iteration is proportional toN, the number of grid points. Thus, a solution with accuracy ɛ requires 0 (|log ɛ|N) operations. In this paper we apply a multi-grid method to Helmholtz's equation (Dirichlet boundary data) in a general region and to a differential equation with variable coefficients subject to arbitrary boundary conditions.

In this paper, we present a new algorithm that is obtained by introducing a damping parameter in the classical Nonlinear Multilevel Method. We analyse this Damped Nonlinear Multilevel Method. In particular, we prove global convergence and local efficiency for a suitable class of problems.

So far there has been no analysis of multigrid methods applied to singularly perturbed Dirichlet boundary-value problems. Only for periodic boundary conditions does the Fourier transformation (mode analysis) apply, and it is not obvious that the convergence results carry over to the Dirichlet case, since the eigenfunctions are quite different in the two cases. In this paper we prove a close relationship between multigrid convergence for the easily analysable case of periodic conditions and the convergence for the Dirichlet case.

An operator L = L(e) depending on a parameter e is called singularly perturbed if the limiting operator \(L(0) = \begin{array}{*{20}{c}} {\lim } \\ {\varepsilon \to 0} \end{array}L(\varepsilon )\) is of a type other than L(e) for e > 0. For instance, an elliptic operator L(e) = e L I + L II (e > 0) is singularly perturbed if L II is non-elliptic or elliptic of a lower order. Different types of L II give rise to the subsections 10.1–3.

A multi-grid iteration is described, which approximates simultaneously k eigenvalues and the associated vectors. The matrix may be unsymmetric or even not diagonalisable. The algorithm is based on a Newton iteration converging to a kxk sub-matrix of the Schur normal form.

The complete multi-grid process will be developed in three stages (§ 3: two-grid iteration, § 4: multi-grid iteration, § 5: nested iteration). The two-grid algorithm serves only as an (impractical) illustration preparing for the multi-grid method which might seem intricate if introduced at once. Although the multi-grid iteration of § 4 is already effective, it can still be improved by the nested iteration (§ 5).

A natural model of an elliptic equation is the two-dimensional Poisson equation in a square. Unfortunately, the analysis of the multi-grid algorithm for this problem is still an involved exercise. Therefore, we start with the simplest one-dimensional Dirichlet boundary value problem $$ - u''\left( x \right) = f\left( x \right)in\Omega = \left( {0,1} \right)u\left( x \right) = 0atx \in \Gamma = \left\{ {0,1} \right\}$$ (2.1.1) .

In this chapter we investigate operator equations and inequalities for functions of one real variable. Our particular objective here is nonlinear Volterra integral equations and ordinary differential equations. Unless explicitly stated otherwise, the Lebesgue concept of integral is always presupposed. As for the results for ordinary differential equations, they are obtained via the corresponding integral equations and therefore also hold for differential equations in the generalized sense of Caratheodory. In the second chapter we will handle ordinary differential equations with a different method, which puts differential equations in the foreground. Then the concept of a classical solution is basic. In this case the differential equations and differential inequalities under consideration must be satisfied at every point (and not just almost everywhere).