Talks

Bachelor-Vortrag

After the introduction of random matrices to nuclear physics by Eugene Wigner in 1955, random quantum systems have grown in popularity. Wigner's idea was to consider families of Hamiltonians that underlie a certain probability distribution to describe overly complicated systems. Of particular interest are, of course, the spectra of these Hamiltonians. In this talk we consider random, in general non-self-adjoint, tridiagonal operators on the Hilbert space of square-summable sequences. To model randomness, we use an approach by Davies that eliminates all probabilistic arguments.

Despite the rising interest, not much is known about the spectra of non-self-adjoint random operators. The Feinberg-Zee random hopping matrix reveals this in a beautiful manner. The boundary of its spectrum appears to be fractal, but a proof has not been found yet. While we can not give a proof either, we present a reason why this is very plausible. Certain tridiagonal operators share remarkable symmetries that allow us to enlarge known subsets of the spectrum by sizeable amounts. In some cases like the Feinberg-Zee random hopping matrix, this implies that the spectrum contains an infinite sequence of Julia sets.

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.