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.

Giovanni Paolini (2017). An algorithm for canonical forms of finite subsets of Z^d up to affinities. DISCRETE & COMPUTATIONAL GEOMETRY, 58(2), 293-312 [10.1007/s00454-017-9895-6].

An algorithm for canonical forms of finite subsets of Z^d up to affinities

Giovanni Paolini
2017

Abstract

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
Giovanni Paolini (2017). An algorithm for canonical forms of finite subsets of Z^d up to affinities. DISCRETE & COMPUTATIONAL GEOMETRY, 58(2), 293-312 [10.1007/s00454-017-9895-6].
Giovanni Paolini
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/943178
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact