GSoC :- Week 1

My proposal "Implementing the LLL algorithm in FLINT" has been accepted for Google Summer of Code 2014. The official coding period began last week (May 19) and so I have started to code. The source code can be found here.

What did you work on this week?

- Implemented the _fmpz_vec_dot function in fmpz_vec module for use in fmpz_lll_heuristic_dot.

- Implemented the fmpz_lll_heuristic_dot function for use in fmpz_lll_check_babai_heuristic_d.

- Implemented the _fmpz_vec_get_d_vec_2exp function in fmpz_vec module for use in fmpz_lll_check_babai.

- Wrote the fmpz_lll_check_babai function.

- Wrote the fmpz_lll_check_babai_heuristic_d function.

- Made changes to d_mat, d_vec modules and fmpq_mat implementation of classical LLL based on mentor comments.

What do you plan on doing next week?

- Change fmpz_lll_heuristic_dot to use the new _d_vec_dot heurstic function and test it.

- Document the Babai functions.

- Write the fmpz_lll_d function.

- Test, profile and document fmpz_lll_d.

- Increase the pace, maybe? :)

Are you stuck on anything?

I am not stuck because of these issues, but would certainly appreciate comments to improve the  code.

- How to check if a double is NaN?: IEEE standard specifies f != f will be true only if f is NaN and so, I use this as the check. However, compilers may optimize this out. This requires checking with different compilers. The condition cannot be changed to use isnan function in math.h as that was introduced in C99.

- Will +-0 cause a problem? -0.0 == 0.0 returns true, so it seems to be okay.

- Hackish way of finding ulps in _d_vec_dot_heurstic. Is there a better way not using functions like nextafter which is since C99?

- y = rint(x); is not ANSI C. I used if(x < 0) y = ceil(x-0.5); else y = floor(x+0.5); instead. Here's the output on my machine with the rounding mode as default.
rint(5.5) = 6.0 rint(-1.5) = -2.0
ceil(5.5-0.5) = 5.0 floor(5.5+0.5) = 6.0 ceil(-1.5-0.5) = -2.0 floor(-1.5+0.5) = -1.0  

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?