Chunky and Equal-Spaced Polynomial Multiplication

Details Chunky and Equal-Spaced Polynomial Multiplication Chunky and Equal-Spaced Polynomial Multiplication

2010-04-26

arxiv.org/abs/1004.4641v2

Computer Science

Symbolic Computation

23 Pages, pdflatex, accepted to Journal of Symbolic Computation (JSC)

Scientific paper

Finding the product of two polynomials is an essential and basic problem in computer algebra. While most previous results have focused on the worst-case complexity, we instead employ the technique of adaptive analysis to give an improvement in many "easy" cases. We present two adaptive measures and methods for polynomial multiplication, and also show how to effectively combine them to gain both advantages. One useful feature of these algorithms is that they essentially provide a gradient between existing "sparse" and "dense" methods. We prove that these approaches provide significant improvements in many cases but in the worst case are still comparable to the fastest existing algorithms.

Affiliated with

Also associated with

No associations

Rating

Chunky and Equal-Spaced Polynomial Multiplication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Chunky and Equal-Spaced Polynomial Multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chunky and Equal-Spaced Polynomial Multiplication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-236236