Speeding up cylindrical algebraic decomposition by Gröebner Bases

Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 8 Citations

Abstract

Gröebner Bases and Cylindrical Algebraic Decomposition are generally thought of as two, rather different, methods of looking at systems of equations and, in the case of Cylindrical Algebraic Decomposition, inequalities. However, even for a mixed system of equalities and inequalities, it is possible to apply Gröebner basesto the (conjoined) equalities before invoking CAD. We see that this is, quite often but not always, a beneficial preconditioning of the CAD problem. It is also possible to precondition the (conjoined) inequalities with respect to the equalities, and this can also be useful in many cases.
LanguageEnglish
Title of host publicationIntelligent Computer Mathematics
EditorsJohan Jeuring, John A Campbell, Jacques Carette, Gabriel Dos Reis, Petr Sojka, Makarius Wenzel, Volker Sorge
Place of PublicationHeidelberg
Pages280-294
Number of pages15
Volume7362
ISBN (Electronic)9783642313745
DOIs
StatusPublished - 2012
Event11th International Conference, AISC 2012, 19th Symposium, Calculemus 2012, 5th International Workshop, DML 2012, 11th International Conference, MKM 2012, Systems and Projects, held as part of CICM 2012 - Bremen, Germany
Duration: 8 Jul 201213 Jul 2012

Publication series

NameLecture Notes in Computer Science
Volume7362
ISSN (Print)0302-9743

Conference

Conference11th International Conference, AISC 2012, 19th Symposium, Calculemus 2012, 5th International Workshop, DML 2012, 11th International Conference, MKM 2012, Systems and Projects, held as part of CICM 2012
Abbreviated titleCICM 2012
CountryGermany
CityBremen
Period8/07/1213/07/12

Fingerprint

Equality
Decompose
Precondition
Preconditioning
System of equations

Keywords

  • Groebner basis
  • Cylindrical Algebraic Decomposition

Cite this

Wilson, D. J., Bradford, R. J., & Davenport, J. H. (2012). Speeding up cylindrical algebraic decomposition by Gröebner Bases. In J. Jeuring, J. A. Campbell, J. Carette, G. Dos Reis, P. Sojka, M. Wenzel, & V. Sorge (Eds.), Intelligent Computer Mathematics (Vol. 7362, pp. 280-294). (Lecture Notes in Computer Science; Vol. 7362). Heidelberg. https://doi.org/10.1007/978-3-642-31374-5_19

Speeding up cylindrical algebraic decomposition by Gröebner Bases. / Wilson, David J; Bradford, Russell J; Davenport, James H.

Intelligent Computer Mathematics. ed. / Johan Jeuring; John A Campbell; Jacques Carette; Gabriel Dos Reis; Petr Sojka; Makarius Wenzel; Volker Sorge. Vol. 7362 Heidelberg, 2012. p. 280-294 (Lecture Notes in Computer Science; Vol. 7362).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Wilson, DJ, Bradford, RJ & Davenport, JH 2012, Speeding up cylindrical algebraic decomposition by Gröebner Bases. in J Jeuring, JA Campbell, J Carette, G Dos Reis, P Sojka, M Wenzel & V Sorge (eds), Intelligent Computer Mathematics. vol. 7362, Lecture Notes in Computer Science, vol. 7362, Heidelberg, pp. 280-294, 11th International Conference, AISC 2012, 19th Symposium, Calculemus 2012, 5th International Workshop, DML 2012, 11th International Conference, MKM 2012, Systems and Projects, held as part of CICM 2012, Bremen, Germany, 8/07/12. https://doi.org/10.1007/978-3-642-31374-5_19
Wilson DJ, Bradford RJ, Davenport JH. Speeding up cylindrical algebraic decomposition by Gröebner Bases. In Jeuring J, Campbell JA, Carette J, Dos Reis G, Sojka P, Wenzel M, Sorge V, editors, Intelligent Computer Mathematics. Vol. 7362. Heidelberg. 2012. p. 280-294. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-31374-5_19
Wilson, David J ; Bradford, Russell J ; Davenport, James H. / Speeding up cylindrical algebraic decomposition by Gröebner Bases. Intelligent Computer Mathematics. editor / Johan Jeuring ; John A Campbell ; Jacques Carette ; Gabriel Dos Reis ; Petr Sojka ; Makarius Wenzel ; Volker Sorge. Vol. 7362 Heidelberg, 2012. pp. 280-294 (Lecture Notes in Computer Science).
@inproceedings{122fd0976ff445eb82fe9e139cda78c3,
title = "Speeding up cylindrical algebraic decomposition by Gr{\"o}ebner Bases",
abstract = "Gr{\"o}ebner Bases and Cylindrical Algebraic Decomposition are generally thought of as two, rather different, methods of looking at systems of equations and, in the case of Cylindrical Algebraic Decomposition, inequalities. However, even for a mixed system of equalities and inequalities, it is possible to apply Gr{\"o}ebner basesto the (conjoined) equalities before invoking CAD. We see that this is, quite often but not always, a beneficial preconditioning of the CAD problem. It is also possible to precondition the (conjoined) inequalities with respect to the equalities, and this can also be useful in many cases.",
keywords = "Groebner basis, Cylindrical Algebraic Decomposition",
author = "Wilson, {David J} and Bradford, {Russell J} and Davenport, {James H}",
year = "2012",
doi = "10.1007/978-3-642-31374-5_19",
language = "English",
isbn = "9783642313738",
volume = "7362",
series = "Lecture Notes in Computer Science",
pages = "280--294",
editor = "Johan Jeuring and Campbell, {John A } and Jacques Carette and {Dos Reis}, Gabriel and Sojka, {Petr } and Makarius Wenzel and Volker Sorge",
booktitle = "Intelligent Computer Mathematics",

}

TY - GEN

T1 - Speeding up cylindrical algebraic decomposition by Gröebner Bases

AU - Wilson, David J

AU - Bradford, Russell J

AU - Davenport, James H

PY - 2012

Y1 - 2012

N2 - Gröebner Bases and Cylindrical Algebraic Decomposition are generally thought of as two, rather different, methods of looking at systems of equations and, in the case of Cylindrical Algebraic Decomposition, inequalities. However, even for a mixed system of equalities and inequalities, it is possible to apply Gröebner basesto the (conjoined) equalities before invoking CAD. We see that this is, quite often but not always, a beneficial preconditioning of the CAD problem. It is also possible to precondition the (conjoined) inequalities with respect to the equalities, and this can also be useful in many cases.

AB - Gröebner Bases and Cylindrical Algebraic Decomposition are generally thought of as two, rather different, methods of looking at systems of equations and, in the case of Cylindrical Algebraic Decomposition, inequalities. However, even for a mixed system of equalities and inequalities, it is possible to apply Gröebner basesto the (conjoined) equalities before invoking CAD. We see that this is, quite often but not always, a beneficial preconditioning of the CAD problem. It is also possible to precondition the (conjoined) inequalities with respect to the equalities, and this can also be useful in many cases.

KW - Groebner basis

KW - Cylindrical Algebraic Decomposition

UR - http://www.scopus.com/inward/record.url?scp=84864958030&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1007/978-3-642-31374-5_19

U2 - 10.1007/978-3-642-31374-5_19

DO - 10.1007/978-3-642-31374-5_19

M3 - Conference contribution

SN - 9783642313738

VL - 7362

T3 - Lecture Notes in Computer Science

SP - 280

EP - 294

BT - Intelligent Computer Mathematics

A2 - Jeuring, Johan

A2 - Campbell, John A

A2 - Carette, Jacques

A2 - Dos Reis, Gabriel

A2 - Sojka, Petr

A2 - Wenzel, Makarius

A2 - Sorge, Volker

CY - Heidelberg

ER -