Sage-FLINT Days schedule

Friday 16 | arrival, no activities planned |

Saturday 17 | |

10:00 - 11:00 | registration and coffee and tea |

11:00 - 11:30 | welcome address by Bill Hart, including introduction to FLINT |

11:30 - 12:30 | coding sprint coordination |

12:30 - 13:30 | lunch (provided) |

13:30 - 14:30 | Fredrik Johansson - Fast Special Functions We discuss techniques used in FLINT to enable asymptotically fast and practically efficient computation of various special functions, polynomials and number sequences of interest in number theory. Among the highlights in the upcoming version of FLINT is a new implementation of the partition function p(n), running 500 times faster than the previous best available implementations (Mathematica and Sage). The code has been used to compute p(10^19) and to determine 22 billion new congruences for the partition function. |

14:35 - 15:30 | Mike Hansen - How to write code for Sage (experienced Sage developers might choose to go elsewhere for coding and collaboration) |

15:30 - 16:00 | tea and coffee |

16:00 - 17:00 | Simon King - How to implement new algebraic structures in Sage: Sage's category and coercion framework Sage's main programming language is Python. Algebraic code in base |

17:00 - 18:30 | coding and collaboration |

18:30 - 19:30 | dinner (provided) |

19:30 - late | coding and collaboration (room is available until at least 22:00) |

Sunday 18 | |

9:00 - 10:30 | coding and collaboration |

10:30 - 11:00 | coffee and tea |

11:00 - 12:00 | Andy Novocin - L1, a quasi-linear LLL algorithm The LLL lattice reduction algorithm of 1982 has proven to be useful in a wide variety of fields. It can be used to approximately solve computationally difficult lattice-based problems, such as the shortest vector problem, in polynomial time. We present a new algorithm for lattice reduction which is the first algorithm to have a complexity bound which is both polynomial and quasi-linear in the bit-length of the input. To achieve this we present an independently interesting toolkit for analyzing incremental lattice reductions. |

12:00 - 12:30 | coding sprint status reports |

12:30 - 13:30 | lunch (provided) |

13:30 - 14:30 | Arne Storjohann - Some ideas for efficient implementation of polynomial matrix computations In this talk I'll survey some ideas for realizing efficient implementations of algorithms for polynomial matrix computations. These include linearization to transform to a problem on scalar matrices, partial linearization to smooth the degrees of entries in an input matrix, and exploiting different representations such as radix expansions, evaluations at sets of points, and combinations of both of these representations. |

14:30 - 15:30 | coding and collaboration |

15:30 - 16:00 | tea and coffee |

16:00 - 18:30 | coding and collaboration |

18:30 - 19:30 | dinner (provided) |

19:30 - late | coding and collaboration (room is available until at least 22:00) |

Monday 19 | MIR@W Day |

9:00 - 11:30 | coding and collaboration, including coffee and tea at 10:30 |

11:30 - 12:00 | coding sprint status reports, parallel: registration and arrival for MIR@W Day |

12:00 - 13:00 | lunch (provided) |

13:00 - 13:30 | John Cremona - Sage as a research tool |

13:30 - 14:20 | Martin Albrecht - Linear Algebra over Dense Matrices over GF(2) and Small Extensions Linear algebra over GF(2) and GF(2^e) where e is a small integer has many applications such as cryptography and coding theory. Since matrices over these base fields can be efficiently bit-packed, dense techniques are often feasible for considerable matrix sizes beyond 100,000 x 100,000. In this talk we will present our work on matrices over these fields and discuss algorithms, implementation techniques, recurring themes and what performance we achieved so far in the M4RI(E) libraries. |

14:20 - 14:35 | short break |

14:35 - 15:25 | Nick Hale - A Brief Introduction to Chebfun Chebfun is a collection of algorithms and an open-source software system in object-oriented MATLAB which extends familiar powerful methods of numerical computation involving numbers to continuous or piecewise-continuous functions. The mathematical basis of the system combines tools of Chebyshev expansions, fast Fourier transform, barycentric interpolation, recursive zero-finding, and automatic differentiation. In this talk we'll see a brief introduction to the software, exploring some of its fundamental concepts and mathematical/algorithmic foundations, as well some more advanced examples of what its capable of. |

