Differences between revisions 2 and 7 (spanning 5 versions)
Revision 2 as of 2007-02-14 05:47:41
Size: 616
Editor: 71-212-21-65
Comment:
Revision 7 as of 2008-11-14 13:41:56
Size: 999
Editor: localhost
Comment: converted to 1.6 markup
Deletions are marked like this. Additions are marked like this.
Line 3: Line 3:
[http://cr.yp.to/papers/pippenger.pdf Paper] 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.
Line 5: Line 5:
[[http://cr.yp.to/papers/pippenger.pdf|Paper]]

[[http://sage.math.washington.edu/home/boothby/sprint/pippenger.sws|Worksheet]] with my progress so far.
Line 13: Line 16:
 * Output partitioning
 * Output clumping
 * 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 papers by Pippenger.
 * 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].

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.

Paper

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)