Multithreaded parallel implementation of arithmetic operations modulo a triangular set

ABSTRACT

We discuss the parallelization of arithmetic operations on polynomials modulo a triangular set. We focus on parallel normal form computations since this is a core subroutine in many high-level algorithms, such as triangular decompositions of polynomial systems.

When computing modulo a triangular set, multivariate polynomials are regarded recursively as univariate ones, which leads to several implementation challenges when one targets highly efficient code. We rely on an algorithm proposed in [17] which addresses some of these issues.

We propose a two-level parallel scheme. First, we make use of parallel multidimensional Fast Fourier Transform in order to perform multivariate polynomial multiplication. Secondly, we extract parallelism from the structure of the sequential normal form algorithm of [17]. We have realized a multithreaded implementation. We report on different strategies for the management of tasks and threads.

REFERENCES

• 1: R. AlNa'Mneh, W. D. Pan, and R. Adhami Communication efficient adaptive matrix transpose algorithm for FFT on symmetric multiprocessors. In Proc. SSST'05 the Thirty-Seventh Southeastern Symposium on System Theor, pages 312--315. IEEE Computer Society, 2005.
• 2: Jean-Claude Bajard , Graham A. Jullien, Parallel Montgomery Multiplication in GF (2^k) Using Trinomial Residue Arithmetic, Proceedings of the 17th IEEE Symposium on Computer Arithmetic, p.164-171, June 27-29, 2005 [doi>10.1109/ARITH.2005.34]
• 3: Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, An analysis of dag-consistent distributed shared-memory algorithms, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.297-308, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237574]
• 4: S. Cook. On the minimum computation time of functions. PhD thesis, Harvard University, 1966.
• 5: Xavier Dahan , Marc Moreno Maza , Eric Schost , Wenyuan Wu , Yuzhen Xie, Lifting techniques for triangular decompositions, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.108-115, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073901]
• 6: Akpodigha Filatei , Xin Li , Marc Moreno Maza , Éric Schost, Implementation techniques for fast polynomial arithmetic in a high-level programming environment, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145789]
• 7: Mikhail V. Foursov , Marc Moreno Maza, On computer-assisted classification of coupled integrable equations, Journal of Symbolic Computation, v.33 n.5, p.647-660, May 2002 [doi>10.1006/jsco.2002.0527]
• 8: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 9: A. Halbutogullari , C. K. Koc, Parallel Multiplication in $GF(2^k)$ usingPolynomial Residue Arithmetic, Designs, Codes and Cryptography, v.20 n.2, p.155-173, June 2000 [doi>10.1023/A:1008389508626 ]
• 10: Joris van der Hoeven, The truncated fourier transform and applications, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.290-296, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005327]
• 11: Hoon Hong , Hans-Wolfgang Loidl, Parallel Computation of Modular Multivariate Polynominal Resultants on a Shared Memory Machine, Proceedings of the Third Joint International Conference on Vector and Parallel Processing: Parallel Processing, p.325-336, September 06-08, 1994
• 12: Jeremy R. Johnson , Werner Krandick , Anatole D. Ruslanov, Architecture-aware classical Taylor shift by 1, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.200-207, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073913]
• 13: Hyun-Sung Kim, Hee-Joo Park, and Sung-Ho Hwang. Parallel Modular Multiplication Algorithm in Residue Number System. Chapter in Parallel Processing and Applied Mathematics, volume 3019/2004 of Lecture Notes in Computer Science, Springer, 2004.
• 14: Wolfgang Küchlin, On the multi-threaded computation of integral polynomial greatest common divisors, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.333-342, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120747]
• 15: H. T. Kung. On computing reciprocals of power series. Numerische Mathematik, 22:341--348, 1974.
• 16: X. Li and M. Moreno Maza. Efficient implementation of polynomial arithmetic in a multiple-level programming environment. In A. Iglesias and N. Takayama, editors, Proc. International Congress of Mathematical Software-ICMS 2006, pages 12--23. Springer, 2006.
• 17: Xin Li , Marc Moreno Maza , Éric Schost, Fast arithmetic for triangular sets: from theory to practice, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277585]
• 18: X. Li, M. Moreno Maza, and É. Schost. On the virtues of generic programming for symbolic computation. In Proc. CASA'07, Lecture Notes in Computer Science vol. 4488, pages. 251258, Springer-Verlag Berlin Heidelberg 2007.
• 19: Marc Moreno Maza , Ben Stephenson , Stephen M. Watt , Yuzhen Xie, Multiprocessed parallelism support in ALDOR on SMPs and multicores, Proceedings of the 2007 international workshop on Parallel symbolic computation, July 27-28, 2007, London, Ontario, Canada [doi>10.1145/1278177.1278188]
• 20: Marc Moreno Maza , Yuzhen Xie, Component-level parallelization of triangular decompositions, Proceedings of the 2007 international workshop on Parallel symbolic computation, July 27-28, 2007, London, Ontario, Canada [doi>10.1145/1278177.1278189]
• 21: Kazutaka Morita , Akimasa Morihata , Kiminori Matsuzaki , Zhenjiang Hu , Masato Takeichi, Automatic inversion generates divide-and-conquer parallel programs, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 22: M. Sieveking. An algorithm for division of power series. Computing, 10:153--156, 1972.
• 23: Jean-Louis Roch , Sébastien Varrette, Probabilistic certification of divide & conquer algorithms on global computing platforms: application to fault-tolerant exact matrix-vector product, Proceedings of the 2007 international workshop on Parallel symbolic computation, July 27-28, 2007, London, Ontario, Canada [doi>10.1145/1278177.1278191]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Design, Experimentation, Languages, Performance, Theory

Keywords:
algorithms, high-performance, normal form, parallelization, polynomials