Multiplication of sparse Laurent polynomials and Poisson series on modern hardware architectures

Details Multiplication of sparse Laurent polynomials and Poisson series on modern hardware architectures Multiplication of sparse Laurent polynomials and Poisson series on modern hardware architectures

2010-04-26

arxiv.org/abs/1004.4548v1

Computer Science

Symbolic Computation

Scientific paper

In this paper we present two algorithms for the multiplication of sparse Laurent polynomials and Poisson series (the latter being algebraic structures commonly arising in Celestial Mechanics from the application of perturbation theories). Both algorithms first employ the Kronecker substitution technique to reduce multivariate multiplication to univariate multiplication, and then use the schoolbook method to perform the univariate multiplication. The first algorithm, suitable for moderately-sparse multiplication, uses the exponents of the monomials resulting from the univariate multiplication as trivial hash values in a one dimensional lookup array of coefficients. The second algorithm, suitable for highly-sparse multiplication, uses a cache-optimised hash table which stores the coefficient-exponent pairs resulting from the multiplication using the exponents as keys. Both algorithms have been implemented with attention to modern computer hardware architectures. Particular care has been devoted to the efficient exploitation of contemporary memory hierarchies through cache-blocking techniques and cache-friendly term ordering. The first algorithm has been parallelised for shared-memory multicore architectures, whereas the second algorithm is in the process of being parallelised. We present benchmarks comparing our algorithms to the routines of other computer algebra systems, both in sequential and parallel mode.

Affiliated with

Also associated with

No associations

Rating

Multiplication of sparse Laurent polynomials and Poisson series on modern hardware architectures 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 Multiplication of sparse Laurent polynomials and Poisson series on modern hardware architectures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplication of sparse Laurent polynomials and Poisson series on modern hardware architectures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32514