Reliability and Efficiency of the Existing Spectral Methods for Isomorphism Detection

Abstract

Mechanism researchers have developed several types of codes and indices, to indicate if a pair of kinematic chains is isomorphic. Unfortunately, most of these codes or indices are either computationally inefficient or unreliable. This work establishes, for the first time, the reliability of the existing spectral techniques—characteristic polynomial and eigenvector approaches—for isomorphism detection. The reliability of characteristic polynomial of adjacency matrix is established by determining the number of pairs of non-isomorphic chains, with up to 14 links and one, two, and three degrees of freedom. The most recent eigenvector approach is critically reviewed and correct proof is provided for the statement that is the basis for this approach. It is shown, for the first time, that the eigenvector approach was able to identify all nonisomorphic chains, with up to 14 links and one, two, and three degrees of freedom. It is shown that unlike the characteristic polynomial method the eigenvector approach in worst case might take exponential time. Finally, efficient methods are suggested to the classical eigenvector approach by using the Perron–Frobenius theorem.