Vorträge

Bachelor-Vortrag

Bachelor-Vortrag

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.