๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Improved Projection for Cylindrical Algebraic Decomposition

โœ Scribed by Christopher W. Brown

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
358 KB
Volume
32
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 point to a better projection operator than he proposes-a reduced McCallum projection.

The reduced projection 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. Additionally, the same methods are used to show that McCallum's projection can be reduced still further when CAD is applied to certain types of commonly occurring quantifier elimination problems.

๐Ÿ“œ SIMILAR VOLUMES

Interval Arithmetic in Cylindrical Algeb
Interval Arithmetic in Cylindrical Algebraic Decomposition
โœ George E. Collins; Jeremy R. Johnson; Werner Krandick ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 237 KB

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 polynomial real root isolation can be greatly reduc

Local Box Adjacency Algorithms for Cylin
Local Box Adjacency Algorithms for Cylindrical Algebraic Decompositions
โœ Scott M c Callum; George E. Collins ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 372 KB

We describe new algorithms for determining the adjacencies between zero-dimensional cells and those one-dimensional cells that are sections (not sectors) in cylindrical algebraic decompositions (cad). Such adjacencies constitute a basis for determining all other cell adjacencies. Our new algorithms

Exponent Reduction for Projective Schur
Exponent Reduction for Projective Schur Algebras
โœ Eli Aljadeff; Jack Sonn ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 88 KB

In this paper it is proved that the ''exponent reduction property'' holds for all projective Schur algebras. This was proved in an earlier paper of the authors for a special class, the ''radical abelian algebras.'' The precise statement is as follows: let ลฝ . A be a projective Schur algebra over a f