ICMS 2014 Session: Software, design and practice in triangular decompositions of polynomial systems

ICMS 2014: Home, Sessions

Organizers

Aim and Scope

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

Topics (including, but not limited to)

Publications

Submission Guidelines

Talks/Abstracts

  1. Cylindrical Algebraic Decomposition in the RegularChains Library

    Changbo Chen (CIGIT, Chinese Academy of Sciences)
    Marc Moreno Maza (University of Western Ontario)

    Slides.


    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)

  2. Choosing variable orderings for truth-table invariant CAD by incremental triangular decomposition

    James Davenport (University of Bath, UK)
    Russell Bradford (University of Bath, UK)
    Matthew England (University of Bath, UK)
    David Wilson (University of Bath, UK)

    Slides.

    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.

  3. Using the RegularChains Library to build CADs by projecting and lifting

    Matthew England (University of Bath, UK)
    James Davenport (University of Bath, UK)
    Russell Bradford (University of Bath, UK)
    David Wilson (University of Bath, UK)

    Slides.

    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.

  4. Hierarchically Comprehensive Triangular Decomposition

    Zhenghong Chen (Peking University, China)
    Xiaoxian Tang (Peking University, China)
    Bican Xia (Peking University, China)

    Slides.


    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).

  5. Doing Algebraic Geometry with the RegularChains Library

    Parisa Alvandi (University of Western Ontario)
    Changbo Chen (CIGIT, Chinese Academy of Sciences)
    Steffen Marcus (College of New Jersey)
    Marc Moreno Maza (University of Western Ontario)
    Eric Schost (University of Western Ontario)
    Paul Vrbik (University of Western Ontario)

    Slides.

    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.

  6. Computing Moore-Penrose pseudo-inverses of Ore matrices

    Yang Zhang (University of Manitoba, Canada)

    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.

  7. On multivariate Birkhoff rational interpolation problem

    Peng Xia School of Mathematics, Liaoning University, Shenyang, China
    Bao-Xin Shang Institute of Mathematics, Jilin University, Changchun, China
    Na Lei Key Lab. of Symbolic Computation and Knowledge Engineering, Jilin University, Changchun, China

    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).

  8. An Improvement of Rosenfeld-Groebner Algorithm

    Amir Hashemi (IPM & Isfahan University of Technology, Iran)
    Zahra Touraji (Isfahan University of Technology, Iran)

    Slides.

    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).

  9. Frobenius Normal Form over Families of Parametric Matrices

    Robert M. Corless (University of Western Ontario, Canada)
    Steven Thorton (University of Western Ontario, Canada)

    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.