Basis enumeration of hyperplane arrangements up to symmetries

Loading...
Thumbnail Image
Date
2012
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.
Description
Keywords
Citation