Big prime field FFT on multi-core processors. (English) Zbl 1467.65121
Bradford, Russell (ed.), Proceedings of the 44th international symposium on symbolic and algebraic computation, ISSAC ’19, Beijing, China, July 15–18, 2019. New York, NY: Association for Computing Machinery (ACM). 106-113 (2019).
MSC:
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
| 68W10 | Parallel algorithms in computer science |
Keywords:
fast Fourier transforms; finite fields; generalized Fermat numbers; Intel CilkPlus; multi-core processors; specialized arithmeticReferences:
| [1] | Ayaz Ali, Lennart Johnsson, and Jaspal Subhlok. 2007. Scheduling FFT Computation on SMP and Multicore Systems. In Proceedings of the 21st Annual International Conference on Supercomputing (ICS ’07). ACM, New York, NY, USA, 293-301. 10.1145/1274971.1275011 |
| [2] | Elizabeth A. Arnold. 2003. Modular Algorithms for Computing Gröbner Bases. Journal of Symbolic Computation, Vol. 35, 4 (2003), 403-419. 10.1016/S0747-7171(02)00140-2 · Zbl 1046.13018 |
| [3] | Mohammadali Asadi, Alexander Brandt, Changbo Chen, Svyatoslav Covanov, Farnam Mansouri, Davood Mohajerani, Robert Moir, Marc Moreno Maza, Linxiao Wang, Ning Xie, and Yuzhen Xie. 2019. Basic Polynomial Algebra Subprograms (BPAS). http://www.bpaslib.org. · Zbl 1365.68484 |
| [4] | Paul Barrett. 1986. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In Conference on the Theory and Application of Cryptographic Techniques. Springer, 311-323. |
| [5] | Liangyu Chen, Svyatoslav Covanov, Davood Mohajerani, and Marc Moreno Maza. 2017. Big Prime Field FFT on the GPU. In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC. 85-92. 10.1145/3087604.3087657 · Zbl 1472.94046 |
| [6] | Svyatoslav Covanov. 2014. Putting Fürer Algorithm into practice. Technical Report. ORCCA Lab, London. |
| [7] | Svyatoslav Covanov and Emmanuel Thomé. 2018. Fast integer multiplication using generalized Fermat primes . Mathematics of Computation (2018). https://hal.inria.fr/hal-01108166 · Zbl 1412.68304 |
| [8] | Xavier Dahan, Marc Moreno Maza, É ric Schost, Wenyuan Wu, and Yuzhen Xie. 2005. Lifting techniques for triangular decompositions. In ISSAC 2005, Proceedings, , M. Kauers (Ed.). ACM, 108-115. 10.1145/1073884.1073901 · Zbl 1360.14146 |
| [9] | Anindya De, Piyush P. Kurur, Chandan Saha, and Ramprasad Saptharishi. 2008. Fast integer multiplication using modular arithmetic. In STOC. 499-506. 10.1145/1374376.1374447 · Zbl 1231.68289 |
| [10] | Anindya De, Piyush P Kurur, Chandan Saha, and Ramprasad Saptharishi. 2013. Fast Integer Multiplication Using Modular Arithmetic. SIAM J. Comput., Vol. 42, 2 (2013), 685-699. · Zbl 1271.68247 |
| [11] | Franz Franchetti and Markus Püschel. 2011. FFT (Fast Fourier Transform). In Encyclopedia of Parallel Computing . 658-671. |
| [12] | Franz Franchetti, Yevgen Voronenko, and Markus Pü schel. 2006. Tools and techniques for performance - FFT program generation for shared memory: SMP and multicore. In Proceedings of the ACM/IEEE SC2006 Conference on High Performance Networking and Computing, November 11-17, 2006, Tampa, FL, USA. 115. 10.1145/1188455.1188575 |
| [13] | Martin Fürer. 2009. Faster Integer Multiplication. SIAM J. Comput., Vol. 39, 3 (2009), 979-1005. 10.1137/070711761 · Zbl 1192.68926 |
| [14] | Torbjörn Granlund and the GMP development team. 2012. GNU MP: The GNU Multiple Precision Arithmetic Library 5.0.5 ed.). http://gmplib.org/. |
| [15] | David Harvey, Joris van der Hoeven, and Grégoire Lecerf. 2017. Faster Polynomial Multiplication over Finite Fields. J. ACM, Vol. 63, 6, Article 52 (Jan. 2017), bibinfonumpages23 pages. 10.1145/3005344 · Zbl 1426.68310 |
| [16] | David Harvey, Joris van der Hoeven, and Grégoire Lecerf. 2016a. Even faster integer multiplication. Journal of Complexity, Vol. 36 (2016), 1-30. 10.1016/j.jco.2016.03.001 · Zbl 1350.68145 |
| [17] | David Harvey, Joris van der Hoeven, and Grégoire Lecerf. 2016b. Fast Polynomial Multiplication over F260. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC ’16). ACM, New York, NY, USA, 255-262. 10.1145/2930889.2930920 · Zbl 1360.68935 |
| [18] | Marc Moreno Maza and Yuzhen Xie. 2009. FFT-Based Dense Polynomial Arithmetic on Multi-cores. In HPCS (Lecture Notes in Computer Science), Vol. 5976. Springer, 378-399. 10.1007/978-3-642-12659-8_28 · Zbl 1222.68416 |
| [19] | Lingchuan Meng, Yevgen Voronenko, Jeremy R. Johnson, Marc Moreno Maza, Franz Franchetti, and Yuzhen Xie. 2010. Spiral-generated modular FFT algorithms. In PASCO. 169-170. 10.1145/1837210.1837235 |
| [20] | Peter L. Montgomery. 1985. Modular multiplication without trial division. Mathematics of computation, Vol. 44, 170 (1985), 519-521. · Zbl 0559.10006 |
| [21] | Arnold Schönhage and Volker Strassen. 1971. Schnelle Multiplikation großer Zahlen. Computing, Vol. 7, 3-4 (1971), 281-292. · Zbl 0223.68007 |
| [22] | Joachim von zur Gathen and Jürgen Gerhard. 2013. Modern Computer Algebra (3. ed.) .Cambridge University Press. · Zbl 1277.68002 |
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.
