Saturday 29 March 2014

Introduction

Hi,
My name is Abhinav Baid. I am a computer science undergraduate at Birla Institute of Technology and Science, Pilani. This is a blog post to go along with my proposal and code sample for the project "Implementing the LLL algorithm in FLINT" as a part of the Google Summer of Code under lmonade. FLINT is a C library for number theory. The aim of this project is to implement a basic LLL in FLINT allowing for parameters to be supplied governing the strength of reduction (delta-eta reduction using floating-point arithmetic), followed by a couple of the more interesting modern versions, including the LLL with removals and ULLL, a version of LLL with better complexity in terms of the size of the entries. The mentors for this project are William Hart and Fredrik Johansson.

A description of the algorithms involved in this project can be found in my proposal. A more comprehensive list of references is available in this thread of the flint-devel mailing list. The proposal also includes an Objective and Deliverables section where I describe how I plan to approach this task. The data types used in this project will be double, mpf_t, and fmpz_t. Unlike flint-1.6, mpf was chosen over mpfr because correct rounding is not required for LLL. The modules which will be added/modified as part of this project are d_mat, d_vec, mpf_mat, mpf_vec. fmpq_mat, fmpz_lll.

  • d_mat : Matrices with double precision floating point entries. Functions for operations like memory management, arithmetic, etc. BLAS compatible representation will be used.
  • mpf_mat : Matrices with arbitrary precision floating point entries. Functions for operations like memory management, arithmetic, etc.
  • d_vec : Vectors with double precision floating point entries. Functions to help modularise the code in the d_mat module.
  • mpf_vec : Vectors with arbitrary precision floating point entries. Functions to help modularise the code in the mpf_mat module.
  • fmpq_mat : Function to implement the rational algorithm (delta / c reduction).
  • fmpz_lll : LLL reduction on the rows of an fmpz_mat_t. Functions related to LLL like the various Babai's, actual LLL (L^2) functions, wrappers, LLL with removals,  ULLL.

I plan to finish the basic helper functions (not related to the algorithm) and the fmpq_mat implementation before the coding period of GSoC. The LLL implementations in FLINT 1.6 do not support passing of parameters and are not compatible with the current FLINT series (FLINT 2.x). Hence, the project aims to build a structured and clean module instead of having all the functions in a single file. The proposal also has a detailed timeline where I provide a schedule with dates and important milestones.

Now, what attracts me to this problem? Well, there are lots of reasons but just for fun, let me enumerate a few:

  • It involves C programming.
  • It involves linear algebra.
  • It has applications in diverse fields.
  • It is open source.
  • Most importantly, it has excellent mentors - computational number theory experts with lots of experience in implementing efficient algorithms.
If a project had even one of the above features, I would have loved to be a part of it. Now, when I get a (linear (:) combination of all the above plus a chance to flaunt, I'll surely be interested, won't I?