Return to search

Basis Enumeration of Hyperplane Arrangements up to Symmetries

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, Sikiri c, and Sch urmann's method for basis enumeration of polyhedra up to symmetries, including a new pivoting rule for nding 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.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:UNB.1882/44593
Date09 January 2012
CreatorsMoss, Aaron
ContributorsUniversity of New Brunswick, Faculty of Computer Science
PublisherFredericton: University of New Brunswick
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation

Page generated in 0.0022 seconds