A divided algorithm to improve Smith's algorithm for a matrix with integer elements and its applications

摘要

In a state equation Ax=b (A/spl epsi/Z/sup m/spl times/,b/spl epsi/Z/sup m/spl times/1/) of Petri nets, it is known that generators of any integer solution x/spl epsi/Z/sup (n+1)/spl times/1/ of the augmented equation Ax=O/sup m/spl times/1/, A:=[A,-b], are obtained by applying Smith's algorithm. In this paper, we propose a divided method such that, first, we obtain generators of any rational solution x/spl epsi/Q/sup (n+1)/spl times/1/ of Ax=0/sup m/spl times/1/ by applying Gaussian elimination and, next, we obtain generators of any integer solution x/spl epsi/Z/sup (n+1)/spl times/1/ by applying the modified Smith's algorithm to the above generators of any rational solution. We hope that the complexity of a divided method is less than that of a direct method.