Parallelization of triangular decompositions: techniques and implementation
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 [\textit{M. Moreno Maza} and \textit{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; \url{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.
- Algorithms for computing triangular decompositions of polynomial systems
- A blackbox polynomial system solver on parallel shared memory computers
- Algorithms for computing triangular decomposition of polynomial systems
- Parallel Homotopy Algorithms to Solve Polynomial Systems
- Improved parallel solution of a triangular linear system
- A fast parallel sparse polynomial GCD algorithm
- Algorithme de Bareiss, algorithme des sous-résultants
- Algorithms for computing triangular decomposition of polynomial systems
- Algorithms for the non-monic case of the sparse modular GCD algorithm
- An elementary approach to subresultants theory.
- An Improved Multivariate Polynomial Factoring Algorithm
- Database of Polynomial Systems
- Euclid's Algorithm for Large Numbers
- Factoring multivariate polynomials with many factors and huge coefficients
- Fast computation of continued fraction expansions.
- scientific article; zbMATH DE number 5722788 (Why is no real title available?)
- scientific article; zbMATH DE number 47171 (Why is no real title available?)
- scientific article; zbMATH DE number 53772 (Why is no real title available?)
- scientific article; zbMATH DE number 1263425 (Why is no real title available?)
- scientific article; zbMATH DE number 3440002 (Why is no real title available?)
- scientific article; zbMATH DE number 1821697 (Why is no real title available?)
- Modern computer algebra
- NTL
- On the parallelization of triangular decompositions
- On the theories of triangular sets
- Parallel algorithms for normalization
- Parallel sparse polynomial multiplication on modern hardware architectures
- Probabilistic algorithms for computing resultants
- RegularChains
- Sparse multivariate Hensel lifting: a high-performance design and implementation
- Strategy-accurate parallel Buchberger algorithms
- The EEZ-GCD algorithm
- The RegularChains library in Maple 10
- A unified approach to parallel space decomposition methods
- On designing optimal parallel triangular solvers.
- Dimension-wise decompositions and their efficient parallelization
- Parallel and Heterogeneous m--Hessenberg--Triangular--Triangular Reduction
- A Modular Algorithm for Computing the Intersection of a One-Dimensional Quasi-Component and a Hypersurface
Uses Software
This page was built for publication: Parallelization of triangular decompositions: techniques and implementation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2674015)
