Talks

One of the most important and frequently used preconditioning techniques for solving symmetric positive definite systems is based on computing the approximate inverse factorizations. It is also a well-known fact that such factors can be computed column-wise by the orthogonalization process applied to the unit basis vectors provided that we use a non-standard inner product induced by the positive definite system matrix A. In this contribution we consider the classical Gram-Schmidt algorithm (CGS), the modified Gram-Schmidt algorithm (MGS) and also yet another variant of sequential orthogonalization, which is motivated originally by the AINV preconditioner and which uses oblique projections.

The orthogonality between computed vectors is crucial for the quality of the preconditioner constructed in the approximate inverse factorization. While for the case of the standard inner product there exists a complete rounding error analysis for all main orthogonalization schemes, the numerical properties of the schemes with a non-standard inner product are much less understood. We will formulate results on the loss of orthogonality and on the factorization error for all previously mentioned orthogonalization schemes.

This contribution is joint work with Jiří Kopal (Technical University Liberec), Miroslav Tůma and Alicja Smoktunowicz (Warsaw University of Technology).

Die von Peter Sonneveld erdachten Methoden, allen voran die neueste, IDR(s), können zur approximativen Eigenwertberechnung linearer Operatoren herangezogen werden. Im Gegensatz zu klassischen Krylovraumverfahren, welche Tridiagonal- oder Hessenbergmatrizen berechnen, berechnen Sonneveld-Methoden Büschel aus einer Band-Hessenbergmatrix und einer oberen Band-Dreiecksmatrix, von denen einige Eigenwerte bekannt sind. Basierend auf einer trivialen Beobachtung präsentieren wir Wege, die anderen Eigenwerte stabil zu berechnen.

Abstract:
We study the Decomposition Conjecture posed by Barát and Thomassen (2006), which states that for every tree T there exists a natural number k_T such that, if G is a k_T-edge-connected graph and |E(T)| divides |E(G)|, then G admits a decomposition into copies of T. This conjecture was verified for stars, some bistars, paths whose length is a power of 2, and paths of length 3. We verify the Decomposition Conjecture for paths of length 5. In this talk I will discuss the ideas behind the proof of this result.

Die von Peter Sonneveld erdachten Methoden, allen voran die neueste, IDR(s), können zur approximativen Eigenwertberechnung linearer Operatoren herangezogen werden. Im Gegensatz zu klassischen Krylovraumverfahren, welche Tridiagonal- oder Hessenbergmatrizen berechnen, berechnen Sonneveld-Methoden Büschel aus einer Band-Hessenbergmatrix und einer oberen Band-Dreiecksmatrix, von denen einige Eigenwerte bekannt sind. Basierend auf einer trivialen Beobachtung präsentieren wir Wege, die anderen Eigenwerte stabil zu berechnen.

Abstract:
The following is NP-hard in general:
given an edge-weighted finite graph and a set of special vertices,
compute a minimum-weight set of edges whose removal disconnects
any special vertex from any other special vertex.
Very efficient algorithms via LP-duality are known for natural subsets of graphs, though,
such as finite trees. Basic theoretical duality-type questions remain open for infinite trees.
To prepare for future talks on the problems about infinite trees,
I will explain an efficient algorithm solving the problem for finite trees.

Die von Peter Sonneveld erdachten Methoden, allen voran die neueste, IDR(s), können zur approximativen Eigenwertberechnung linearer Operatoren herangezogen werden. Im Gegensatz zu klassischen Krylovraumverfahren, welche Tridiagonal- oder Hessenbergmatrizen berechnen, berechnen Sonneveld-Methoden Büschel aus einer Band-Hessenbergmatrix und einer oberen Band-Dreiecksmatrix, von denen einige Eigenwerte bekannt sind. Basierend auf einer trivialen Beobachtung präsentieren wir Wege, die anderen Eigenwerte stabil zu berechnen.

Boundary integral equations are an important tool for analyzing elliptic partial differential equations arising, e.g., in structural mechanics or the simulation of acoustic or electromagnetic fields. Standard discretization techniques lead to large and densely populated matrices that require special algorithms.

The H²-matrix method offers efficient compression schemes for large matrices and can also perform algebraic operations like multiplication, inversion or factorization directly on the compressed matrices.

This talk gives an introduction to the basic concepts of H²-matrices and routlines two recent results: the Green hybrid compression scheme can be used to construct compressed approximations of discretized boundary element systems. Preconditioners for these systems can be constructed by applying a sequence of local low-rank updates to H²-matrices.

The best approximation of a matrix by a low-rank matrix can be obtained by the singular value decomposition. For large-sized matrices this approach is too costly. Instead one may use a block decomposition. Approximating the smaller
block matrices by low-rank matrices and agglomerating them into a new, coarser
block decomposition, one obtains a recursive method. The required computation work is O(rnm) where r is the desired rank and n x m is the size of the matrix. New estimates are presented for the errors A-B and M-A,
where A is the result of the recursive truncation applied to M, while B is the best approximation.

Homogenization theory comprises the study of heterogeneous
materials. In mathematical terms this goes along with the discussion of
differential equations with oscillatory coefficients and the behavior of the
respective solutions, when the oscillations become infinitely fast. The aim in homogenization theory is to show convergence of the solutions for infinitely fast oscillations and to find an effective equation satisfied by the limit. In a Hilbert space setting, we discuss homogenization of ordinary differential equations and give an operator-theoretic reason, when it is likely that the limit equation is of integro-differential type -- in contrast to the equation one started out with. We also discuss possible generalizations to non-autonomous and/or partial differential equations.