ABSTRACT Polyhedral compilers and tensor compilers have achieved great success on accelerating scientific computing kernels and deep learning networks, respectively. Although much work has been done to integrate techniques of the polyhedral model to tensor compilers for accelerating deep learning, leveraging the powerful auto‐tuning ability of modern tensor compilers to accelerate more general scientific computing kernels is challenging and is still at its dawn. In this work, we introduce a method to accelerate a family of basic scientific computing kernels by fusing the polyhedral compiler Pluto and the tensor compiler Tensor Virtual Machine (TVM) to generate efficient implementations targeting the heterogeneous CPU/GPU platform. The fusion is done in four steps: building a polyhedral model for the loop description of a given scientific kernel; designing schedules to transform the polyhedral model to new ones to enable rectangular tiling and expose explicit parallelism; selecting a new polyhedral model and converting it to the tensor compute representation; auto‐tuning the tensor compute to generate efficient implementations on both CPUs and GPUs. Shifting and padding optimizations are also considered to avoid conditionals. Experiments on 30 typical scientific computing kernels show that our method achieves speedup on average over a typical polyhedral compiler PPCG on GPU.

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.