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
classes will be inherited by sub-classes. Any algebra is a ring, and one
might expect that this fact is reflected by the class inheritance.

However, the notion of a Python class is not a mathematical notion.
E.g., the set of all
m by n matrices over a ring R is implemented
in a single Python class, but the result is either an
R-algebra or
just an
R-module, depending on whether or not m=n.

Sage offers a "category framework" as a mathematically more meaningful
way of inheritance. Any category in Sage can provide so called parent or
element methods, that are available to any object in the category and to
any element of the objects.

Coercion is about arithmetic accross different algebraic structures,
e.g., adding a rational number to an integral polynomial. Sage's
coercion framework attempts rigidity by using categories: Before adding
two elements, they are mapped into a common parent by morphisms of a
category, and the common parent can be constructed by functors and a
pushout construction.

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)