Differences between revisions 6 and 7
Revision 6 as of 2007-02-20 10:26:34
Size: 995
Editor: anonymous
Revision 7 as of 2008-11-14 13:41:56
Size: 999
Editor: anonymous
Comment: 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.pdf|Paper]]
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.sws|Worksheet]] 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 [34-36].

  • The general case (not certain this is a reasonable goal for the amount of time we have)

days3/sprints/pippenger (last edited 2008-11-14 13:41:56 by anonymous)