Algorithm Automorphism Incidence Matrix Orbit Matrix Group Action Canonical Form BIBD
Issue Date:
2008
Publisher:
Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Journal of Computing, Vol. 2, No 4, (2008), 349p-368p
Abstract:
The author developed computer programs needed for the classification
of designs with certain automorphisms by the local approach method.
All these programs use canonicity test or/and construction of canonical form
of an integer matrix. Their efficiency substantially influences the speed of
the whole computation. The present paper deals with the implemented
canonicity algorithm. It is based on ideas used by McKay, Meringer, Kaski
and Bouyukliev, but while their algorithms are for the equivalence test, the
canonicity test or finding canonical representative of only one type of
combinatorial object (graph, code, design, binary matrix, etc.), the algorithm
presented in this paper is meant to work fast on all types of integer matrices
used for the classification of designs with predefined automorphisms. This
is achieved through the suitable spectrum invariant, and the way it is used
to cut off some branches of the search tree.
Description:
Partially supported by the Bulgarian Science Fund contract with TU Varna, No 487.
