## Sekundärnavigation / Secondary navigation

- Main Page
- Members
- Secretaries
- Professors
- Lecturers
- Scientific Assistants
- Postdocs and Phd Students
- Former Members

- Lehre
- Talks
- Guests
- Workshops
- Guest Information
- Information for High School Students (in German only)

# Login

## Inhaltsbereich / Content

# TRR 195 - Algorithms

The seminar

TRR 195 - Algorithms

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

## 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.

- (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. - 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. - 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.

- 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 - 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. - Univariate factorisation over univariate functions fields - bivariate factorisation: Zassenhaus and van Hoeij (Daniel Schultz, 9.1)
- Classical multivariate over Q
- Recent Monagan method
- Allan Steel: Factorisation over finitely presented fields (Conquering inseparability: Primary

decomposition and multivariate factorization over algebraic

function fields of positive characteristic.) - Absolute factorisation over Q