Michael Monagan
Roman Pearce
ABSTRACT
We present a parallel algorithm for exact division of sparse distributed polynomials on a multicore processor. This is a problem with significant data dependencies, so our solution requires fine-grained parallelism. Our algorithm manages to avoid waiting for each term of the quotient to be computed, and it achieves superlinear speedup over the fastest known sequential method. We present benchmarks comparing the performance of our C implementation of sparse polynomial division to the routines of other computer algebra systems.
- D. Bini, V. Pan. Improved parallel polynomial division. SIAM J. Comp. 22 (3) 617--626, 1993. Google Scholar
Digital Library
- W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. J. Symb. Comp., 24 (3--4) 235--265, 1997 Google ScholarDigital Library
- R. Fateman. Comparing the speed of programs for sparse polynomial multiplication. ACM SIGSAM Bulletin, 37 (1) 4--15, 2003. Google ScholarDigital Library
- M. Gastineau, J. Laskar. Development of TRIP: Fast Sparse Multivariate Polynomial Multiplication Using Burst Tries. Proc. ICCS 2006, Springer LNCS 3992, 446--453. Google ScholarDigital Library
- G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 3.1.0 -- A computer algebra system for polynomial computations, 2009. http://www.singular.uni-kl.deGoogle Scholar
- L. H. Harper, T. H. Payne, J. E. Savage, E. Straus. Sorting X+Y. Comm. ACM 18 (6), pp. 347--349, 1975. Google ScholarDigital Library
- S. C. Johnson. Sparse polynomial arithmetic. ACM SIGSAM Bulletin, 8 (3) 63--71, 1974. Google ScholarDigital Library
- X. Li and M. Moreno Maza. Multithreaded parallel implementation of arithmetic operations modulo a triangular set. Proc. of PASCO '07, ACM Press, 53--59. Google ScholarDigital Library
- T. Mattson, B. Sanders, B. Massingill. Patterns for Parallel Programming. Addison-Wesley, 2004. Google ScholarDigital Library
- M. Matooane. Parallel Systems in Symbolic and Algebraic Computation. Ph.D Thesis, Cambridge, 2002.Google Scholar
- M. Monagan, R. Pearce. Parallel Sparse Polynomial Multiplication Using Heaps. Proc. of ISSAC 2009, 295--315. Google ScholarDigital Library
- M. Monagan, R. Pearce. Polynomial Division Using Dynamic Arrays, Heaps, and Packed Exponent Vectors. Proc. of CASC 2007, Springer LNCS 4770, 295--315. Google ScholarDigital Library
- M. Monagan, R. Pearce. Sparse Polynomial Division Using a Heap. submitted to J. Symb. Comp., October 2008.Google Scholar
- A. Norman, J. Fitch. CABAL: Polynomial and power series algebra on a parallel computer. Proc. of PASCO '97, ACM Press, pp. 196--203. Google ScholarDigital Library
- P. Wang. Parallel Polynomial Operations on SMPs. J. Symbolic. Comp., 21 397--410, 1996. Google ScholarDigital Library
Index Terms
- Parallel sparse polynomial division using heaps
Recommendations
Parallel operations of sparse polynomials on multicores: I. multiplication and Poisson bracket
PASCO '10: Proceedings of the 4th International Workshop on Parallel and Symbolic ComputationThe multiplication of the sparse multivariate polynomials using the recursive representations is revisited to take advantage on the multicore processors. We take care of the memory management and load-balancing in order to obtain linear speedup. The ...
Parallel sparse polynomial multiplication using heaps
ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computationWe present a high performance algorithm for multiplying sparse distributed polynomials using a multicore processor. Each core uses a heap of pointers to multiply parts of the polynomials using its local cache. Intermediate results are written to buffers ...
Parallel sparse multivariate polynomial division
PASCO '15: Proceedings of the 2015 International Workshop on Parallel Symbolic ComputationWe present a scalable algorithm for dividing two sparse multivariate polynomials represented in a distributed format on shared memory multicore computers. The scalability on the large number of cores is ensured by the lack of synchronizations during the ...
Comments