Talks

In this talk, we discuss our recent progress on the famous directed cycle double cover conjecture of Jaeger. We define the class of trigraphs and prove that a graph connections conjecture formulated on trigraphs implies general Jaeger's conjecture. In addition, we give supporting evidence for our conjecture. This is joint work with Martin Loebl.

Given an $n$-element set which contains a known number $d$ of unknown special elements, we are allowed to use an oracle which accepts queries of size $k$ and responds positively if at least one of the elements of the queried set is in our set of unknowns. The case of a single unknown element has been studied and solved in the past by Rényi (1961), Katona (1966) and more recently by Hosszu, Tapolcai and Wiener (2013). We generalise their results in both the adaptive (on-line) and non-adaptive (parallelised) case for general d. Our approach provides new links between separability and (hyper-)graph girth, as well as new bounds for the problem.
This is joint work with F. Benevides, D. Gerbner and C. Palmer.

In Zusammenhang mit der Nullstellenlage von Polynomen welche ausschließlich nichtnegative Koeffizienten aufweisen wurden von Holtz und Tyaglov (SIAM Review, 2012) speziell strukturierte, unendliche Matrizen betrachtet, deren Minoren sämtlich nicht-negativ sind genau dann, wenn das Polynom nur negative Nullstellen besitzt.

Wir werden zum einen diese aufwendige Charakterisierung der
Nullstellenlage von Polynomen deutlich vereinfachen, desweiteren den Satz von Holtz und Tyaglov auf eine Klasse ganzer Funktionen ausweiten sowie den Bezug zu bekannten Klassen total nichtnegativer Matrizen herstellen.

Als mathematische Anwendungen erhalten wir einen einfachen, unabhängigen Beweis der Charakterisierung von Holtz-Tyaglov, eine neue Verknüpungseigenschaft der betrachteten Matrizen sowie eine Charakterisierung der Nullstellenlage spezieller ganzer Funktionen.

We consider the solution of a rather simple class of eigenvalue problems $Ax=\lambda{Mx}$ for symmetric positive definite matrices $A$,$M$ that stem, e.g., from the discretisation of a PDE eigenvalue problem. Thus, the problem is in principle simple, but the matrices $A$ and $M$ are large-scale and we would like to compute all relevant eigenvalues, where relevant is to be understood in the sense that all eigenvalues should be computed that can be captured by the discretisation of the continuous PDE eigenvalue problem.

We propose a new method for the solution of such eigenvalue problems.
The new method combines ideas of domain decomposition, as in the automated multi-level substructuring (short AMLS) or component mode synthesis, with the concept of hierarchical matrices (short $\cal{H}$-matrices) in order to obtain a solver that scales almost linearly (linear up to logarithmic factors) in the size of the discrete space, i.e. the size $N$ of the linear system times the number of sought eigenvectors. Whereas the classical 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 $\cal{H}$-matrix approximation. We will shortly analyse the complexity in theory and practice, and consider several numerical examples that underline the performance of the solver.

We prove that in finite element settings where the divergence-free subspace of the velocity space has optimal approximation properties, the solution of Chorin/Temam projection methods for Navier-Stokes equations equipped with grad-div stabilization with parameter $\gamma$, converge to the associated coupled method solution with rate $\gamma^{-1}$ as $\gamma\rightarrow \infty$. We prove this first for backward Euler schemes, and then extend the results to BDF2 schemes, and finally to schemes with outflow boundary conditions. Several numerical experiments are given which verify the convergence rate, and show how using projection methods in this setting with large grad-div stabilization parameters can dramatically improve accuracy.

Sometimes it is convenient to have a bi-infinite enumeration of the basis elements in the domain and image spaces of an operator A - leading to a representation of A by a bi-infinite matrix.
Shifting one of these enumerations shifts the matrix and hence changes the main diagonal. So which diagonal is ''the'' main diagonal? Isreal Gohberg once diplomatically said that in a bi-infinite matrix, it is every diagonal's right to claim to be the main diagonal. However, there are concrete problems in numerics and in matrix algebra that require a concrete choice - and, as it turns out, the choices coincide: From a certain point of view, there is one distinguished diagonal that deserves being called the main diagonal (a bit more than the others). We show how to find it and we discuss examples.

This is joint work with Gilbert Strang.