TRR 195 - Algorithms

# TRR 195 - Algorithms

The seminar

TRR 195 - Algorithms

is meant to bring together all algorithmic aspects of the joint project.

## SS 18

Tuesday, 15:30  Room: 436

Topics: various at the intersection of number theory and geometry

1. Christian Eder: PolySolve, 24.4
2. Wolfram Decker: Normalization ala Grauert-Remmert, 8.5.
3. Claus/ Tommy: The Round-2 Method in Number Fields
4. Possibly: The Round-4 Method and friends

Further, less completely scheduled:

• Singularities on Curves (via Janko)
• Singularities on Surfaces (Anne)
• The Ore-Montes method
• Riemann-Roch Spaces:

• Geometric Version ala Isabel
• The Hess Approach
• Tropical ala Andreas G.

• Pascal Schweitzer

## WS 17/18

Tuesday, 15:30  Room: 436

Topics and talks: a mixture of talks mainly around polynomial factorisation.

At this point, this is a suggestion only.

1. (Reimer Behrends, 7.11): Implementing Finite Sets and Relations

This is a survey talk, where we will discuss the various ways in which
we can implement finite sets and relations over finite sets
efficiently. In computer science parlance, this loosely corresponds to
the "searching and sorting" area of topics; however, we will approach
this with the specific needs of mathematicians in mind.

2. Polynomial Factorization over Finite Fields (Raul Epure, 14.11, slides)

In this talk we present one particular strategy for the factorization
of univariate polynomials over finite fields. This strategy splits up
into three stages: squarefree factorization, distinct-degree
factorization and equal-degree factorization. We discuss the
mathematical ideas needed to understand the basic algorithms for each
stage. An efficient algorithm by Kaltofen & Shoup for the
distinct-degree factorization will be presented in detail, since this
stage consumes most of the computation time.

3. Univariate factorisation over Q: Zassenhaus and van Hoeij (Tommy Hofmann, 21.11, slides)

In this talk we will discuss the problem of factoring univariate
polynomials over the rationals, which is a fundamental task in
computer algebra. Starting with a method of Kronecker, we will follow
the development in chronological order, ending with the algorithm of
van Hoeij.
4. Univariate factorisation over number fields: Trager, Zassenhaus and van Hoeij (Claus Fieker, 19.12)

In this talk I will discuss how the methods for factoring over Q can be used to also factor over number fields. Here, we have mainly 2 different possibilities:
- Trager: reduce to the Q case
- discuss lifting problems, leading to a Zassenhaus or van Hoeij type algorithm

5. Dan Roche:  Integer Polynomial Sparse Interpolation with Near-Optimal Complexity
5.12 - after the Xmas party

We investigate algorithms to discover the nonzero coefficients and
exponents of an unknown sparse polynomial, provided a way to evaluate the
polynomial over any modular ring. This problem has been of interest to the
computer algebra community for decades, and its uses include multivariate
polynomial GCD computation, factoring, and sparse polynomial arithmetic.
Starting with the early works of Zippel, Ben-Or and Tiwari, and Kaltofen,
one line of investigation has a key advantage in achieving the minimal
number of evaluations of the polynomial, and has received considerable
attention and improvements over the years. It is closely related to
problems in coding theory and exponential analysis. The downside, however,
is that these methods are not polynomial-time over arbitrary fields. A
separate line of work starting with Garg and Schost and continuing with a
few papers by the speaker and coauthors, has developed a different approach
that works over any finite field. After years of improvements, the
complexity of both approaches over ZZ[x] is currently the same. They scale
well in most aspects except for the degree; the bit complexity in both
cases is currently cubic in the bit-lengths of the exponents. By careful
combination of the techniques in both approaches and a few new tricks, we
are now able to overcome this hurdle. We present an algorithm whose running
time is softly-linear in the size of the output and performs nearly the
minimal number of evaluations of the unknown polynomial. Preliminary
implementation results indicate good promise for practical use when the
unknown polynomial has a moderate number of variables and/or large
exponents.

6. Univariate factorisation over univariate functions fields - bivariate factorisation: Zassenhaus and van Hoeij (Daniel Schultz, 9.1)
7. Classical multivariate over Q
8. Recent Monagan method
9. Allan Steel: Factorisation over finitely presented fields (Conquering inseparability: Primary
decomposition and multivariate factorization over algebraic
function fields of positive characteristic.)
10. Absolute factorisation over Q