While the subject of triangular decomposition is primarily rooted in polynomial algebra and differential algebra, it has developed, through its applications, connections with areas like scientific computation, algebraic geometry, quantifier elimination. Moreover, software implementation of triangular decomposition are becoming more and more accessible and the range of the range of the problems that they can solve keep increasing in terms of difficulty and specification.
The objectives of the proposed workshop are twofold. First, we hope that potential users of solvers based on triangular decomposition could learn about these tools and interact with their developers. Secondly, we wish to create a synergy between the developers. Indeed, for this latter point we note that implementation techniques of triangular decomposition are a research topic on its own, at the intersection of various subjects like asymptotically fast algorithms for polynomial arithmetic, symbolic-numeric computation, parallel and distributed processing
Abstract:
Cylindrical algebraic decomposition (CAD) is a fundamental tool in
computational real algebraic geometry and has been implemented in
several software. While existing implementations are all based on
Collins' projection-lifting scheme and its subsequent ameliorations,
the implementation of CAD in the RegularChains library is based on
triangular decomposition of polynomial systems and real root isolation
of regular chains. To be more precise, this latter method first
produces a cylindrical decomposition of the complex space (CCD)
through the computation of regular GCDs, and then refines the CCD into
a CAD of the real space by isolating real roots of univariate
polynomials with real algebraic number coefficients encoded by regular
chains and isolating boxes. The function in the RegularChains library
for computing CAD is called CylindricalAlgebraicDecompose.
Today, when Maple solve's command is given a semi-algebraic system
(with explicit inequalities) and unless some simple heuristic techniques
apply, the CylindricalDecompose function is invoked.
Two different algorithms, namely a recursive one and an incremental
one, were proposed to compute CCDs in the authors' previous works.
They are implemented as the CylindricalDecompose function of the
RegularChains library.
In this talk, we report on the implementation techniques of the
incremental algorithm for computing CCDs and the operation, called
MakeSemiAlgebraic, which converts a CCD into a CAD. The tree data
structure which supports the implementation of CylindricalDecompose
and allows a CCD to be computed incrementally is described in details.
Important optimizations used in the implementation of both
CylindricalDecompose and MakeSemiAlgebraic are explained. The
function CylindricalAlgebraicDecompose supports different input
formats, such as a list of polynomials or a list of polynomial
constraints, as well as various output formats, such as piecewise, cad
type, RootOf representations, etc. The use of CAD related functions
are illustrated by examples.
This is a joint work with Marc Moreno Maza (University of Western Ontario, Canada)
Abstract: Cylindrical algebraic decompositions (CADs) are a key tool for both quantifier elimination and a range of other applications. We recently presented a new CAD algorithm which combined two advances: truth-table invariance, meaning the CAD produced is invariant with respect to the truth of logical formulae rather than the signs of polynomials; and CAD construction by first decomposing complex space using regular chains technology applied incrementally by constraint. We now consider how best to formulate problems for input to this algorithm. In particular, many problems give a choice over the variable ordering, either free or constrained. This choice can be very important, meaning the difference between a simple problem and an intractable one and even a difference in the theoretical complexity (Brown and Davenport, Proceedings of ISSAC 2007). Hence making such choices intelligently is essential for the practical use of CAD. We examine both existing and new heuristics to help with this choice in the context of the new algorithm.
Abstract: Cylindrical algebraic decomposition (CAD) is an important tool for the investigation of semi-algebraic sets. Since its introduction by Collins in the 1970s it has remained a competitive tool for quantifier elimination, and has found other applications within algebraic geometry and beyond. We describe the ProjectionCAD package for Maple. This implements routines to build cylindrical algebraic decompositions (CADs) by means of projection and lifting in real space. The routines contrast with those already present in the RegularChains Library which build CADs by first decomposing complex space. Despite this, ProjectionCAD actually uses makes use of work from the RegularChains library such as the real root isolation and stack generation commands. This means ProjectionCAD can benefit from the efficient work in the library for dealing with algebraic numbers as well as new and future improvements. It also allows for easy comparison of the different algorithms facilitating the development of new theory. Here we give an overview of the functionality in ProjectionCAD, which includes both classic and contemporary CAD algorithms, and detail how the theoretical algorithms for CAD by projecting and lifting had to be modified in order to make use of the RegularChains routines.
Abstract:
The concept of comprehensive triangular decomposition (CTD) was first introduced in
(C. Chen et al., 2007) based on triangular decomposition and can be viewed as an analogue
of comprehensive Groebner systems for parametric polynomial systems. The algorithm proposed in
(C. Chen et al., 2007) has been implemented as a main function of the Maple library RegularChains.
Following our previous work (Z. Chen et al., 2013) and (X. Tang et al., 2012)
on defining decomposition-unstable (DU) variety and generic regular decomposition (GRD) of
parametric polynomial systems, we introduce a new concept, hierarchically comprehensive
triangular decomposition (HCTD), in this talk. We also propose some algorithms for computing
HCTD based on GRD computation. Roughly
speaking, the key idea here is that we first compute a DU for a given parametric system (with
d parameters) and a CTD of the system for the parameter values in the complement of the
DU in the parametric space. Note that the complement is of dimension d. Second, we call
recursively the same procedure to compute a CTD for parameter values on the DU whose
dimension is strictly less than d. By these recursive calls, we will finally get finitely many
CTDs of the system for parameters of different dimensions. That is why these CTDs are
named hierarchically comprehensive triangular decomposition. Our algorithms have been
implemented as a Maple program HCTD and experimented with a number of benchmarks
from the literature.
Comparison to ComprehensiveTriangularize (CTD for short) of RegularChains are reported.
Although HCTD is faster than CTD on part of the experiments, it is slower on major
part of the experiments. However, for some hard problems on which both HCTD and CTD
cannot get final results, HCTD can provide partial solutions, which means some HCTDs for
almost all parameter values (except some parameter values of lower dimensions). It is an
advantage of our algorithms. We believe that trying different triangular decomposition
methods and optimizing the codes will greatly improve the performance of our program.
This is a joint work with Zhenghong Chen and Bican Xia (Peking University, China).
Abstract: Traditionally, Groebner bases and Cylindrical Algebraic Decomposition are the fundamental tools of Computational Algebraic Geometry. Recent progress in the theory of regular chains has exhibited efficient algorithms for doing local analysis in algebraic varieties, In this talk, we present the implementation of these new ideas within the RegularChains Library. We start by the computation of the (non-trivial) limit points of the quasi-component of a regular chain. This type of calculation can be used to compute the Zarisky closure of a constructible set. Next, we show that these latter computations can be used to calculate tangent cones of space curves, thus providing an alternative to the standard basis approach. From there we derive an algorithm which, under genericity assumptions, computes the intersection multiplicity of a zero-dimensional variety at any of its points. This algorithm relies only on regular chain manipulations, that is no Groebner bases or standard bases are involved.
Slides.
Abstract:
Ore matrices are matrices over Ore algebras (including
differential operators and difference operators). It has a long
research history, at least dated back to Jacobson's seminal work
in 1940s. In past ten years, Ore matrices have attracted more and
more people in computer algebra area, and many important
properties of Ore matrices have been discussed by using symbolic
computation methods, for example, various fast algorithms for
computing Hermite forms and Smith forms, fraction-free algorithms
for computing Popov forms. In this paper, we consider
Moore-Penrose pseudo inverse of Ore matrices. The definition is
similar to commutative case. It is well-known that every matrix
over a field has a MP pseudo inverse. But it is not true for Ore
matrices in general. At first, we use blocked matrices and GCD
computations to give some sufficient and necessary conditions for
Ore matrices to have MP pseudo inverses. Then when MP pseudo
inverses exist, we develop algorithms to compute them. All
algorithms are implemented in the symbolic programming language
Maple, and tested on examples. To our best knowledge, it is the
first Maple package in this direction. Finally we explore some
possible applications of MP pseudo inverse of Ore matrices in
solving systems of differential(difference) equations.
Slides.
Abstract:
Multivariate Birkhoff rational interpolation is the most general
algebraic interpolation scheme. The key character of Birkhoff
interpolation is that the orders of the derivative conditions at some
nodes are non-continuous. Without the non-continuity it degenerates
into an Hermit interpola- tion. Setting the denominator as 1 it
degenerates into a polynomial interpolation. Due to the non-continuity
and the complicated constructive of the multivariate rational
function, we can hardly solve the problem by the linearization
techniques which are widely applied in solving the Hermit ra- tional
interpolation problem. In this paper we propose a parametric
linearization method to convert the original problem into solving a
parametric polynomial system. By adding the lacking deriva- tive
conditions and setting the artificial interpolating values as unknown
parameters, we obtain a parametric Hermit rational interpolation
problem. Then it can be dealt with using the linearization
techniques. As a result the multivariate Birkhoff rational
interpolation problem is converted into a parametric polynomial system
in which the coefficients in the numerator and denominator are the
unknowns. We use the parametric triangular decomposition to solve the
system and prove the solution provides a Birkhoff rational
interpolation function as long as there exist proper parameters such
that the denominator does not vanish at each interpolating point. We
implement the algorithm in Maple 15 with the ’RegularChains’ library.
This is a joint work with Peng Xia (Liaoning University, Shenyang, China).
Abstract: In their paper Boulier et al. (2009) described the Rosenfeld-Grobneralgorithm for computing a regular decomposition of a radicaldifferential ideal generated by a set of polynomial differentialequations, ordinary or with partial derivatives. In order to enhancethe efficiency of this algorithm, they proposed their analog ofBuchberger criteria to avoid useless reductions to zero. For example,they showed that if p and q are two differential polynomials whichare linear, homogeneous, in one differential indeterminate, withconstant coefficients and with leaders Au and Bu, respectively sothat A and B are disjoint then the delta-polynomial of p and q reducesto zero w.r.t. p and q. In this paper we generalize this resultshowing that it remains true if p and q are products of differentialpolynomials which are linear, homogeneous, in the same differentialindeterminate, with constant coefficients and A and B are disjointwhere Au and Bu are leaders of p and q, respectively. We haveimplemented the Rosenfeld-Grobner algorithm and our refined versionon the same platform in Maple and compare them via a set ofbenchmarks. This is a joint work with Zahra Touraji (IsfahanUniversity of Technology, Iran).
Slides.
Abstract:
Motivated by the problem of determining the Jordan and Weyr
canonical forms of parametric matrices, this paper addresses the
problem of computing the Frobenius (Rational) normal form of
parametric matrices.
In other words, we study matrices over a field of
multivariate rational functions, whose indeterminates are
regarded as parameters and are restricted by either
polynomial equations represented as a constructible set or by
polynomial equations and inequalities represented by a
semi-algebraic set.
Since the Frobenius form similar to a parametric matrix is
discontinuous in its parameters the algorithm must compute a
partition of the input constructible or semi-algebraic set
such that a unique Frobenius form arises in each partition.
The proposed algorithm relies on the theory of regular chains
and its implementation on top of the RegularChains library,
applied to various examples from the literature illustrating
the effectiveness of our approach.
A brief discussion of the cost of the implementation is
presented including timing over both the real and complex
cases with varying numbers of parameters.