Algorithmic Triangulation of Monotone families
Lead Research Organisation:
University of Bath
Department Name: Computer Science
Abstract
The proposed research is in the field of computer algebra, one of the main areas of research within the Mathematical foundations group in the Department of Computer Science.
It is centred around the idea that semi algebraic sets become easier to work with once they have been broken down into sufficiently simple pieces.
One such method is Cylindrical Algebraic Decomposition (CAD), which breaks a semi algebraic set into cylindrical cells. This method is well studied, and it is possible to construct a CAD of any semi algebraic set. However sometimes CADs can arise which have undesirable properties. For example, not all cells in the CAD have the property of being topologically regular cells. Basu, Gabrielov and Vorobjov proved that for a semi algebraic set $K \subset R^n$ with $\dim(K) \le 2$ it is always possible to construct a CAD with all topologically regular cells. The first objective of this project is to design and implement an efficient algorithm to construct these regular CADs. The ability to efficiently construct regular CADs is an important problem in it's own right, but it is also a dependency for the second aim of my research.
The University of Bath is also involved in an EPSRC project entitled "Pushing Back the Doubly-Exponential Wall of Cylindrical Algebraic Decomposition". The first part of my research, designing an efficient algorithm for creating regular CADs fits in nicely with this project.
Another method of breaking up semi algebraic sets is triangulation. As with CAD, there are classical results that state that any semi algebraic set can be triangulated. However, in a number of topological problems, approximations of sets by monotone families are useful. When blow-ups occur, the behaviour of these families can be complex, and it can help to try to classify them into a finite number of standard types. Basu, Gabrielov and Vorobjov also proved that a triangulation of a 2-dimensional monotone family into a simplicial complex can be constructed such that each of the 2-simplices will have one of five types. The next objective of my research is to take this result and use it to design an algorithm for constructing triangulations which satisfy the above condition. The construction of a regular CAD will be an intermediate step in this process.
If time allows, there is also a possibility of extending the above algorithms to sets with dimension <= 3, and possibly even generalising to n-dimensional sets.
A tangible objective of this research is to consider the possibility of including these new algorithms in computer algebra systems, such as Maple. This will enable them to be used by other researchers in wider applications. For example, the CAD algorithm can be used to perform quantifier elimination. This has a broad array of applications, ranging from verification of safety-critical software systems to emerging applications in biology and economics.
It is centred around the idea that semi algebraic sets become easier to work with once they have been broken down into sufficiently simple pieces.
One such method is Cylindrical Algebraic Decomposition (CAD), which breaks a semi algebraic set into cylindrical cells. This method is well studied, and it is possible to construct a CAD of any semi algebraic set. However sometimes CADs can arise which have undesirable properties. For example, not all cells in the CAD have the property of being topologically regular cells. Basu, Gabrielov and Vorobjov proved that for a semi algebraic set $K \subset R^n$ with $\dim(K) \le 2$ it is always possible to construct a CAD with all topologically regular cells. The first objective of this project is to design and implement an efficient algorithm to construct these regular CADs. The ability to efficiently construct regular CADs is an important problem in it's own right, but it is also a dependency for the second aim of my research.
The University of Bath is also involved in an EPSRC project entitled "Pushing Back the Doubly-Exponential Wall of Cylindrical Algebraic Decomposition". The first part of my research, designing an efficient algorithm for creating regular CADs fits in nicely with this project.
Another method of breaking up semi algebraic sets is triangulation. As with CAD, there are classical results that state that any semi algebraic set can be triangulated. However, in a number of topological problems, approximations of sets by monotone families are useful. When blow-ups occur, the behaviour of these families can be complex, and it can help to try to classify them into a finite number of standard types. Basu, Gabrielov and Vorobjov also proved that a triangulation of a 2-dimensional monotone family into a simplicial complex can be constructed such that each of the 2-simplices will have one of five types. The next objective of my research is to take this result and use it to design an algorithm for constructing triangulations which satisfy the above condition. The construction of a regular CAD will be an intermediate step in this process.
If time allows, there is also a possibility of extending the above algorithms to sets with dimension <= 3, and possibly even generalising to n-dimensional sets.
A tangible objective of this research is to consider the possibility of including these new algorithms in computer algebra systems, such as Maple. This will enable them to be used by other researchers in wider applications. For example, the CAD algorithm can be used to perform quantifier elimination. This has a broad array of applications, ranging from verification of safety-critical software systems to emerging applications in biology and economics.
Organisations
People |
ORCID iD |
| Nicolai Vorobjov (Primary Supervisor) | |
| Hollie BAKER (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/T518013/1 | 01/10/2020 | 30/09/2025 | |||
| 2427789 | Studentship | EP/T518013/1 | 01/10/2020 | 31/03/2024 | Hollie BAKER |