MATHEON Workshop on Computational Partial Differential Equations

Date
06.06.2007
Place
HU Berlin-Adlershof, Rudower Chaussee 25
Humboldt-Kabinett
between the houses 3 and 4, first level

Schedule

10.15-11.15Andrew Knyazev
(Denver, Colorado, USA)
New A Priori FEM Error Estimates for Eigenvalues abstract
notes
11.30-12.30Ricardo Duran
(Buenos Aires, Argentina)
Finite element approximation of eigenvalue problems abstract
12.30-15.00Lunch
15.00-16.00Wolfgang Hackbusch
(Leipzig, Germany)
Evaluation of convolution integrals involving locally refined hp-finite element functions abstract
presentation
16.05-17.00Lars Grasedyck
(Leipzig, Germany)
Hierarchical Matrix Approximation for the Discretisation and Solution of Partial Differential and Integral Equations abstract
presentation

Organizers

S. Brenner Louisiana State University
C. CarstensenHU Berlin
W. HackbuschMax-Planck-Institut Leipzig
R. KornhuberFU Berlin
V. MehrmannTU Berlin
H. YserentantTU Berlin

Abstracts for the Talks

Ricardo Duran (Buenos Aires, Argentina)
Finite element approximation of eigenvalue problems

We discuss several topics in the numerical approximation of eigenvalues and eigenfunctions. For simplicity we consider the Laplace equation although the results are also valid for more general elliptic problems. It is known that the standard finite element method produces upper approximations of the eigenvalues. Therefore, a natural question is whether it is possible to obtain lower bounds by using other methods. We recall old results obtained in this direction in the context of finite differences and present some results obtained by using numerical integration and non-conforming methods. Finally we introduce and analyze a posteriori error estimators both for standard and non-conforming methods and present some numerical examples.

Lars Grasedyck (Leipzig, Germany)
Hierarchical Matrix Approximation for the Discretisation and Solution of Partial Differential and Integral Equations
(download notes)

The efficient discretisation of (linear) integral equations consists of three different tasks: the construction of a suitable trial space where the solution is sought, the computation of the entries of the stiffness matrix --- typically involving cubature formulae for singular integrals --- and a compression of the matrix in order to avoid the quadratic cost for the storage and setup of the fully populated stiffness matrix. In the first part of this talk we will focus on the third task, namely the matrix compression. We use the hierarchical matrix format to store the stiffness matrix in a data-sparse format and apply an algebraic recompression technique that aims at finding an optimal format for the storage and evaluation of the matrix. This recompression technique is at the same time useful to speed up the standard hierarchical matrix arithmetic that is used for the solution of the discrete system. In the second part of the talk the hierarchical matrix technique for non-local operators is applied to decompose the sparse Galerkin stiffness matrix of a second order elliptic operator into a product of triangular matrices. The triangular factors are stored in the hierarchical matrix format so that the decomposition and solution of the triangular systems can be done in almost linear complexity.

Wolfgang Hackbusch (Leipzig, Germany)
Evaluation of convolution integrals involving locally refined hp-finite element functions
(download presentation)

Let f and g be functions of an hp-element space in R with bounded support. Here, an hp-element space is characterised by local grid sizes h_l=2^{-l}*h (l: refinement level). On each subinterval the functions are polynomials of degree \leq p (no continuity between the subintervals required). The convolution f*g is the integral of f(y)g(x-y)dy over R. Its (exact) orthogonal L2 projection into an hp-element space is to be computed. We describe the algorithm which has the complexity O(p2*N*log(N)). Here, N is the number of all subintervals involved in the description of the factors f,g and of the result, p is the maximal polynomial degree.

Andrew Knyazev (Denver, Colorado, USA)
New A Priori FEM Error Estimates for Eigenvalues
(download notes)

We analyze the Ritz-Galerkin method for symmetric eigenvalue problems and prove a priori eigenvalue error estimates. For a simple eigenvalue, we prove an error estimate that depends mainly on the approximability of the corresponding eigenfunction and provide explicit values for all constants. For a multiple eigenvalue we prove, in addition, apparently the first truly a priori error estimates that show the levels of the eigenvalue errors depending on approximability of eigenfunctions in the corresponding eigenspace. These estimates re┬░ect a known phenomenon that different eigenfunctions in the corresponding eigenspace may have different approximabilities, thus resulting in different levels of errors for the approximate eigenvalues. For clustered eigenvalues, we derive eigenvalue error bounds that do not depend on the width of the cluster. Our results are readily applicable to the classical Ritz method for compact symmetric integral operators and to finite element method eigenvalue approximation for symmetric positive definite differential operators.