Computation of Automorphism Groups of q-ary Codes



Authors
Yekaterina Zhmud and Evgeny Gorkunov, Novosibirsk State University


ABSTRACT

The purpose of this work is to develop and implement an effective algorithm to find automorphism groups of different algebraic and combinatorial objects in n-dimensional vector space over finite field. (Automorphisms are isometries that map the code into itself.) An “effective” algorithm is an algorithm that benefits the exhaustive search and can be used for very big code where the general number of isometries are more than 107. We use the First String Method (FSM) to deal with the automorphism groups used in cryptography and coding theory. It also gives information about code structure, and if in this project the algorithm of this method is proved effective, we will unite it with other algorithms into one tool for theoretical investigations.

The FSM benefits exhaustive search for the ternary codes with code length 4, 5, and 6. To learn if it would be effective, the method needed to be tested with “big” codes. Initially, we decided to find first string for some codes using a 32-core development environment. This could help modify the method for use with concrete codes and get clearer results in testing. It turned out that a different way of testing was actually more helpful. We tested complete algorithms on different codes, and this testing gave more information about efficiency of this method after the first tests.

To test our project we used the Intel® Manycore Testing Lab to execute the parallel algorithm of the first string method on 4 codes. This also gave us information about time of execution of a parallel exhaustive search on the same codes.

Results

Before the testing started, automorphism groups were found using exhaustive search for these codes. Work of exhaustive search on the code with the largest number of isometries was expected to take about 40 hours.  The execution of the first string method was expected to take about an hour, but finished after 6 minutes! Testing on the other 3 codes also proved that this method is effective on these kinds of codes.

The table below shows some of our testing results. The first column shows the general number of isometries in the space and the second column shows the time of parallel exhaustive search in seconds. The third column is the time of parallel algorithm of first string method in seconds. The table demonstrates that for the biggest code the first string method is more than 20 times more efficient than exhaustive search.

Isometries

Exhaustive Search

First String Method

106

4.8 seconds

1.5 seconds

107

64.8

59.7

107

29.8

1.6

 

Figure 1. Exhaustive Search vs. First String Method as measured in seconds.

1010

 

8211.6

362.2


Conclusion

There are several other tests that can be done in this area that are still pending. Next steps would include continuing to work with the Intel® Manycore Testing Lab to test our method on code with general number of isometries greater than 1010. We are also planning to make the first string method auto-tuning for using on codes with different structure.

Author Bio

Yakaterina ZhumdYakaterina Zhumd is a student at Novosibirsk State University. With the support of her scientific advisor Evgeny Gorkunov, she used the Intel® Manycore Testing Lab to perform these tests as part of the qualification work for her Bachelor’s Degree in Computational Science.


For more complete information about compiler optimizations, see our Optimization Notice.
Categories: