TY - JOUR

T1 - An improved projection operation for cylindrical algebraic decomposition of three-dimensional space

AU - McCallum, Scott

PY - 1988/1/1

Y1 - 1988/1/1

N2 - 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 polynomials in the projection comprise a “shadow” of the critical zeros of A. The cad algorithm proceeds by forming successive projections of the input set A, each projection resulting in the elimination of one variable. This paper is concerned with a refinement to the cad algorithm, and to its projection operation in particular. 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. Observations suggest that the reduction in the projection set size leads to a substantial decrease in the computing time of the cad algorithm.

AB - 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 polynomials in the projection comprise a “shadow” of the critical zeros of A. The cad algorithm proceeds by forming successive projections of the input set A, each projection resulting in the elimination of one variable. This paper is concerned with a refinement to the cad algorithm, and to its projection operation in particular. 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. Observations suggest that the reduction in the projection set size leads to a substantial decrease in the computing time of the cad algorithm.

UR - http://www.scopus.com/inward/record.url?scp=85025515304&partnerID=8YFLogxK

U2 - 10.1016/S0747-7171(88)80010-5

DO - 10.1016/S0747-7171(88)80010-5

M3 - Article

AN - SCOPUS:85025515304

SN - 0747-7171

VL - 5

SP - 141

EP - 161

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

IS - 1-2

ER -