Cylindrical Algebraic Decomposition
Lead Research Organisation:
University of Bath
Department Name: Computer Science
Abstract
Cylindrical Algebraic Decomposition is a general-purpose computation technique underpinning many questions in
real algebraic geometry and its applications,
e.g. robot motion planning. There are various algorithms for producing such decompositions. However, all known
algorithms produce objects which,
while Cylindrical Algebraic Decompositions, also satisfy certain other properties. These are generally not wellarticulated,
and we would like to make
this precise. Many issues, such as adjacency, are currently not solved for Cylindrical Algebraic Decompositions,
because of the generality of the definition.
We suspect that having a more precise description of the sort of decompositions produced in practice would make it
easier to produce algorithms that are very
useful in applications. The Bath group have made many developments in CAD based on McCallum's projection as a
tool for constructing such CADs. But McCallum's
projection can fail. Recently McCallum and colleagues have proved that a different projection (Lazard's), and
associated different lifting algorithms, never fails.
The starting phase of the project revolves around gathering background information regarding CAD, specifically
around McCallum's and Lazard's projection. During this phase I will
be attending the computer algebra course offered to third years in the computer science department as this covers
the basics of CAD. Apart from CAD I will be broadening my
knowledge in Algebraic Geometry, as required by the scope of the project, and will be attending the regular geometry
seminars that are held at the University of Bath.
As a starting point I will be focussing my attention towards understanding the piano mover's problem, which asks
whether, given an object and its configuration space,
it is possible to move the object from point A to point B. If this is possible what is the most efficient way to do so?
real algebraic geometry and its applications,
e.g. robot motion planning. There are various algorithms for producing such decompositions. However, all known
algorithms produce objects which,
while Cylindrical Algebraic Decompositions, also satisfy certain other properties. These are generally not wellarticulated,
and we would like to make
this precise. Many issues, such as adjacency, are currently not solved for Cylindrical Algebraic Decompositions,
because of the generality of the definition.
We suspect that having a more precise description of the sort of decompositions produced in practice would make it
easier to produce algorithms that are very
useful in applications. The Bath group have made many developments in CAD based on McCallum's projection as a
tool for constructing such CADs. But McCallum's
projection can fail. Recently McCallum and colleagues have proved that a different projection (Lazard's), and
associated different lifting algorithms, never fails.
The starting phase of the project revolves around gathering background information regarding CAD, specifically
around McCallum's and Lazard's projection. During this phase I will
be attending the computer algebra course offered to third years in the computer science department as this covers
the basics of CAD. Apart from CAD I will be broadening my
knowledge in Algebraic Geometry, as required by the scope of the project, and will be attending the regular geometry
seminars that are held at the University of Bath.
As a starting point I will be focussing my attention towards understanding the piano mover's problem, which asks
whether, given an object and its configuration space,
it is possible to move the object from point A to point B. If this is possible what is the most efficient way to do so?
Organisations
People |
ORCID iD |
| Akshar NAIR (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509589/1 | 01/10/2016 | 30/09/2021 | |||
| 1940105 | Studentship | EP/N509589/1 | 01/10/2017 | 31/03/2021 | Akshar NAIR |
| Description | Two (out of many) CAD construction methods for \RR^n are due to McCallum and to Lazard, producing order-invariant and lex-least invariant CADs respectively. Both work by repeated projection and lifting. McCallum later modified his method so as to exploit an equational constraint and thus efficiently construct a CAD of a hypersurface. We have similarly modified Lazard's method, but because our output is sign-invariant and Lazard requires a lex-least invariant input we can only use it at the first projection stage, not recursively. We then proceed by using Lazard's method without modification. Nonetheless, reducing the output in the first step significantly reduces the complexity throughout. McCallum's method fails if any of the polynomials are nullified (i.e. vanish on a fibre of the projection) but Lazard's method still works in this case. Our current work aims to carry this over to the modified version, by using a second CAD construction on the locus, called a curtain, where the equational constraint is nullified. |
| Exploitation Route | In general a faster CAD algorithm is useful for describing the solution space for quantified problems. Such problems arise, for instance, in motion planning, robotics and machine learning. We are in the process of improving our algorithm in order to provide a balance between accuracy and complexity. All existing methods have problems with curtains, and the current methods that deal with curtains have quite bad complexity. We are confident with our recent ideas that we shall be able to provide better solutions to this problem. |
| Sectors | Construction,Creative Economy,Financial Services, and Management Consultancy |