Speeding up cylindrical algebraic decomposition by Gröebner Bases

David J Wilson; Russell J Bradford; James H Davenport

doi:10.1007/978-3-642-31374-5_19

Speeding up cylindrical algebraic decomposition by Gröebner Bases

David J Wilson, Russell J Bradford, James H Davenport

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

13 Citations (SciVal)

163 Downloads (Pure)

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.

Original language	English
Title of host publication	Intelligent Computer Mathematics
Editors	Johan Jeuring, John A Campbell, Jacques Carette, Gabriel Dos Reis, Petr Sojka, Makarius Wenzel, Volker Sorge
Place of Publication	Heidelberg
Pages	280-294
Number of pages	15
Volume	7362
ISBN (Electronic)	9783642313745
DOIs	https://doi.org/10.1007/978-3-642-31374-5_19
Publication status	Published - 2012
Event	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 Duration: 8 Jul 2012 → 13 Jul 2012

Publication series

Name	Lecture Notes in Computer Science
Volume	7362
ISSN (Print)	0302-9743

Conference

Conference	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
Abbreviated title	CICM 2012
Country/Territory	Germany
City	Bremen
Period	8/07/12 → 13/07/12

Keywords

Groebner basis
Cylindrical Algebraic Decomposition

Access to Document

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

CICM2012-v9-EasyChair.pdf
The original publication is available at www.springerlink.com
Accepted author manuscript, 413 KB

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).. 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 or section in a book/report/conference proceeding › Chapter in a published conference proceeding

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

@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",

note = "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, CICM 2012 ; Conference date: 08-07-2012 Through 13-07-2012",

}

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 - Chapter in a published conference proceeding

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

T2 - 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

Y2 - 8 July 2012 through 13 July 2012

ER -

Speeding up cylindrical algebraic decomposition by Gröebner Bases

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Real Geometry and Connectedness via Triangular Description

Cite this