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.

Worksheet with my progress so far.

• 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)