Inhalt des Dokuments
Kolloquium (Oberseminar)
In our Kolloquium on algorithmic mathematics and complexity theory, guests and members of the group present current topics about their research.
If you are interested in (some of) the talks you are welcome to join us. (For students: Please note that you cannot earn any ECTS!)
Schedule
Usually the talks are on Wednesdays, start at 14:15 and last 60-90 minutes. If not stated otherwise, the Kolloquium takes place in MA 316.
The schedule will be updated regularly.
Speaker | Title | Date | Starts |
---|---|---|---|
Matías Bender | Algorithms for sparse polynomial systems: Gröbner bases and resultants | 23.10.2019 | 14:15 |
Philipp Reichenbach | Bounds on the Weight Margin | 06.11.2019 | 14:15 |
Oliver Gräfvert | Computational complexity in algebraic regression | 13.11.2019 | 14:15 |
Alperen Ergür | Real Polyhedral Homotopy Algorithm | 20.11.2019 | 14:15 |
Dirk Kussin | Real elliptic curves | 27.11.2019 | 14:15 |
Simon Telen | Truncated Normal Forms for Polynomial System Solving | 04.12.2019 | 14:15 |
Daniele Agostini | On the Schottky problem for genus five Jacobians with a vanishing theta null | 11.12.2019 | 14:15 |
Elise Walker | tba | 15.01.2020 | 14:15 |
Mathieu Dutour | tba | 29.01.2020 | 14:15 |
Algorithms for sparse polynomial systems: Gröbner bases and resultants
Speaker: Matías Bender
Polynomial system solving is one of the oldest and most important problem in computational mathematics and has many applications in computer science. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. In this talk, we focus on exploiting the structure related to the sparsity of the supports of the polynomials; that is, we take advantage of the fact that the polynomials only have a few monomials with non-zero coefficients. Our objective is to solve sparse systems faster than the worst case estimates that assume that all the terms are present. We develop algorithms for mixed sparse polynomial systems, that is, systems where the sparsity structure of the polynomials (Newton polytope) is different. We elaborate on two domains of elimination theory: sparse resultants and Gröbner bases. We work on each domain independently, but we also combine them to introduce new algorithms showing for the first time their relation in the sparse setting. We build on the multigraded Castelnuovo-Mumford regularity to develop this relation. We use resultants to propose "optimal" algorithms to solve families of mixed multilinear systems and, for a more general setting, we use Gröbner bases to solve sparse systems avoiding useless computations. The complexity of our algorithms depends on the sparsity structure of the systems (Newton polytopes). Finally, we introduce quasi-optimal algorithms to decompose binary forms.
Bounds on the Weight Margin
Speaker: Philipp Reichenbach
Finding polynomial-time algorithms for the null-cone membership problem is nowadays one of the striving problems in Computational Invariant Theory. In their very recent work [1] Peter Bürgisser et. al. propose analytic 1st and 2nd order methods for solving the null-cone membership problem. Moreover, they provide a complexity analysis of these methods and the main complexity parameter is the so-called weight margin, see [1, Theorems 4.3 and 5.6]. This is a purely discrete measure, that only depends on the weights of the underlying group action.
In this talk we will explain for concrete group actions lower resp. upper bounds on the weight margin. With these bounds we can conclude, when the algorithms provide polynomial resp. at best exponential running time. To do so, we first motivate the null-cone problem, introduce the weight margin and state some complexity results from [1]. Afterwards, we present some bounds on the weight margin and focus on the proof ideas for the upper bounds.
The presented lower bounds are taken from [1], while the upper bounds are ongoing joint work with Cole Franks.
Literature:
[1] P. Bürgisser, C. Franks, A. Garg, R. Oliveira, M. Walter and A. Wigderson. Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes. arXiv 1910.12375v1. 2019.
Computational complexity in algebraic regression
Speaker: Oliver Gräfvert
I will discuss the problem of fitting a variety, coming from a class of varieties, to a configuration of points in space. I will analyse the complexity of this problem using the Euclidean distance degree of an associated variety called the hypothesis variety. For the problem of fitting an n-sphere to a configuration of points, we give a closed formula of the complexity in a special case. For the general case we conjecture a generalization of this formula supported by numerical experiments.
Real Polyhedral Homotopy Algorithm
Speaker: Alperen Ergür
We present a homotopy continuation algorithm for finding real zeros of sparse polynomial systems. The algorithm is based on numerically tracking Viro's patchworking method. It also uses basics of the theory of A-discriminants. Two aspects of the algorithm might be contrasted: on one hand it operates completely over the reals and tracks optimal number of solution paths, on the other hand it solves polynomial systems with certain concavity conditions on the coefficients (a.k.a. patchworked polynomial systems). This is joint work with Timo de Wolff, and it relies on superb coding skills of Sascha Timme.
Real elliptic curves
Speaker: Dirk Kussin
It is well-known that complex smooth projective curves correspond to compact Riemann surfaces. Similarly, real smooth projective curves correspond to the so-called Klein surfaces [1]. The real (=boundary) points form so-called ovals. Ernst Witt [2] studied Klein surfaces with an even number of marked points on each of its ovals. We show that this leads to noncommutative real smooth projective curves, which we call Witt curves. We then consider those curves of Euler characteristic zero (or genus one), the noncommutative real elliptic curves. Prominent commutative examples are the Klein bottle, the Moebius band and the annulus, but there are also not-commutative ones. We will show that the Klein bottle has a (noncommutative) Witt curve as a so-called Fourier-Mukai partner. (This is part of [3].)
Literature:
[1] N. L. Alling and N. Greenleaf, Foundations of the theory of Klein surfaces, Lecture Notes in Mathematics, 219, Springer-Verlag, Berlin-New York, 1971.
[2] E. Witt, Zerlegung reeller algebraischer Funktionen in Quadrate. Schiefkörper über reellem Funktionenkörper, J. Reine Angew. Math., 171 (1934), 4–11.
[3] D. Kussin, Weighted noncommutative regular projective curves, J. Noncommut. Geom. 10 (2016), 1465-1540.
Truncated Normal Forms for Polynomial System Solving
Speaker: Simon Telen
We consider the problem of solving a system of algebraic equations with complex coefficients. We propose robust numerical linear algebra methods for tackling this problem. In order to do so, we define Truncated Normal Forms (TNFs), which provide a general framework for constructing rewriting rules modulo the ideal generated by the input polynomials. We give explicit algorithms for the case where the equations are generic with respect to their degrees or to their Newton polytopes. Several numerical experiments illustrate the effectiveness of the approach. This is joint work with Bernard Mourrain and Marc Van Barel.
On the Schottky problem for genus five Jacobians with a vanishing theta null
Speaker: Daniele Agostini
The Schottky problem asks to recognize Jacobians amongst all abelian varieties and it is one of the central questions in algebraic geometry since the time of Riemann. We will present the state of the art about this problem and we will explain a recent joint work with Lynn Chua where we give a solution to the weak Schottky problem for genus five Jacobians with a vanishing theta null. We will also emphasize how to make this result effective using the software Julia.