Parallel Digraphs-building Computer Algorithm for Finding a Set of Characteristic Polynomial Realisations of Dynamic System

This paper presents in-depth the parallel computer algorithm for the determination of characteristic polynomial realisations of dynamic system. The main differences between the depicted method and other state of- the-art solutions include finding not few realisations, but a whole set, and the fact that the found realisations are always minimal among all possible. As digraphsbuilding methods used in the algorithm are NP-complete or NP-hard problems, the algorithm is paralleled and GPGPU (General-Purpose computing on Graphics Processor Units) computation is proposed as the only feasible solution. The article describes in detail the proposed method, discusses it’s complexity, presents optimisation solutions and still open problems. The working algorithm is illustrated with a numerical example and compared to results of other known methods.