×

Parallelization of triangular decompositions: techniques and implementation. (English) Zbl 1503.13018

One of the well-known tools for solving polynomial systems is triangular decomposition which provides a finite set of regular chains. This kind of decomposition proceeds in an incremental manner by solving the equations one after the other and this may yield a splitting of the quasi-component of a regular chain. Thus, here the construction looks like a tree and one can complete each branch independently. The natural question that may arise is how we can use parallelization techniques for this computation. This question has been addressed in [M. Moreno Maza and Y. Xie [“Component-level parallelization of triangular decompositions”, in: Proceedings of the 2007 international workshop on Parallel symbolic computation, PASCO 2007. New York, NY: Association for Computing Machinery (ACM). 69–77 (2007; doi:10.1145/1278177.1278189)].
In this paper the authors consider four different and related schemes in low and high levels to exploit parallelism in triangular decomposition algorithms. It is worth noting that a splitting is dependent on the geometry of the input polynomial system, and this may cause a problem for the parallelization (this point has been taken into account in the paper). The implementation (written in C/C++ in as a part of the BPAS library) of these algorithms and experimentation on thousands of polynomial systems show examples with even more than 10 times of speed-up.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
11Y05 Factorization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asadi, M.; Brandt, A.; Chen, C.; Covanov, S.; Kazemi, M.; Mansouri, F.; Mohajerani, D.; Moir, R. H.C.; Moreno Maza, M.; Talaashrafi, D.; Wang, L.-X.; Xie, N.; Xie, Y., Basic Polynomial Algebra Subprograms (BPAS) v. 1.791 (2021)
[2] Asadi, M.; Brandt, A.; Moir, R. H.C.; Moreno Maza, M., Algorithms and data structures for sparse polynomial arithmetic, Mathematics, 7, 5, 441 (May 2019)
[3] Asadi, M.; Brandt, A.; Moir, R. H.C.; Moreno Maza, M.; Xie, Y., On the parallelization of triangular decompositions, (Emiris, I. Z.; Zhi, L., ISSAC ’20: International Symposium on Symbolic and Algebraic Computation. ISSAC ’20: International Symposium on Symbolic and Algebraic Computation, Kalamata, Greece, July 20-23, 2020 (2020), ACM), 22-29 · Zbl 07300049
[4] Attardi, G.; Traverso, C., Strategy-accurate parallel buchberger algorithms, J. Symb. Comput., 22, 1-15 (1996) · Zbl 0865.68059
[5] Aubry, P.; Lazard, D.; Moreno Maza, M., On the theories of triangular sets, J. Symb. Comput., 28, 1-2, 105-124 (1999) · Zbl 0943.12003
[6] Ben-Ari, M., Principles of Concurrent and Distributed Programming, PHI Series in Computer Science (1990), Prentice Hall · Zbl 0701.68001
[7] Bini, D.; Mourrain, B., Polynomial test suite (1999)
[8] Biscani, F., Parallel sparse polynomial multiplication on modern hardware architectures, (ISSAC 2012. ISSAC 2012, Grenoble, France, 2012 (2012)), 83-90 · Zbl 1308.68159
[9] Böhm, J.; Decker, W.; Laplagne, S.; Pfister, G.; Steenpaß, A.; Steidel, S., Parallel algorithms for normalization, J. Symb. Comput., 51, 99-114 (2013) · Zbl 1408.13072
[10] Boulier, F.; Lemaire, F.; Moreno Maza, M., Well known theorems on triangular systems and the D5 principle, (Proc. of Transgressive Computing 2006. Proc. of Transgressive Computing 2006, Granada, Spain (2006)) · Zbl 1213.13044
[11] Buchberger, B., The parallelization of critical-pair/completion procedures on the l-machine, (Proc. of the Jap. Symp. on Functional Programming (1987)), 54-61
[12] Bündgen, R.; Göbel, M.; Küchlin, W., A fine-grained parallel completion procedure, (Proceedings of ISSAC (1994), ACM), 269-277 · Zbl 0964.68572
[13] Chen, C.; Moreno Maza, M., Algorithms for computing triangular decomposition of polynomial systems, J. Symb. Comput., 47, 6, 610-642 (2012) · Zbl 1264.12011
[14] de Kleine, J.; Monagan, M. B.; Wittkopf, A. D., Algorithms for the non-monic case of the sparse modular GCD algorithm, (Kauers, M., Symbolic and Algebraic Computation, International Symposium ISSAC 2005. Symbolic and Algebraic Computation, International Symposium ISSAC 2005, Beijing, China, July 24-27, 2005, Proceedings (2005), ACM), 124-131 · Zbl 1360.11145
[15] Ducos, L., Algorithme de bareiss, algorithme des sous-résultants, ITA, 30, 4, 319-347 (1996) · Zbl 0868.65026
[16] Faugere, J. C., Parallelization of Gröbner Basis, Parallel Symbolic Computation PASCO 1994 Proceedings, vol. 5, 124 (1994), World Scientific
[17] Gastineau, M.; Laskar, J., Parallel sparse multivariate polynomial division, (Proceedings of PASCO 2015 (2015)), 25-33
[18] Granlund, T., The GNU multiple precision arithmetic library (2016)
[19] Hennessy, J. L.; Patterson, D. A., Computer Architecture - A Quantitative Approach (2012), Morgan Kaufmann · Zbl 0752.68014
[20] Hu, J.; Monagan, M. B., A fast parallel sparse polynomial GCD algorithm, (ISSAC 2016. ISSAC 2016, Waterloo, ON, Canada, July 19-22, 2016 (2016)), 271-278 · Zbl 1361.11082
[21] Kahoui, M. E., An elementary approach to subresultants theory, J. Symb. Comput., 35, 3, 281-292 (2003) · Zbl 1054.13014
[22] Knuth, D. E., The analysis of algorithms, The Actes du Congrés International des Mathématiciens, 3, 269-274 (1970) · Zbl 0279.68041
[23] Lehmer, D. H., Euclid’s algorithm for large numbers, Am. Math. Mon., 45, 4, 227-233 (1938) · Zbl 0018.29204
[24] Leiserson, C. E., Cilk, (Encyclopedia of Parallel Computing (2011)), 273-288
[25] Lemaire, F.; Moreno Maza, M.; Xie, Y., The regularchains library in MAPLE, ACM SIGSAM Bull., 39, 3, 96-97 (2005) · Zbl 1114.68628
[26] Maplesoft, Maple 2020 (2020), Maplesoft, a division of Waterloo Maple Inc.
[27] McCool, M.; Reinders, J.; Robison, A., Structured Parallel Programming: Patterns for Efficient Computation (2012), Elsevier
[28] Monagan, M.; Pearce, R., Parallel sparse polynomial division using heaps, (Proceedings of PASCO 2010 (2010), ACM), 105-111
[29] Monagan, M. B., Probabilistic algorithms for computing resultants, (ISSAC (2005), ACM), 245-252 · Zbl 1360.68946
[30] Monagan, M.; Tuncer, B., Factoring multivariate polynomials with many factors and huge coefficients, (International Workshop on Computer Algebra in Scientific Computing (2018), Springer), 319-334 · Zbl 1453.13072
[31] Monagan, M. B.; Tuncer, B., Sparse multivariate hensel lifting: a high-performance design and implementation, (ICMS 2018 - 6th International Conference. ICMS 2018 - 6th International Conference, South Bend, IN, USA, July 24-27, 2018, Proceedings (2018)), 359-368 · Zbl 1395.68349
[32] Moreno Maza, M.; Xie, Y., Component-level parallelization of triangular decompositions, (PASCO 2007 Proceedings (2007), ACM), 69-77
[33] Pan, W., Algorithmic contributions to the theory of regular chains (2011), University of Western Ontario: University of Western Ontario London, ON, Canada, Ph.D. thesis
[34] Saunders, B. D.; Lee, H. R.; Abdali, S. K., A parallel implementation of the cylindrical algebraic decomposition algorithm, (ISSAC, vol. 89 (1989)), 298-307
[35] Schönhage, A., Schnelle berechnung von kettenbruchentwicklungen, Acta Inform., 1, 139-144 (1971) · Zbl 0223.68008
[36] Scott, M. L., Programming Language Pragmatics (2009), Academic Press · Zbl 1005.68031
[37] Shoup, V., NTL: a library for doing number theory (2020)
[38] Thull, K.; Yap, C. K., A uni ed approach to hgcd algorithms for polynomials and integers (1990)
[39] Verschelde, J., The database of polynomial systems (2020)
[40] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2013), Cambridge University Press: Cambridge University Press NY, USA · Zbl 1277.68002
[41] Wang, P. S., An improved multivariate polynomial factoring algorithm, Math. Comput., 32, 144, 1215-1231 (1978) · Zbl 0388.10035
[42] Wang, P. S., The EEZ-GCD algorithm, ACM SIGSAM Bull., 14, 2, 50-60 (1980) · Zbl 0445.68026
[43] Xie, Y., Fast algorithms, modular methods, parallel approaches, and software engineering for solving polynomial systems symbolically (2007), University of Western Ontario: University of Western Ontario London, ON, Canada, Ph.D. thesis
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.