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

Scott McCallum*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

54 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)141-161
Number of pages21
JournalJournal of Symbolic Computation
Volume5
Issue number1-2
DOIs
Publication statusPublished - 1 Jan 1988
Externally publishedYes

Fingerprint Dive into the research topics of 'An improved projection operation for cylindrical algebraic decomposition of three-dimensional space'. Together they form a unique fingerprint.

Cite this