Page 57 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 57
INVITED SPEAKERS
function fields and the lines on cubic threefolds will make appearances.
(Based on joint work with A. Forey and J. Fresán)
Fast algorithms from low-rank updates
Daniel Kressner, daniel.kressner@epfl.ch
EPFL, Switzerland
The development of efficient numerical algorithms for solving large-scale linear systems is
one of the success stories of numerical linear algebra that has had a tremendous impact on
our ability to perform complex numerical simulations and large-scale statistical computations.
Many of these developments are based on multilevel and domain decomposition techniques,
which are closely linked to Schur complements and low-rank updates of matrices. In this talk,
we explain how these tools carry over to other important linear algebra problems, including
matrix functions and matrix equations. Fast algorithms are derived from combining divide-
and-conquer strategies with low-rank updates of matrix functions. The convergence analysis of
these algorithms is built on a multivariate extension of the celebrated Crouzeix-Palencia result.
The newly developed algorithms are capable of addressing a wide variety of matrix functions
and matrix structures, including sparse matrices as well as matrices with hierarchical low rank
and Toeplitz-like structures. Their versatility will be demonstrated with several applications
and extensions. This talk is based on joint work with Bernhard Beckermann, Alice Cortinovis,
Leonardo Robol, Stefano Massei, and Marcel Schweitzer.
A proof of the Erdo˝s-Faber-Lovász conjecture
Daniela Kühn, d.kuhn@bham.ac.uk
University of Birmingham, United Kingdom
Coauthors: Dong-Yeap Kang, Tom Kelly, Abhishek Methuku, Deryk Osthus
Graph and hypergraph colouring problems are central to combinatorics, with applications and
connections to many other areas, such as geometry, algorithm design, and information theory.
However, for hypergraphs even basic problems have turned out to be rather challenging: in
particular, the famous Erdo˝s-Faber-Lovász conjecture (posed in 1972) states that the chromatic
index of any linear hypergraph on n vertices is at most n. (Here the chromatic index of a
hypergraph H is the smallest number of colours needed to colour the edges of H so that any
two edges that share a vertex have different colours.) There are also several other equivalent
(dual) versions of this conjecture, e.g. in terms of colouring the vertices of nearly disjoint
cliques. Erdo˝s considered this to be one of his three most favorite combinatorial problems and
offered $500 for the solution of the problem.
In joint work with Dong-yeap Kang, Tom Kelly, Abhishek Methuku and Deryk Osthus, we
prove this conjecture for every large n. We also provide ‘stability versions’ of this result, which
confirm a prediction of Kahn.
In my talk, I will discuss some background, some of the ideas behind the proof as well as
some related open problems.
55
function fields and the lines on cubic threefolds will make appearances.
(Based on joint work with A. Forey and J. Fresán)
Fast algorithms from low-rank updates
Daniel Kressner, daniel.kressner@epfl.ch
EPFL, Switzerland
The development of efficient numerical algorithms for solving large-scale linear systems is
one of the success stories of numerical linear algebra that has had a tremendous impact on
our ability to perform complex numerical simulations and large-scale statistical computations.
Many of these developments are based on multilevel and domain decomposition techniques,
which are closely linked to Schur complements and low-rank updates of matrices. In this talk,
we explain how these tools carry over to other important linear algebra problems, including
matrix functions and matrix equations. Fast algorithms are derived from combining divide-
and-conquer strategies with low-rank updates of matrix functions. The convergence analysis of
these algorithms is built on a multivariate extension of the celebrated Crouzeix-Palencia result.
The newly developed algorithms are capable of addressing a wide variety of matrix functions
and matrix structures, including sparse matrices as well as matrices with hierarchical low rank
and Toeplitz-like structures. Their versatility will be demonstrated with several applications
and extensions. This talk is based on joint work with Bernhard Beckermann, Alice Cortinovis,
Leonardo Robol, Stefano Massei, and Marcel Schweitzer.
A proof of the Erdo˝s-Faber-Lovász conjecture
Daniela Kühn, d.kuhn@bham.ac.uk
University of Birmingham, United Kingdom
Coauthors: Dong-Yeap Kang, Tom Kelly, Abhishek Methuku, Deryk Osthus
Graph and hypergraph colouring problems are central to combinatorics, with applications and
connections to many other areas, such as geometry, algorithm design, and information theory.
However, for hypergraphs even basic problems have turned out to be rather challenging: in
particular, the famous Erdo˝s-Faber-Lovász conjecture (posed in 1972) states that the chromatic
index of any linear hypergraph on n vertices is at most n. (Here the chromatic index of a
hypergraph H is the smallest number of colours needed to colour the edges of H so that any
two edges that share a vertex have different colours.) There are also several other equivalent
(dual) versions of this conjecture, e.g. in terms of colouring the vertices of nearly disjoint
cliques. Erdo˝s considered this to be one of his three most favorite combinatorial problems and
offered $500 for the solution of the problem.
In joint work with Dong-yeap Kang, Tom Kelly, Abhishek Methuku and Deryk Osthus, we
prove this conjecture for every large n. We also provide ‘stability versions’ of this result, which
confirm a prediction of Kahn.
In my talk, I will discuss some background, some of the ideas behind the proof as well as
some related open problems.
55
