Research

Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition


Reference:

England, M., Bradford, R. J., Chen, C., Davenport, J. H., Moreno Maza, M. and Wilson, D., 2014. Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. In: Watt, S. M., Davenport, J. H., Sexton, A. P., Sojka, P. and Urban, J., eds. Intelligent Computer Mathematics. Springer, pp. 45-60. (Lecture Notes in Artificial Intelligence; 8543)

Related documents:

[img]
Preview
PDF (EBCDMW14) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (841kB) | Preview

    Official URL:

    http://dx.doi.org/10.1007/978-3-319-08434-3_5

    Abstract

    Cylindrical algebraic decompositions (CADs) are a key tool for solving problems in real algebraic geometry and beyond. We recently presented a new CAD algorithm combining two advances: truth-table invariance, making the CAD invariant with respect to the truth of logical formulae rather than the signs of polynomials; and CAD construction by regular chains technology, where first a complex decomposition is constructed by refining a tree incrementally by constraint. We here consider how best to formulate problems for input to this algorithm. We focus on a choice (not relevant for other CAD algorithms) about the order in which constraints are presented. We develop new heuristics to help make this choice and thus allow the best use of the algorithm in practice. We also consider other choices of problem formulation for CAD, as discussed in CICM 2013, revisiting these in the context of the new algorithm.

    Details

    Item Type Book Sections
    CreatorsEngland, M., Bradford, R. J., Chen, C., Davenport, J. H., Moreno Maza, M. and Wilson, D.
    EditorsWatt, S. M., Davenport, J. H., Sexton, A. P., Sojka, P. and Urban, J.
    DOI10.1007/978-3-319-08434-3_5
    Uncontrolled Keywordscylindrical algebraic decomposition,truth table invariance,regular chains,triangular decomposition,problem formulation
    DepartmentsFaculty of Science > Computer Science
    Publisher StatementEBCDMW14.pdf: The final publication will be available from http://link.springer.com/
    StatusPublished
    ID Code39231

    Export

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...