Fourier-Motzkin elimination is a fundamental operation in polyhedral geometry. It can be performed by several equivalent procedures, and can be regarded as an adaptation of Gaussian elimination to systems of linear inequalities. These procedures tend to generate large numbers of redundant inequalities. Efficiently detecting these redundancies is essential for obtaining software implementation of practical interest. In this paper, we propose a novel detection technique. We demonstrate its benefits over alternative approaches. A detailed experimentation is reported.

Fourier-Motzkin elimination is a fundamental operation in polyhedral geometry. It can be performed by several equivalent procedures, which can be regarded as an adaptation of Gaussian elimination to systems of linear inequalities. These procedures tend to generate large numbers of redundant inequalities. Efficiently detecting these redundancies is essential to obtain software implementation of practical interest. In this paper, we propose a detection technique. We demonstrate its benefits over alternative approaches. A detailed experimentation is reported.

tutorial Design and Implementation of Multi-Threaded Algorithms in Polynomial Algebra Share on Author: Marc Moreno Maza University of Western Ontario, London, ON, Canada University of Western Ontario, London, ON, CanadaSearch about this author Authors Info & Claims ISSAC '21: Proceedings of the 2021 on International Symposium on Symbolic and Algebraic ComputationJuly 2021 Pages 15–20https://doi.org/10.1145/3452143.3465511Online:18 July 2021Publication History 0citation40DownloadsMetricsTotal Citations0Total Downloads40Last 12 Months40Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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, namely, workpile, producer-consumer, and fork/join. We report on our implementation in the freely available BPAS library. Experimentation with thousands of polynomial systems yield examples with up to 9.5× speed-up on a 12-core machine.

We propose a new geometric regularization principle for reconstructing vector fields based on prior knowledge about their divergence. As one important example of this general idea, we focus on vector fields modelling blood flow pattern that should be divergent in arteries and convergent in veins. We show that this previously ignored regularization constraint can significantly improve the quality of vessel tree reconstruction particularly around bifurcations where non-zero divergence is concentrated. Our divergence prior is critical for resolving (binary) sign ambiguity in flow orientations produced by standard vessel filters, \eg Frangi. Our vessel tree centerline reconstruction combines divergence constraints with robust curvature regularization. Our unsupervised method can reconstruct complete vessel trees with near-capillary details on synthetic and real 3D volumes.

We report on a multi-threaded implementation of Fast Fourier Transforms over generalized Fermat prime fields. This work extends a previous study realized on graphics processing units to multi-core processors. In this new context, we overcome the less fine control of hardware resources by successively using FFT in support of the multiplication in those fields. We obtain favorable speedup factors (up to 6.9x on a 6-core, 12 threads node, and 4.3x on a 4-core, 8 threads node) of our parallel implementation compared to the serial implementation for the overall application thanks to the low memory footprint and the sharp control of arithmetic instructions of our implementation of generalized Fermat prime fields.

The Extended Hensel Construction (EHC) is a procedure which, for an input bivariate polynomial with complex coefficients, can serve the same purpose as the Newton-Puiseux algorithm, and, for the multivariate case, can be seen as an effective variant of Jung-Abhyankar Theorem. We show that the EHC requires only linear algebra and univariate polynomial arithmetic. We deduce complexity estimates and report on a software implementation together with experimental results. This work is motivated and illustrated by the computation of real branches of space curves.

We consider prime fields of large characteristic, typically fitting on $k$ machine words, where k is a power of 2. When the characteristic of these fields is restricted to a subclass of the generalized Fermat numbers, we show that arithmetic operations in such fields offer attractive performance, both in terms of algebraic complexity and parallelism. In particular, these operations can be vectorized, leading to efficient implementation of fast Fourier transforms on graphics processing units.

We present an algorithm for determining the existence of the limit of a real multivariate rational function q at a given point which is an isolated zero of the denominator of q. When the limit exists, the algorithm computes it, without making any assumption on the number of variables.

A quantifier elimination algorithm by cylindrical algebraic decomposition based on regular chains is presented. The main idea is to refine a complex cylindrical tree until the signs of polynomials appearing in the tree are sufficient to distinguish the true and false cells. We report on an implementation of our algorithm in the RegularChains library in Maple and illustrate its effectiveness by examples.

This article is a continuation of our earlier work [3], which introduced triangular decompositions of semi-algebraic systems and algorithms for computing them. Our new contributions include theoretical results based on which we obtain practical improvements for these decomposition algorithms.

We propose new algorithms for computing triangular decompositions of polynomial systems incrementally. With respect to previous works, our improvements are based on a weakened notion of a polynomial GCD modulo a regular chain, which permits to greatly simplify and optimize the sub-algorithms. Extracting common work from similar expensive computations is also a key feature of our algorithms. In our experimental results the implementation of our new algorithms, realized with the RegularChains library in MAPLE, outperforms solvers with similar specifications by several orders of magnitude on sufficiently difficult problems.

