H. Hong
ABSTRACT
The Cylindrical Algebraic Decomposition (CAD) method of Collins [5] decomposes r-dimensional Euclidean space into regions over which a given set of polynomials have constant signs. An important component of the CAD method is the projection operation: given a set A of r-variate polynomials, the projection operation produces a set P of (r - 1)-variate polynomials such that a CAD of r-dimensional space for A can be constructed from a CAD of (r-1)-dimensional space for P. In this paper, we present an improvement to the projection operation. By generalizing a lemma on which the proof of the original projection operation is based, we are able to find another projection operation which produces a smaller number of polynomials. Let m be the number of polynomials contained in A, and let n be a bound for the degree of each polynomial in A in the projection variable. The number of polynomials produced by the original projection operation is dominated by m2n3 whereas the number of polynomials produced by our projection operation is dominated by m2n2.
- 1.D.S. Arnon, G. E. Collins, and S. McCMlum. Cylindrical algebraic decomposition I: The basic algorithm. Technical Report CSD-427, Computer Science Dept, Purdue U aiversity, 1982.Google Scholar
- 2.D.S. Arnon, G. E. Collins, and S. McCailum. Cylindrical algebraic decomposition I: The basic algorithm. SIAM J. Comp,, 13:865-877, 1984. Google ScholarDigital Library
- 3.D. S. Arnon and M. Mignotte. On mechanical quantifier elimination for elementary algebra and geometry. J. $1trnboli~ Comp., 5(1,2):237-260, 1988. Google ScholarDigital Library
- 4.G. E. Collins and R. Loos. The ALDES-SAC2 computer algebra system. Technical report, 1980.Google Scholar
- 5.George E. Collins. Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition. In Lecture Note8 In Computer Science, pages 134-183. Springer-Verlag, Berlin, 1975. Vol. 35. Google ScholarDigital Library
- 6.George E. Collins and H oon H ong. Partial cad construction in quantifier elimination. Technical Report OSU- CISRC-10/89 TR45, Computer Science Dept, The Ohio State University, 1989. Submitted to Journal of Symbolic Computation.Google Scholar
- 7.James H. Davenport and Joos Heintz. Real quantifier elimination is doubly exponential. J. Symbolic Comp., 5(1,2), 19ss. Google ScholarDigital Library
- 8.Hoon Hong. An improvement of the projection operator in cylindrical algebraic decomposition. Technical Report OSU-CISRC-12/89 TR55, Computer Science Dept, The Ohio State University, 1989.Google Scholar
- 9.$. McC~llum. An Imp,o,~d P,ojection Operator for Cylindrical Algebraic Decompoaition. PhD thesis, University of Wisconsin-Madison, 1984. Google ScholarDigital Library
Index Terms
- An improvement of the projection operator in cylindrical algebraic decomposition
Recommendations
An improved projection operation for cylindrical algebraic decomposition of three-dimensional space
A key component of the cylindrical algebraic decomposition (cad) algorithm of Collins (1975) is the projection operation: the projection of a set A of r-variate polynomials is defined to be a certain set or (r-1)-variate polynomials. Tile zeros of the ...
Improved Projection for Cylindrical Algebraic Decomposition
McCallum s projection operator for cylindrical algebraic decomposition (CAD) represented a huge step forward for the practical utility of the CAD algorithm. This paper presents a simple theorem showing that the mathematics in McCallum s paper actually ...
Interval Arithmetic in Cylindrical Algebraic Decomposition
Cylindrical algebraic decomposition requires many very time consuming operations, including resultant computation, polynomial factorization, algebraic polynomial gcd computation and polynomial real root isolation. We show how the time for algebraic ...
Comments