2015/01/31 by Matthew England, Russell Bradford, James H. Davenport · 1 citation
Computer Science · #cs.SC #msc:68W30 #msc:03C10 #acm:68W30 #acm:03C10
paper · pdf · doi:10.1145/2755996.2756678
published as Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation (ISSAC '15), pp. 165--172. ACM, 2015
arxiv created 2015/05/07 · arxiv updated 2015/07/20
When building a cylindrical algebraic decomposition (CAD) savings can be made in the presence of an equational constraint (EC): an equation logically implied by a formula. The present paper is concerned with how to use multiple ECs, propagating those in the input throughout the projection set. We improve on the approach of McCallum in ISSAC 2001 by using the reduced projection theory to make savings in the lifting phase (both to the polynomials we lift with and the cells lifted over). We demonstrate the benefits with worked examples and a complexity analysis.