Differences between revisions 1 and 2
 ⇤ ← Revision 1 as of 2008-06-20 21:32:57 → Size: 1739 Editor: GonzaloTornaria Comment: Status report ← Revision 2 as of 2008-11-14 13:41:51 → ⇥ Size: 1740 Editor: localhost Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 13: Line 13: Worked with Bill Hart on huge polynomial multiplication using multimodular method (see his [:dev1/billhart: Status Report]). So far the code is twice as slow as FLINT, but uses less memory. For instance, I can multiply two polinomials of 1 million 960 bit coefficients each in 4 minutes in my laptop. FLINT would take an estimated 2 minutes, but I "only" have 2Gb of RAM in my laptop (I killed it after 10 minutes just before the OOM killer jumped in). Worked with Bill Hart on huge polynomial multiplication using multimodular method (see his [[dev1/billhart| Status Report]]). So far the code is twice as slow as FLINT, but uses less memory. For instance, I can multiply two polinomials of 1 million 960 bit coefficients each in 4 minutes in my laptop. FLINT would take an estimated 2 minutes, but I "only" have 2Gb of RAM in my laptop (I killed it after 10 minutes just before the OOM killer jumped in).

## Computing theta series for Congruent Number Problem

Implemented fast code to compute unary and binary theta series needed for the Congruent Number Problem. The aim is to multiply these two theta series together using a fast multiplication to get the weight 3/2 modular form --- instead of using a ternary theta series (which would be O(X3/2).)

In order to support computing X=1012 coefficients, this code allows computing theta series "by blocks", and I discovered that it's actually faster to compute by small blocks (a bit larger than O(sqrt(X))), for example:

• 109 takes 3.6 secs if computed in blocks of 105 coefficients, and 15 secs if computed in blocks of 106 coefficients, etc.

• for 1012 it seems optimal to use blocks of 107 coefficients -- estimated total time a bit under 6 hours (note that clearing 1012 words to 0 would take about 2 of the 6 hours).

The goal is to eventually extended this to handle general binary and ternary quadratic forms.

## Multiplying large polynomials

Worked with Bill Hart on huge polynomial multiplication using multimodular method (see his Status Report). So far the code is twice as slow as FLINT, but uses less memory. For instance, I can multiply two polinomials of 1 million 960 bit coefficients each in 4 minutes in my laptop. FLINT would take an estimated 2 minutes, but I "only" have 2Gb of RAM in my laptop (I killed it after 10 minutes just before the OOM killer jumped in).

## Montgomery multiplication

The reconstruction step in the multimodular multiplication can be improved using (division free) Montgomery multiplication, so we've been working on adding support for this to FLINT (to be added in MPIR later).

dev1/tornaria (last edited 2008-11-14 13:41:51 by localhost)