Seminar TRR 195 - Algorithms

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

Previous Semesters

Tuesday, 15:30  Room: 48-436

Topic: Numerical Algebraic Geometry

  1. Stavros Papadakis: A Campedelli ZZ/6 algebraic surface construction, 30th Oct
  2. Wolfram Decker: Kinematics and NAG, 13th Nov
  3. Carlo Sircana: Coefficient-Parameter Homotopy, Path Tracking, A7, 20th Nov
  4. Raul Epure: Polynomial Structures, A8, 4th Dec
  5. IRTG-Seminar: Saarbrücken, 11th Dec
  6. NN: Endpoint Estimation, A10
  7. Tommy Hofmann: Basis NAG, A13, 8th Jan
  8. NN: Numer. Irr. Decomp., A15, 15th Jan
  9. NN: Isosingular sets and Deflation, B13, papers, 22nd Jan
  10. NN: Intersection of Algebraic sets, A16, B12, 29th Jan
  11.  Isabel Stenger: Real Solutions, Cell Decomposition, B14, 5th Feb


Tuesday, 15:30  Room: 48-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
  5. Janko Böhm: Adjoint Curves

Further, less completely scheduled:

  • Singularities on Curves (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

 Tuesday, 15:30  Room: 48-436

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

  1. Implementing Finite Sets and Relations(Reimer Behrends, 7.11):
    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 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. Integer Polynomial Sparse Interpolation with Near-Optimal Complexity (Dan Roche, 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, 09.01.)
  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