The Experts below are selected from a list of 5817 Experts worldwide ranked by ideXlab platform
Changbo Chen - One of the best experts on this subject based on the ideXlab platform.
-
chordality preserving incremental Triangular Decomposition and its implementation
International Congress on Mathematical Software, 2020Co-Authors: Changbo ChenAbstract:In this paper, we first prove that the incremental algorithm for computing Triangular Decompositions proposed by Chen and Moreno Maza in ISSAC’ 2011 in its original form preserves chordality, which is an important property on sparsity of variables. On the other hand, we find that the current implementation in Triangularize command of the RegularChains library in Maple may not always respect chordality due to the use of some simplification operations. Experimentation show that modifying these operations, together with some other optimizations, brings significant speedups for some super sparse polynomial systems.
-
problem formulation for truth table invariant cylindrical algebraic Decomposition by incremental Triangular Decomposition
arXiv: Symbolic Computation, 2014Co-Authors: Matthew England, Changbo Chen, Marc Moreno Maza, Russell Bradford, James H Davenport, David WilsonAbstract:Cylindrical algebraic Decompositions (CADs) are a key tool for solving problems in real algebraic geometry and beyond. We recently presented a new CAD algorithm combining two advances: truth-table invariance, making the CAD invariant with respect to the truth of logical formulae rather than the signs of polynomials; and CAD construction by regular chains technology, where first a complex Decomposition is constructed by refining a tree incrementally by constraint. We here consider how best to formulate problems for input to this algorithm. We focus on a choice (not relevant for other CAD algorithms) about the order in which constraints are presented. We develop new heuristics to help make this choice and thus allow the best use of the algorithm in practice. We also consider other choices of problem formulation for CAD, as discussed in CICM 2013, revisiting these in the context of the new algorithm.
-
algorithms for computing Triangular Decomposition of polynomial systems
Journal of Symbolic Computation, 2012Co-Authors: Changbo Chen, Marc Moreno MazaAbstract:We discuss algorithmic advances which have extended the pioneer work of Wu on Triangular Decompositions. We start with an overview of the key ideas which have led to either better implementation techniques or a better understanding of the underlying theory. We then present new techniques that we regard as essential to the recent success and for future research directions in the development of Triangular Decomposition methods.
-
computing with semi algebraic sets represented by Triangular Decomposition
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Changbo Chen, Marc Moreno Maza, James H Davenport, Bican Xia, Rong XiaoAbstract: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 exhibit new results on the theory of border polynomials of parametric semi-algebraic systems: in particular a geometric characterization of its "true boundary" (Definition 2). In order to optimize these algorithms, we also propose a technique, that we call relaxation, which can simplify the Decomposition process and reduce the number of redundant components in the output. Moreover, we present procedures for basic set-theoretical operations on semi-algebraic sets represented by Triangular Decomposition. Experimentation confirms the effectiveness of our techniques.
-
Triangular Decomposition of semi algebraic systems
International Symposium on Symbolic and Algebraic Computation, 2010Co-Authors: Changbo Chen, Marc Moreno Maza, James H Davenport, Bican Xia, John P May, Rong XiaoAbstract: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.We show that any such system can be decomposed into finitely many regular semi-algebraic systems. We propose two specifications of such a Decomposition and present corresponding algorithms. Under some assumptions, one type of Decomposition can be computed in singly exponential time w.r.t. the number of variables. We implement our algorithms and the experimental results illustrate their effectiveness.
Marc Moreno Maza - One of the best experts on this subject based on the ideXlab platform.
-
On the Parallelization of Triangular Decomposition of Polynomial Systems.
arXiv: Symbolic Computation, 2019Co-Authors: Mohammadali Asadi, Marc Moreno Maza, Alexander Brandt, Robert H. C. Moir, Yuzhen XieAbstract:We discuss the parallelization of algorithms for solving polynomial systems symbolically by way of Triangular Decomposition. Algorithms for solving polynomial systems combine low-level routines for performing arithmetic operations on polynomials and high-level procedures which produce the different components (points, curves, surfaces) of the solution set. The latter "component-level" parallelization of Triangular Decompositions, our focus here, belongs to the class of dynamic irregular parallel applications. Possible speedup factors depend on geometrical properties of the solution set (number of components, their dimensions and degrees); these algorithms do not scale with the number of processors. In this paper we combine two different concurrency schemes, the fork-join model and producer-consumer patterns, to better capture opportunities for component-level parallelization. We report on our implementation with the publicly available BPAS library. Our experimentation with 340 systems yields promising results.
-
problem formulation for truth table invariant cylindrical algebraic Decomposition by incremental Triangular Decomposition
arXiv: Symbolic Computation, 2014Co-Authors: Matthew England, Changbo Chen, Marc Moreno Maza, Russell Bradford, James H Davenport, David WilsonAbstract:Cylindrical algebraic Decompositions (CADs) are a key tool for solving problems in real algebraic geometry and beyond. We recently presented a new CAD algorithm combining two advances: truth-table invariance, making the CAD invariant with respect to the truth of logical formulae rather than the signs of polynomials; and CAD construction by regular chains technology, where first a complex Decomposition is constructed by refining a tree incrementally by constraint. We here consider how best to formulate problems for input to this algorithm. We focus on a choice (not relevant for other CAD algorithms) about the order in which constraints are presented. We develop new heuristics to help make this choice and thus allow the best use of the algorithm in practice. We also consider other choices of problem formulation for CAD, as discussed in CICM 2013, revisiting these in the context of the new algorithm.
-
algorithms for computing Triangular Decomposition of polynomial systems
Journal of Symbolic Computation, 2012Co-Authors: Changbo Chen, Marc Moreno MazaAbstract:We discuss algorithmic advances which have extended the pioneer work of Wu on Triangular Decompositions. We start with an overview of the key ideas which have led to either better implementation techniques or a better understanding of the underlying theory. We then present new techniques that we regard as essential to the recent success and for future research directions in the development of Triangular Decomposition methods.
-
computing with semi algebraic sets represented by Triangular Decomposition
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Changbo Chen, Marc Moreno Maza, James H Davenport, Bican Xia, Rong XiaoAbstract: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 exhibit new results on the theory of border polynomials of parametric semi-algebraic systems: in particular a geometric characterization of its "true boundary" (Definition 2). In order to optimize these algorithms, we also propose a technique, that we call relaxation, which can simplify the Decomposition process and reduce the number of redundant components in the output. Moreover, we present procedures for basic set-theoretical operations on semi-algebraic sets represented by Triangular Decomposition. Experimentation confirms the effectiveness of our techniques.
-
Triangular Decomposition of semi algebraic systems
International Symposium on Symbolic and Algebraic Computation, 2010Co-Authors: Changbo Chen, Marc Moreno Maza, James H Davenport, Bican Xia, John P May, Rong XiaoAbstract: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.We show that any such system can be decomposed into finitely many regular semi-algebraic systems. We propose two specifications of such a Decomposition and present corresponding algorithms. Under some assumptions, one type of Decomposition can be computed in singly exponential time w.r.t. the number of variables. We implement our algorithms and the experimental results illustrate their effectiveness.
Lu Yang - One of the best experts on this subject based on the ideXlab platform.
-
computing cylindrical algebraic Decomposition via Triangular Decomposition
International Symposium on Symbolic and Algebraic Computation, 2009Co-Authors: Changbo Chen, Marc Moreno Maza, Bican Xia, Lu YangAbstract: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.
-
Computing Cylindrical Algebraic Decomposition via Triangular Decomposition
arXiv: Symbolic Computation, 2009Co-Authors: Changbo Chen, Marc Moreno Maza, Lu YangAbstract: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 \subset {\R}[y_1, ..., y_n]$ 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.
Bican Xia - One of the best experts on this subject based on the ideXlab platform.
-
hierarchical comprehensive Triangular Decomposition
arXiv: Symbolic Computation, 2014Co-Authors: Zhenghong Chen, Xiaoxian Tang, Bican XiaAbstract:The concept of comprehensive Triangular Decomposition (CTD) was first introduced by Chen et al. in their CASC'2007 paper and could be viewed as an analogue of comprehensive Grobner systems for parametric polynomial systems. The first complete algorithm for computing CTD was also proposed in that paper and implemented in the RegularChains library in Maple. Following our previous work on generic regular Decomposition for parametric polynomial systems, we introduce in this paper a so-called hierarchical strategy for computing CTDs. Roughly speaking, for a given parametric system, the parametric space is divided into several sub-spaces of different dimensions and we compute CTDs over those sub-spaces one by one. So, it is possible that, for some benchmarks, it is difficult to compute CTDs in reasonable time while this strategy can obtain some "partial" solutions over some parametric sub-spaces. The program based on this strategy has been tested on a number of benchmarks from the literature. Experimental results on these benchmarks with comparison to RegularChains are reported and may be valuable for developing more efficient Triangularization tools.
-
computing with semi algebraic sets represented by Triangular Decomposition
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Changbo Chen, Marc Moreno Maza, James H Davenport, Bican Xia, Rong XiaoAbstract: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 exhibit new results on the theory of border polynomials of parametric semi-algebraic systems: in particular a geometric characterization of its "true boundary" (Definition 2). In order to optimize these algorithms, we also propose a technique, that we call relaxation, which can simplify the Decomposition process and reduce the number of redundant components in the output. Moreover, we present procedures for basic set-theoretical operations on semi-algebraic sets represented by Triangular Decomposition. Experimentation confirms the effectiveness of our techniques.
-
Triangular Decomposition of semi algebraic systems
International Symposium on Symbolic and Algebraic Computation, 2010Co-Authors: Changbo Chen, Marc Moreno Maza, James H Davenport, Bican Xia, John P May, Rong XiaoAbstract: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.We show that any such system can be decomposed into finitely many regular semi-algebraic systems. We propose two specifications of such a Decomposition and present corresponding algorithms. Under some assumptions, one type of Decomposition can be computed in singly exponential time w.r.t. the number of variables. We implement our algorithms and the experimental results illustrate their effectiveness.
-
Triangular Decomposition of semi algebraic systems
arXiv: Symbolic Computation, 2010Co-Authors: Changbo Chen, Marc Moreno Maza, James H Davenport, Bican Xia, John P May, Rong XiaoAbstract: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. We show that any such system can be decomposed into finitely many {\em regular semi-algebraic systems}. We propose two specifications of such a Decomposition and present corresponding algorithms. Under some assumptions, one type of Decomposition can be computed in singly exponential time w.r.t.\ the number of variables. We implement our algorithms and the experimental results illustrate their effectiveness.
-
computing cylindrical algebraic Decomposition via Triangular Decomposition
International Symposium on Symbolic and Algebraic Computation, 2009Co-Authors: Changbo Chen, Marc Moreno Maza, Bican Xia, Lu YangAbstract: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.
James H Davenport - One of the best experts on this subject based on the ideXlab platform.
-
choosing a variable ordering for truth table invariant cylindrical algebraic Decomposition by incremental Triangular Decomposition
arXiv: Symbolic Computation, 2014Co-Authors: Matthew England, Russell Bradford, James H Davenport, David WilsonAbstract:Cylindrical algebraic Decomposition (CAD) is a key tool for solving problems in real algebraic geometry and beyond. In recent years a new approach has been developed, where regular chains technology is used to first build a Decomposition in complex space. We consider the latest variant of this which builds the complex Decomposition incrementally by polynomial and produces CADs on whose cells a sequence of formulae are truth-invariant. Like all CAD algorithms the user must provide a variable ordering which can have a profound impact on the tractability of a problem. We evaluate existing heuristics to help with the choice for this algorithm, suggest improvements and then derive a new heuristic more closely aligned with the mechanics of the new algorithm.
-
problem formulation for truth table invariant cylindrical algebraic Decomposition by incremental Triangular Decomposition
arXiv: Symbolic Computation, 2014Co-Authors: Matthew England, Changbo Chen, Marc Moreno Maza, Russell Bradford, James H Davenport, David WilsonAbstract:Cylindrical algebraic Decompositions (CADs) are a key tool for solving problems in real algebraic geometry and beyond. We recently presented a new CAD algorithm combining two advances: truth-table invariance, making the CAD invariant with respect to the truth of logical formulae rather than the signs of polynomials; and CAD construction by regular chains technology, where first a complex Decomposition is constructed by refining a tree incrementally by constraint. We here consider how best to formulate problems for input to this algorithm. We focus on a choice (not relevant for other CAD algorithms) about the order in which constraints are presented. We develop new heuristics to help make this choice and thus allow the best use of the algorithm in practice. We also consider other choices of problem formulation for CAD, as discussed in CICM 2013, revisiting these in the context of the new algorithm.
-
computing with semi algebraic sets represented by Triangular Decomposition
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Changbo Chen, Marc Moreno Maza, James H Davenport, Bican Xia, Rong XiaoAbstract: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 exhibit new results on the theory of border polynomials of parametric semi-algebraic systems: in particular a geometric characterization of its "true boundary" (Definition 2). In order to optimize these algorithms, we also propose a technique, that we call relaxation, which can simplify the Decomposition process and reduce the number of redundant components in the output. Moreover, we present procedures for basic set-theoretical operations on semi-algebraic sets represented by Triangular Decomposition. Experimentation confirms the effectiveness of our techniques.
-
Triangular Decomposition of semi algebraic systems
International Symposium on Symbolic and Algebraic Computation, 2010Co-Authors: Changbo Chen, Marc Moreno Maza, James H Davenport, Bican Xia, John P May, Rong XiaoAbstract: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.We show that any such system can be decomposed into finitely many regular semi-algebraic systems. We propose two specifications of such a Decomposition and present corresponding algorithms. Under some assumptions, one type of Decomposition can be computed in singly exponential time w.r.t. the number of variables. We implement our algorithms and the experimental results illustrate their effectiveness.
-
Triangular Decomposition of semi algebraic systems
arXiv: Symbolic Computation, 2010Co-Authors: Changbo Chen, Marc Moreno Maza, James H Davenport, Bican Xia, John P May, Rong XiaoAbstract: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. We show that any such system can be decomposed into finitely many {\em regular semi-algebraic systems}. We propose two specifications of such a Decomposition and present corresponding algorithms. Under some assumptions, one type of Decomposition can be computed in singly exponential time w.r.t.\ the number of variables. We implement our algorithms and the experimental results illustrate their effectiveness.
