attachment:notes_hart.txt of msri07/notes

   1 10:30 a.m.
   2 Parallel Processing in Algebraic Number Theory
   3 Bill Hart
   4 
   5 FLINT = Fast Library for Number Theory.  Jointly maintained by David Harvey and Bill Hart.
   6 Design Philosophy
   7 	-Want to be faster than all available alternatives (unrealistic and unachievable)
   8 	-Asymptotically fast algorithms
   9 	-Library written in C
  10 	-Based on GMP
  11 	-Extensively tested
  12 	-Extensively profiled
  13 	-Support for parallel processing
  14 
  15 What does FLINT currently do?
  16 	-All GMP integer functions
  17 	-Additional functions for integer and modular arithmetic
  18 		-Not efficient for small operands.  GMP is very efficient for very long integers.
  19 	-Integer factorisation (Multiple Polynomial Quadratic Sieve)
  20 	-Some polynomial arithmetic, including asymptotically fast polynomial multiplication
  21 
  22 What will FLINT eventually do?
  23 	-Z-integer arithmetic
  24 	-Zmod - Arithmetic in the intergers modulo n
  25 	-Zpoly - Polynomials over the integers
  26 	-Zvec - vectors over the integers
  27 	-Zmat - Linear algebra over the integers
  28 	-Z_p - p-adics
  29 	-GF2 - Sparse and dense matricies over GF2
  30 	-QNF - Quadratic Number Fields
  31 	-NF - Genreal Number Fields
  32 
  33 Additional functions available in FLINT
  34 	exponentiation
  35 	modular multiplication, inversion, square rooot, CRT, exponentiation
  36 	next prime, random prime, extended GCD, GCD
  37 	integer multiplication (faster than GMP 4.2.1)
  38 	Block Lanczos code
  39 	polynomial root finding code
  40 	SQUFOF factoring algorithm
  41 	self initialising multiple polynomial quadratic sieve
  42 	memory management for single mpz_t's and arrays of mpz_t's
  43 
  44 Basic polynomial arithmetic is available.
  45 
  46 Why a new library?  What about Pari, NTL, LiDIA, others?  What about Magma, Maple, Mathematica?  What about SAGE?
  47 
  48 FLINT currently beats Pari in integer factorisation, and is faster (at smaller sizes) than Msieve.
  49 
  50 FLINT beats Pari virtually all the time at polynomial multiplication.  MAGMA beats NTL at polynomial multiplication similarly
  51 
  52 Algorithms for Polynomial Multiplication
  53 	-Radix multiplications (used by NTL, old algorithm, outdated)
  54 	-Schoenhage-Strassen (based on FFTs)
  55 	-Kronecker-Schoenhage (combine into large integers and multiply) (most efficient algorithm for certain problem sizes)
  56 	-Karatsuba
  57 	-Toom
  58 All of the talk of polynomial multiplications is only of the univariate case.
  59 
  60 Schoenhage-Strassen Method:
  61 	A polynomail of degree n is completely determined by its values at n+1 distinct points
  62 	g(x) = f_1(x)*f_2(x) is determined by its value at 2n points of f_1 and f_2 have length n
  63 	Discrete FFT chooses 2n-th roots of unity as the poitns at which to evaluate.
  64 	Compute DFT of coefficients of f_1, compute DFT of coefficients of f_2, multiply the 2n values, perform inverse transformation.
  65 	Use FFt.
  66 	Schoenhage-Strassen works in the ring integers modulo (2^n+1)
  67 
  68 What does MAGMA use?  By looking at a graph of the expected times vs actual performance times, it seems that MAGMa uses Schoenhage-Strassen by the jumps of runtime at lengths of powers of 2.  Something else seems to be going on when one polynomial is small.
  69 
  70 What does FLINT do?  Flint uses variants of Schoenhage-Strassen and Kroenecker-Strassen.
  71 	Uses a trick suggested by David Harvey and Paul Zimmerman for KS.
  72 	Uses Bailey's four-step algorithm.
  73 	Truncated FFT (with 2 step) - Joris van der Hoeven
  74 
  75 After some work, FLINT now competes with MAGMA.
  76 
  77 Parallelisation in FLINT:
  78 	No global or static variables
  79 	Memory management (needs to support multiple threads requesting memory).
  80 	Decided to use Posix threads for now.
  81 
  82 There is a frustratoin at the lack of open source mathematics that uses pthreads.
  83 There are (outrageous) claims that 200,000 threads cna be started by the kernel, per second.
  84 Threads may take some time to be scheduled (real-time threads)
  85 Some solutions?
  86 	-Queue of jobs from which threads can pull tasks
  87 	-Threads go to sleep when thre is no work and wake up when a condition is met
  88 	-Sometimes, they're just not necessary
  89 
  90 For parallelising the FFT, the general idea is to break the vectors into smaller chunks and performing FFTs on those chunks.
  91 
  92 Feeling much more confident now that FLINT is doable and even parallelisable
  93 
  94 SAGE relies on Pari for many things.  Would like to do a lot of these things themselves over working with Pari to improve Pari
  95 once you introduce a layer of abstraction into a problem, you need C++