Parallelization of triangular decompositions: Techniques and implementation. (March 2023)

• Record Type: Journal Article
• Authors: Asadi, Mohammadali; Brandt, Alexander; Moir, Robert H.C.; Moreno Maza, Marc; Xie, Yuzhen
• Is Part Of: Journal of symbolic computation. Volume 115(2023)
• Page Start: 371
• Page End: 406
• Publication Date: 2023-03
• Subjects: Polynomial system solving -- Parallel processing -- Triangular decomposition -- Regular chains -- Irregular parallelism -- Producer-consumer problem; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.08.015
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We discuss the parallelization of algorithms for solving polynomial systems by way of triangular decomposition. The Triangularize algorithm proceeds through incremental intersections of polynomials to produce different components (points, curves, surfaces, etc.) of the solution set. Independent components imply the opportunity for concurrency. This "component-level" parallelization of triangular decompositions, our focus here, belongs to the class of dynamic irregular parallelism. Potential parallel speed-up depends only on geometrical properties of the solution set (number of components, their dimensions and degrees); these algorithms do not scale with the number of processors. To manage the irregularities of component-level parallelization we combine different concurrency patterns: map, workpile, producer-consumer, pipeline, and fork-join. We report on our implementation in the freely available BPAS library. Comprehensive experimentation with thousands of polynomial systems yields examples with up to 10.8× speed-up on a 12-core machine.