Skip to content

Vectorised product table

Vicentini Filippo requested to merge github/fork/attila-i-szabo/product_table into master

Created by: attila-i-szabo

This PR improves the runtime of PermutationGroup.product_table by vectorising the lookups.

The new version first sorts (using np.unique) the array of permutations after appending their index in the group to the end of the row. The same is done with row_perms (these list g^-1 h as permutations for a given g). If the sorted permutation arrays are the same, the group is closed under multiplication, and the product table is built using the appended indices; if there is a mismatch in the permutations, we raise a RuntimeError.

Apparently, not calculating hashes in a big loop speeds things up: calculating the product table of nk.graph.Square(12).space_group() (1152 elements) takes about 4 seconds with the new code, compared to the ~35 seconds the previous versions took on the same machine. It's possible we could improve this performance further, but it seems like a useful stopgap to have.

Merge request reports