Parallel sparse polynomial multiplication using heaps. (English) Zbl 1237.68258
May, John P. (ed.), ISSAC 2009. Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, Seoul, July 28–31, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-609-0). 263-269 (2009).
MSC:
| 68W30 | Symbolic computation and algebraic computation |
| 68W10 | Parallel algorithms in computer science |
References:
| [1] | D. Bini, V. Pan. Improved parallel polynomial division. SIAM J. Comp. 22 (3) 617-626, 1993. 10.1137/0222041 · Zbl 0779.68048 |
| [2] | W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. J. Symb. Comp., 24 (3-4) 235-265, 1997 10.1006/jsco.1996.0125 · Zbl 0898.68039 |
| [3] | R. Fateman. Comparing the speed of programs for sparse polynomial multiplication. ACM SIGSAM Bulletin, 37 (1) (2003) 4-15. 10.1145/844076.844080 · Zbl 1054.65022 |
| [4] | M. Gastineau, J. Laskar. Development of TRIP: Fast Sparse Multivariate Polynomial Multiplication Using Burst Tries. Proceedings of ICCS 2006, Springer LNCS 3992 (2006) 446-453. 10.1007/11758525_60 · Zbl 1155.68593 |
| [5] | G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 3.1.0 - A computer algebra system for polynomial computations. http://www.singular.uni-kl.de (2009). |
| [6] | T. Granlund. The GNU Multiple Precision Arithmetic Library, version 4.2.2. http://www.gmplib.org/ (2008). |
| [7] | S. C. Johnson. Sparse polynomial arithmetic. ACM SIGSAM Bulletin, 8 (3) (1974) 63-71. 10.1145/1086837.1086847 |
| [8] | M. Lam, E. Rothberg, and M. Wolf. The cache performance and optimizations of blocked algorithms. ACM SIGOPS Operating Systems Review., 25 (1991) 63-74. |
| [9] | X. Li and M. Moreno Maza. Multithreaded parallel implementation of arithmetic operations modulo a triangular set. Proc. of PASCO ’07, ACM Press, 53-59, 2007. 10.1145/1278177.1278187 |
| [10] | M. Monagan, K. Geddes, K. Heal, G. Labahn, S. Vorkoetter, J. McCarron, P. DeMarco. Maple 13 Introductory Programming Guide Maplesoft, 2009. |
| [11] | M. Monagan, R. Pearce. Polynomial Division Using Dynamic Arrays, Heaps, and Packed Exponent Vectors. Proc. of CASC 2007, Springer (2007) 295-315. · Zbl 1141.68706 |
| [12] | M. Monagan, R. Pearce. Sparse Polynomial Division Using a Heap. submitted to J. Symb. Comp., October 2008. 10.1016/j.jsc.2010.08.014 |
| [13] | A. Norman, J. Fitch. CABAL: Polynomial and power series algebra on a parallel computer. Proc. of PASCO ’97, ACM Press, pp. 196-203, 1997. 10.1145/266670.266729 · Zbl 0923.68074 |
| [14] | PARI/GP, version 2.3.4, Bordeaux, 2008, http://pari.math.u-bordeaux.fr/. |
| [15] | D. Reed, R. Kanodia. Synchronization with eventcounts and sequencers. Comm. of the ACM, 22 (2) (1979) 115-123. 10.1145/359060.359076 · Zbl 0393.68025 |
| [16] | L. Rudolph, M. Slivkin-Allalouf, and E. Upfal. A simple load balancing scheme for task allocation in parallel machines. Proc. of the third annual ACM symposium on Parallel algorithms and architectures., (1991), 237-245. 10.1145/113379.113401 |
| [17] | P. Sweazey, A. Smith. A Class of Compatible Cache Consistency Protocols and their Support by the IEEE Futurebus. Proc. of 13th Annual International Symposium on Computer Architecture, (1986), 414-423. |
| [18] | P. Wang. Parallel Polynomial Operations on SMPs. J. Symbolic. Comp., 21 397-410, 1996. 10.1006/jsco.1996.0021 · Zbl 0865.68058 |
| [19] | B. Wilkinson, M. Allen. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice Hall, 1999. |
| [20] | C. Xavier, S. Iyengar. Introduction to Parallel Algorithms Wiley, 1998. Section 10.5 has an FFT based univariate multiplication. · Zbl 0948.68220 |
| [21] | T. Yan. The Geobucket Data Structure for Polynomials. J. Symb. Comput. 25 (1998) 285-293. 10.1006/jsco.1997.0176 · Zbl 0927.68124 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
