Research

Using the distribution of cells by dimension in a cylindrical algebraic decomposition


Reference:

Wilson, D., England, M., Bradford, R.J. and Davenport, J.H., 2014. Using the distribution of cells by dimension in a cylindrical algebraic decomposition. IEEE, pp. 53-60.

Related documents:

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

    Official URL:

    http://dx.doi.org/10.1109/SYNASC.2014.15

    Related URLs:

    Abstract

    We investigate the distribution of cells by dimension in cylindrical algebraic decompositions (CADs). We find that they follow a standard distribution which seems largely independent of the underlying problem or CAD algorithm used. Rather, the distribution is inherent to the cylindrical structure and determined mostly by the number of variables. This insight is then combined with an algorithm that produces only full-dimensional cells to give an accurate method of predicting the number of cells in a complete CAD. Since constructing only full-dimensional cells is relatively inexpensive (involving no costly algebraic number calculations) this leads to heuristics for helping with various questions of problem formulation for CAD, such as choosing an optimal variable ordering. Our experiments demonstrate that this approach can be highly effective.

    Details

    Item Type Conference or Workshop Items (UNSPECIFIED)
    CreatorsWilson, D., England, M., Bradford, R.J. and Davenport, J.H.
    DOI10.1109/SYNASC.2014.15
    Related URLs
    URLURL Type
    http://synasc.ro/2014/Organisation
    Uncontrolled Keywordscylindrical algebraic decomposition,problem formulation,heuristic
    DepartmentsFaculty of Science > Computer Science
    Publisher StatementSYNASC2014.pdf: 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works
    StatusPublished
    ID Code40758

    Export

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...