Regular chains and triangular decompositions are fundamental and well-developed tools for describing the complex solutions of polynomial systems. This paper proposes adaptations of these tools focusing on solutions of the real analogue: semi-algebraic systems.

Cylindrical algebraic decomposition is one of the most important tools for computing with semi-algebraic sets, while triangular decomposition is among the most important approaches for manipulating constructible sets. In this paper, for an arbitrary finite set F ⊂ [y1,...,yn] we apply comprehensive triangular decomposition in order to obtain an F-invariant cylindrical decomposition of the n-dimensional complex space, from which we extract an F-invariant cylindrical algebraic decomposition of the n-dimensional real space. We report on an implementation of this new approach for constructing cylindrical algebraic decompositions.

The computation of triangular decompositions involve two fundamental operations: polynomial GCDs modulo regular chains and regularity test modulo saturated ideals. We propose new algorithms for these core operations based on modular methods and fast polynomial arithmetic. We rely on new results connecting polynomial subresultants and GCDs modulo regular chains. We report on extensive experimentation, comparing our code to pre-existing Maple implementations, as well as more optimized Magma functions. In most cases, our new code outperforms the other packages by several orders of magnitude.

In symbolic computation, polynomial multiplication is a fundamental operation akin to matrix multiplication in numerical computation. We present efficient implementation strategies for FFT-based dense polynomial multiplication targeting multi-cores. We show that balanced input data can maximize parallel speedup and minimize cache complexity for bivariate multiplication. However, unbalanced input data, which are common in symbolic computation, are challenging. We provide efficient techniques, what we call contraction and extension, to reduce multivariate (and univariate) multiplication to balanced bivariate multiplication. Our implementation in Cilk++ demonstrates good speedup on multi-cores.

Given a regular chain T, we aim at finding an efficient way for computing a system of generators of Sat(T), the saturated ideal of T. A natural idea is to test whether the equality {T}=Sat(T) holds, that is, whether T generates its saturated ideal. By generalizing the notion of primitivity from univariate polynomials to regular chains, we establish a necessary and sufficient condition, together with a Grobner basis free algorithm, for testing this equality. Our experimental results illustrate the efficiency of this approach in practice.

Given a real parametric polynomial p(x) and an interval (a,b) ⊂ R, the Complete Root Classification (CRC) of p(x) on (a,b) is a collection of all possible cases of its root classification on (a,b), together with the conditions its coefficients must satisfy for each case. In this paper, a new algorithm is proposed for the automatic computation of the complete root classification of a parametric polynomial on an interval. As a direct application, the new algorithm is applied to some real quantifier elimination problems.

We study arithmetic operations for triangular families of polynomials, concentrating on multiplication in dimension zero. By a suitable extension of fast univariate Euclidean division, we obtain theoretical and practical improvements over a direct recursive approach; for a family of special cases, we reach quasi-linear complexity. The main outcome we have in mind is the acceleration of higher-level algorithms, by interfacing our low-level implementation with languages such as AXIOM or Maple We show the potential for huge speed-ups, by comparing two AXIOM implementations of van Hoeij and Monagan's modular GCD algorithm.

Though there is increased activity in the implementation of asymptotically fast polynomial arithmetic, little is reported on the details of such effort. In this paper, we discuss how we achieve high performance in implementing some well-studied fast algorithms for polynomial arithmetic in two high-level programming environments, AXIOM and Aldor.Two approaches are investigated. With Aldor we rely only on high-level generic code, whereas with AXIOM we endeavor to mix high-level, middle-level and low-level specialized code. We show that our implementations are satisfactory compared with other known computer algebra systems or libraries such as Magma v2.11-2 and NTL v5.4.

Triangular decompositions are one of the major tools for solving polynomial systems. For systems of algebraic equations, they provide a convenient way to describe complex solutions and a step toward isolation of real roots or decomposition into irreducible components. Combined with other techniques, they are used for these purposes by several computer algebra systems. For systems of partial differential equations, they provide the main practicable way for determining a symbolic description of the solution set. Moreover, thanks to Rosenfeld's Lemma, techniques from the algebraic case apply to the differential one [3].Research in this area is following the natural cycle: theory, algorithms, implementation, which will be the main theme of this tutorial. We shall also concentrate on the algebraic case and mention the differential one among the applications.Theory. The concept of a characteristic set, introduced by Ritt [14], is the cornerstone of the theory. He described an algorithm for solving polynomial systems by factoring in field extensions and computing characteristic sets of prime ideals. Wu [16] obtained a factorization-free adaptation of Ritt's algorithm. Several authors continued and improved Wu's approach: Chou, Gao [4], Gallo, Mishra [10] Wang [15] and others. Considering characteristic sets of non-prime ideals leads to difficulties that were overcome by Kalkbrener [11] and, Yang and Zhang [17] who defined particular characteristic sets, called regular chains. See also the work of Lazard and his students [1]. The first part of this tutorial will be an introduction to this notion for a general audience.Algorithms. Regular chains, combined with the D5 Principle [8] and a notion of polynomial GCD [13], have also contributed to improve the efficiency of algorithms for computing triangular decompositions, as reported in [2]. To go further, complexity estimates of the output regular chains were needed. Such results were provided by Dahan and Schost [7]. Together with the notion of equiprojectable decomposition, they have led to the first modular algorithm for computing triangular decompositions [5]. The second part of this tutorial will focus on polynomial GCDs modulo regular chains. Using the RegularChains library [12] in Maple, we will show how they are used for producing equiprojectable decomposition.Implementation. This is certainly the hot topic today. Obtaining fast algorithms for the low-level routines used in triangular decompositions [6] and developing implementation techniques for them [9] are the priorities that we shall discuss in the last part of this tutorial.

