Differences between revisions 2 and 3

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]

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)

-  ⇤ ← Revision 2 as of 2007-02-14 05:47:41 → 
  Size: 616
  Editor: anonymous
  Comment:
+   ← Revision 3 as of 2007-02-14 05:50:34 → ⇥
  Size: 889
  Editor: anonymous
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 3:
+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 4:
+Line 6:
-Line 13:
+Line 14:
- * 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].

Diff for "days3/sprints/pippenger"

Tom Boothby: Implement Pippenger's Algorithm for multivariate polynomial evaluation