Complex Algorithms in OSCAR
On this page we will list some of the more involved algorithmic problems of OSCAR which you may encounter in the background. For larger examples these may not terminate, due to lack of memory or time. We will not go into the details of the respective complexity, as there is sufficient literature.
Often there are several algorithms in OSCAR solving a particular problem, and trying different alternatives may be worthwhile, as some algorithms may not terminate, while others finish in an instant.
Groebner and Standard Bases
A standard basis of an ideal is a generating with special properties. A standard basis is necessary for many (mathematical) low level operations from commutative algebra.
- Ideal membership
- Radical of an ideal
- Kernel of a ring homomorphism
- Krull dimension of an ideal
Double Description
A polyhedron may be described as the convex hull of a finite set of points or as the intersection of finitely many halfspaces. We omit the more complex cases of unbounded or non-fulldimensional polyhedra here. Computing one description from the other is done via double description algorithms. Many simple algorithms on polyhedra need a double description.
- Equality of polyhedra
- Face lattice
- Lattice points
- Hilbert basis
Omitted input sanity checks
Some input sanity checks are omitted on purpose, since they would be too expensive to verify performance wise. We will continue to add to the following list.
- Checking that the input for
subdivision_of_pointsactually defines a proper polyhedral complex covering the convex hull of the given points.