Systolic arrays for parallel matrix g-inversion and finding Petri net invariants (Q1822901)

The paper deals with the solution of the homogeneous linear system \(Ax=0\), where A is an \(m\times n\) matrix with rational entries and \(x=(x_ 1,...,x_ n)'\) is the unknown vector having integral or rational components. The general solution of the system is given by \(x=(I-A^-A)y\), where y is an arbitrary vector and \(A^-\) is an \(n\times m\) matrix satisfying \(AA^-A=A.\) An algorithm for computing the generalized inverse \(A^-\) is described. The proposed algorithm is suitable for rational or exact arithmetic and uses a divide and conquer strategy of finding the g-inverse \(A^-\) of A column by column. A single instruction systolic array (SISA) able to execute this algorithm is proposed. The architecture consists of an \(n\times m\) mesh connected array of identical processing elements (PEs). Each PE is able to execute a fixed instruction set and communicates with its four neighbours. Also, each PE has one instruction register and is supplied with instructions from the outside in a systolic manner. The architecture is done more flexible by supplying each row and column of the array with an additional flow of selector bits, each PE executing the received instruction only if it receives true values of the selector bits. The SISA subprograms leading to a SISA implementation of one iteration of the above algorithm are also presented. The performance of SISA concerning the response time and the period is analyzed. Some remarks related to the fault-diagnosis are also given. An application concerning the finding of Petri net invariants is discribed.