15:25 - 16:15 | Nigel Smart - Fully Homomorphic Encryption The big story in theoretical cryptography over the last couple of years has been the discovery of various fully homomorphic encryption schemes. In this talk I will introduce these schemes, and show how they motivate the application of a number of classical results from algebraic number theory. |

16:15 - 16:40 | tea and coffee |

16:40 - 17:30 | Paul Zimmermann - CADO-NFS: integer factorization with the Number Field Sieve CADO-NFS (http://cado-nfs.gforge.inria.fr/) is a complete implementation in C/C++ of the Number Field Sieve (NFS) algorithm for factoring integers. It consists in various programs corresponding to all the phases of the algorithm, and a general perl script that runs them, possibly in parallel over a network of computers. CADO-NFS is distributed under the Gnu Lesser General Public License (LGPL) version 2.1 (or any later version). In this talk, we will describe the status of the current release (1.1) of CADO-NFS, and compare its strengths or weaknesses with respect to other NFS software. |

17:30 - 18:00 | Bruce Westbury - Ribbon graphs, planar maps and circle packing |

18:00 - late | coding and collaboration, and time to go out for dinner (room is available until at least 22:00) |

Tuesday 20 | |

9:00 - 10:30 | coding and collaboration |

10:30 - 11:00 | coffee and tea |

11:00 - 12:00 | David Harvey - Faster arithmetic for number-theoretic transforms I will describe some techniques for speeding up number-theoretic transforms (discrete Fourier transforms over finite fields) on modern processors. |

12:00 - 12:30 | coding sprint status reports |

12:30 - 13:30 | lunch (provided) |

13:30 - 14:30 | Mark van Hoeij - Bivariate factorization over a finite field. Let f(x,y) in Fq[x,y] be a square-free polynomial. The usual way to factor f is to start by choosing an evaluation point x=a in Fq for which f(a,y) is square-free in Fq[y], then to perform a univariate factorization, do an (x-a)-adic Hensel lift, and reconstruct the factorization of f(x,y). When Fq has few elements, there may not be any a in Fq for which f(a,y) is square-free. The talk will explain how to address this problem in efficient way. If time remains, the second topic of the talk will be (a) computing subfields of a number field, and its application to algebraic simplification, or (b) the modular Euclidean algorithm for polynomials over number fields and function fields. |

14:30 - 15:30 | coding and collaboration |

15:30 - 16:00 | tea and coffee |

16:00 - late | coding and collaboration, and time to go out for dinner (room is available until at least 22:00) |

Wednesday 21 | |

9:00 - 10:30 | coding and collaboration |

10:30 - 11:00 | coffee and tea |

11:00 - 12:00 | Maarten Derickx - Torsion points on elliptic curves over number fields of small degree. B. Mazur proved that there are only finitely many torsion subgroups which can arise as the torsion subgroup of an elliptic curve over QQ. Later the uniform boundedness conjecture was stated and proved, generalizing the previous statement to arbitrary number fields in the following way: "Let d be an integer, then there exist a number B (depending on d) such that every torsion subgroup over an elliptic curve over a number field of degree at most d has at most B elements." In particular, Oesterle managed to show that if p is a prime dividing the order of the torsion group of an elliptic curve over a number field of degree d then p < (3^{d/2}+1)^2. In this talk I will explain how Sage can be used to improve this bound for small d. |

12:00 - 12:30 | coding sprint status reports |

12:30 - 13:30 | lunch (provided) |

13:30 - 14:30 | Sebastian Pancratz - Upcoming p-adic functionality in FLINT and practical use cases The past few months saw the beginning development of p-adic arithmetic in FLINT. Specifically, there are experimental modules for the field Qp as well as the univariate polynomial ring and matrix spaces. We discuss the various choices for data types, provide an overview of the functionality that is already available and carry out a speed comparison with Magma and Sage. As evidence of practical usefulness in the current state, we provide an example computation from a p-adic point counting algorithm. N.B. As the modules are still in their early stages of development and the routines are not tied down to their final contracts yet, comments, questions and requests are very much welcome. |

14:30 - 15:30 | coding, collaboration, departure |

15:30 - 16:00 | tea and coffee |

16:00 - late | coding, collaboration, time to go out for dinner, and departure (room is available until at least 22:00) |

Thursday 22 | coding, collaboration, departure (room is available 9:00 -- 22:00) |