Since the discovery of Gröbner bases, the algorithmic advances in Commutative Algebra have made possible to tackle many classical problems in Algebraic Geometry that were previously out of reach. However, algorithmic progress is still desirable, for instance when solving symbolically a large system of algebraic non-linear equations. For such a system, in particular if its solution set consists of geometric components of different dimension (points, curves, surfaces, etc) it is necessary to combine Gröbner bases with decomposition techniques, such as triangular decompositions. Ideally, one would like each of the different components to be produced by an independent processor, or set of processors. In practice, the input polynomial system, which is hiding those components, requires some transformations in order to split the computations into sub-systems and, then, lead to the desired components. The efficiency of this approach depends on its ability to detect and exploit geometrical information during the solving process.Our work addresses two questions: How to discover geometrical information, at an early stage of the solving process, that would be favorable to parallel execution? How to ensure load balancing among the processors? We answer these questions in the context of triangular decompositions [2] which are a popular way of solving polynomial systems symbolically. These methods tend to split the input polynomial system into subsystems and, therefore, are natural candidate for parallel implementation. However, the only such method which has been parallelized so far is the Characteristic Set Method of Wu [5], as reported in [1, 6]. This approach suffers from several limitations. For instance, the solving of the second component cannot start before that of the first one is completed; this is a limitation in view of coarse-grain parallelization.In [4] an algorithm, called Triade, for TRIAngular DEcompositions, provides a good management of the intermediate computations for triangular decompositions. It is also a natural candidate for coarse-grain parallel implementation based on geometrical considerations; indeed the number of working processors can depend on the intrinsic difficulty of the system to solve. However, several challenges remain to be considered. First, load balancing is very difficult to control due to irregular tasks. Even worse: for some input polynomial systems, especially with integer coefficients, resource consuming tasks may not be necessarily executed concurrently. Second, data communication overhead can be very heavy due to large intermediate results.In order to achieve load balancing we rely on the following facts. For an input polynomial system, the Triade algorithm generates the intermediate or output components by decreasing order of dimension. As a consequence, expensive tasks (those in lower dimension) can be processed concurrently. In addition, when solving a (non-trivial) polynomial system modulo a prime integer, the number of these tasks is sufficient for expecting a good speed-up in a parallel execution. The case of polynomial systems with integer coefficients can also benefit from these features by using the modular techniques introduced in [3].We have developed a parallel scheme for the Triade algorithm, aiming at minimizing data communication overhead. Tasks are scheduled and updated by a process manager. Individual tasks are solved "lazily" by process workers. However, each process worker keeps track of enough information such that it can continue the solving of some of these tasks, when needed.We have realized a preliminary implementation on a shared memory multiprocessor. The experimental results show a satisfactory speed-up for some well-known problems.

We present lifting techniques for triangular decompositions of zero-dimensional varieties, that extend the range of the previous methods. We discuss complexity aspects, and report on a preliminary implementation. Our theoretical results are comforted by these experiments. Categories and Subject Descriptors: I.I.2 [Computing

In this paper we conduct a careful study of the equivalence classes of ternary cubics under general complex linear changes of variables. Our new results are based on the method of moving frames and involve triangular decompositions of algebraic varieties. We provide a computationally efficient algorithm that matches an arbitrary ternary cubic with its canonical form and explicitly computes a corresponding linear change of coordinates. We also describe a classification of the symmetry groups of ternary cubics.

We propose a new algorithm for converting a characteristic set of a prime differential ideal from one ranking into another. This differential algebra algorithm computes characteristic sets by change of ranking (ordering) for prime ideals. It identifies the purely algebraic subproblems which arise during differential computations and solves them algebraically. There are two improvements w.r.t. other approaches: formerly unsolved problems could be carried out; it is conceptually simple. Different variants are implemented.

We show how the triangularization method of the second author can be successfully applied to the problem of classification of homogeneous coupled integrable equations. The classifications rely on the recent algorithm developed by the first author that requires solving 17 systems of polynomial equations. We show that these systems can be completely resolved in the case of coupled Korteweg-de Vries, Sawada-Kotera and Kaup-Kupershmidt—type equations.