Differences between revisions 4 and 6 (spanning 2 versions)
Revision 4 as of 2007-02-19 19:01:18
Size: 980
Editor: dhcp46-71
Revision 6 as of 2007-02-20 10:26:34
Size: 995
Editor: 12
Deletions are marked like this. Additions are marked like this.
Line 6: Line 6:
[http://sage.math.washington.edu/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.

[http://cr.yp.to/papers/pippenger.pdf Paper]

[http://sage.math.washington.edu/home/boothby/sprint/pippenger.sws 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 localhost)