995
Comment:

← Revision 7 as of 20081114 13:41:56 ⇥
999
converted to 1.6 markup

Deletions are marked like this.  Additions are marked like this. 
Line 5:  Line 5: 
[http://cr.yp.to/papers/pippenger.pdf Paper]  [[http://cr.yp.to/papers/pippenger.pdfPaper]] 
Line 7:  Line 7: 
[http://sage.math.washington.edu/home/boothby/sprint/pippenger.sws Worksheet] with my progress so far.  [[http://sage.math.washington.edu/home/boothby/sprint/pippenger.swsWorksheet]] with my progress so far. 
Tom Boothby: Implement Pippenger's Algorithm for multivariate polynomial evaluation
Pippenger's Algorithm is a method to compute a sequence of multiple products of multiple inputs. I intend to use this to (drastically, in some cases) speed up the evaluation of multivariate polynomials over arbitrary rings.
Worksheet with my progress so far.
Skip to page 13. I've already implemented:
 Direct computation (option 1 in the paper)
 Input partitioning (option 2)
 Most of input clumping (option 3)
I need:
 Output partitioning (option 4)
 Output clumping (excercise left to reader)
Some insight as to why DJB thinks that one can "quickly compute the parameter sequence given p, q. I'll bring a print copy of the 3 cites from Pippenger [3436].
 The general case (not certain this is a reasonable goal for the amount of time we have)