An Algorithm for Canonical Forms of Finite Subsets of Z(d) up to Affinities

作者：Paolini Giovanni^*

来源：Discrete & Computational Geometry, 2017, 58(2): 293-312.

DOI：10.1007/s00454-017-9895-6

• Computational complexity
• Integral linear algebra
• Canonical form
• Group theory

In this paper we describe an algorithm for the computation of canonical forms of finite subsets of Z(d), up to affinities over Z. For fixed dimension d, this algorithm has worst-case asymptotic complexity O (n log(2) ns mu(s)), where n is the number of points in the given subset, s is an upper bound to the size of the binary representation of any of the n points, and mu(s) is an upper bound to the number of operations required to multiply two s-bit numbers. In particular, the problem is fixed-parameter tractable with respect to the dimension d. This problem arises e.g. in the context of computation of invariants of finitely presented groups with abelianized group isomorphic to Z(d). In that context one needs to decide whether two Laurent polynomials in d indeterminates, considered as elements of the group ring over the abelianized group, are equivalent with respect to a change of basis.

• 出版日期2017-9