Zur Hauptnavigation / To main navigation

Zur Sekundärnavigation / To secondary navigation

Zum Inhalt dieser Seite / To the content of this page

Hauptnavigation / Main Navigation

Sekundärnavigation / Secondary navigation

TRR 195 - Algorithms

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.

  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