attachment:note_leykin.txt of msri07/notes

   1 1:30 p.m.
   2 Parallel Computations of Groebner Bases in the Weyl Algebra.
   3 Anton Leykin
   4 
   5 R = QQ[a,b,c]
   6 f_1 = 2a^2b^2 + 3b^2c + 1
   7 f_2 = abc - b^2c
   8 
   9 Think of the Weyl Algebra as an algebra of something over something or something
  10 
  11 Consider all the generators x_i, \partial_i, where x_i\dot f = x_if  and \partial_i f = \frac{\partial f}{\partial x_i}
  12 
  13 Who cares about Weyl Algebra?  Agebraic geometers, for one.
  14 
  15 Now, forget about the Weyl Algebra.  It belongs to the wider Algebra of Solvable Type, or "Groebner-Friendly Algebra"
  16 
  17 In the above polynomials, ordered with deg-lex ordering:
  18 	initial monomial lm(f_1) = a^2b^2 , lm(f_2) = abc
  19 	initial coefficient lc(f_1) = 2 , lc(f_2) = 1
  20 	initial term lt(f) = lm(f)lc(f)
  21 	L(f,g) = lcm( lm(f), lm(g) )
  22 	sPoly(f_1,f_2) = cf_1 - 2abf_2 = 3b^2c^2 +c + 2ab^3c
  23 
  24 We can calculate a Groebner basis using the Buchberger algorithm (or any improvements).  The improved versions require modifications for the Weyl algebra.
  25 
  26 Slave stores a local basis G (or a set of reductors).  Receives information on what to reduce, reduces it, and sends it back.
  27 The load of the Master is negligable to the load of the Slave, but it is necessary to maintain an intermediate basis of G and the queue of s-pairs.
  28 
  29 Key point in the parallelization:  The order of the s-pairs is the same as in the serial algorithm.  The strategies used for s-pair selection are also preserved.
  30 
  31 Assumptions of the parallel simulator:
  32 	-Operations performed by Master are instantaneous (negligable).
  33 	-Time for sending package from one node to another assumed to be linear by size.
  34 Achieves a theoretic speed-up of about a factor of 8 using 10 nodes.  Factor of about 26 on 64 nodes.
  35 A lot of idle time was noted when 64 nodes were used.
  36 
  37 Seeking a practical improvement over calculation times.
  38 
  39 F_4 algorithm of calculating the Groebener basis can be adapted to work over the Weyl algebra.
  40 
  41 Parallel versions of Buchberger's algorithm can produce limited speedups
  42 Course-grain approach exhibits better speedups in the noncommutative algebra than in the commutative polynoimal rings on "interesting" problems of similar size.
  43 It does make sense to use 128 nodes on this problem, even with the idle times!
  44 
  45 Future:
  46 	From theory to practice--we need to make this parallel implementation practically efficient.
  47 	The F_4 algorithm results in the loss of sparsity in the intermediate computation, however is still feasible and its parallel version could be constructed.
  48 	A test/benchmark should be agreed upon.
  49 
  50 Examples that are "interesting" usually cause the computer to run out of memory due to intermediate growth of terms