Basis enumeration of hyperplane arrangements up to symmetries
Loading...
Files
Date
2012
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of New Brunswick
Abstract
This thesis details a method of enumerating bases of hyperplane arrangements
up to symmetries. I consider here automorphisms, geometric symmetries
which leave the set of all points contained in the arrangement setwise
invariant. The algorithm for basis enumeration described in this thesis is
a backtracking search over the adjacency graph implied on the bases by
minimum-ratio simplex pivots, pruning at bases symmetric to those already
seen. This work extends Bremner, Sikiric, and Schiirmann's method for basis
enumeration of polyhedra up to symmetries, including a new pivoting
rule for finding adjacent bases in arrangements, a method of computing automorphisms
of arrangements which extends the method of Bremner et al.
for computing automorphisms of polyhedra, and some associated changes to
optimizations used in the previous work. I include results of tests on ACEnet
clusters showing an order of magnitude speedup from the use of C++ in my
implementation, an up to 3x speedup with a 6-core parallel variant of the
algorithm, and positive results from other optimizations.