# Open Weak CAD and Its Applications

@article{Dai2017OpenWC, title={Open Weak CAD and Its Applications}, author={Liyun Dai and Jingjun Han and Hoon Hong and Bican Xia}, journal={ArXiv}, year={2017}, volume={abs/1507.03834} }

Abstract The concept of open weak CAD is introduced. Every open CAD is an open weak CAD. On the contrary, an open weak CAD is not necessarily an open CAD. An algorithm for computing projection polynomials of open weak CADs is proposed. The key idea is to compute the intersection of projection factor sets produced by different projection orders. The resulting open weak CAD often has smaller number of sample points than open CADs. The algorithm can be used for computing sample points for all open… Expand

#### 4 Citations

Global Optimization of Polynomials over Real Algebraic Sets

- Computer Science, Mathematics
- J. Syst. Sci. Complex.
- 2019

The authors propose a method to compute the global infimum f* of f over an arbitrary given real algebraic set V = {x ∈ Rn | g1(x) = 0,..., gs(x] = 0}, where V is not required to be compact or smooth. Expand

Choosing the Variable Ordering for Cylindrical Algebraic Decomposition via Exploiting Chordal Structure

- Computer Science
- ISSAC
- 2021

It is indicated that typical CAD algorithms, if executed with respect to a special kind of variable orderings (called "the perfect elimination orderings''), naturally preserve chordality, which is well compatible with an important (variable) sparsity pattern called "the correlative sparsity''. Expand

Solving Satisfiability of Polynomial Formulas By Sample-Cell Projection

- Mathematics, Computer Science
- ArXiv
- 2020

A new algorithm for deciding the satisfiability of polynomial formulas over the reals is proposed, custom-made for Conflict-Driven Clause Learning (CDCL)-style search and can efficiently guide CDCL-style search away from conflicting states. Expand

Multivariate discriminant and iterated resultant

- Mathematics
- 2015

In this paper, we study the relationship between iterated resultant and multivariate discriminant. We show that, for generic form f(xn) with even degree d, if the polynomial is squarefreed after each… Expand

#### References

SHOWING 1-10 OF 36 REFERENCES

Proving inequalities and solving global optimization problems via simplified CAD projection

- Mathematics, Computer Science
- J. Symb. Comput.
- 2016

A simplified Brown-McCallum's CAD projection operator, Nproj, is proposed, of which the projection scale is always no larger than that of Brown- McCallum's, and the lifting phase is also simplified. Expand

Constructing fewer open cells by GCD computation in CAD projection

- Mathematics, Computer Science
- ISSAC
- 2014

It is proved that the new projection operator based on cylindrical algebraic decomposition can be used for testing semi-definiteness of polynomials and still guarantees obtaining at least one sample point from every connected component of the highest dimension. Expand

Testing Sign Conditions on a Multivariate Polynomial and Applications

- Mathematics, Computer Science
- Math. Comput. Sci.
- 2007

The paper shows how to use the computation of generalized critical values in order to obtain an efficient algorithm deciding the emptiness of a semi-algebraic set defined by a single inequality or a single inequation. Expand

An Improved Projection Operation for Cylindrical Algebraic Decomposition of Three-Dimensional Space

- Computer Science, Mathematics
- J. Symb. Comput.
- 1988

It is shown, using a theorem from complex analytic geometry, that the original projection set for trivariate polynomials that Collins used can be substantially reduced in size, without affecting its essential properties. Expand

Polar varieties and computation of one point in each connected component of a smooth real algebraic set

- Mathematics, Computer Science
- ISSAC '03
- 2003

An algorithm is deduced that extends that of Bank, Giusti, Heintz and Mbakop to non-compact situations and its arithmetic complexity is polynomial in the complexity of evaluation of the input system, an intrinsic algebraic quantity and a combinatorial quantity. Expand

Partial Cylindrical Algebraic Decomposition for Quantifier Elimination

- Computer Science, Mathematics
- J. Symb. Comput.
- 1991

This paper presents a method which intermingles CAD construction with truth evaluation so that parts of the CAD are constructed only as needed to further truth evaluation and aborts CAD construction as soon as no more truth evaluation is needed. Expand

On the combinatorial and algebraic complexity of quantifier elimination

- Mathematics, Computer Science
- JACM
- 1996

This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this data, and new and improved algorithms for deciding a sentence in the first order theory over real closed fields, are obtained. Expand

Solving Systems of Strict Polynomial Inequalities

- Computer Science, Mathematics
- J. Symb. Comput.
- 2000

An algorithm for finding an explicit description of solution sets of systems of strict polynomial inequalities, correct up to lower dimensional algebraic sets is presented, based on the cylindrical algebraic decomposition algorithm. Expand

Improved Projection for Cylindrical Algebraic Decomposition

- Computer Science, Mathematics
- J. Symb. Comput.
- 2001

A simple theorem is presented showing that the mathematics in McCallum?s paper actually point to a better projection operator than he proposes, which has the potential to not simply speed up CAD computation for problems that are currently solvable in practice, but actually increase the scope of problems that can realistically be attacked via CADs. Expand

Variant quantifier elimination

- Computer Science, Mathematics
- J. Symb. Comput.
- 2012

The main idea underlying the algorithm is to substitute the repeated projection step of CAD by a single projection without carrying out a parametric existential decision over the reals, and it is found that the algorithm can tackle important and challenging problems, such as numerical stability analysis of the widely-used MacCormack's scheme. Expand