%0 Journal Article %J IEEE Transactions on Parallel and Distributed Systems %D 2019 %T Solving Linear Diophantine Systems on Parallel Architectures %A Dmitry Zaitsev %A Stanimire Tomov %A Jack Dongarra %K Mathematical model %K Matrix decomposition %K Parallel architectures %K Petri nets %K Software algorithms %K Sparse matrices %K Task analysis %X Solving linear Diophantine systems of equations is applied in discrete-event systems, model checking, formal languages and automata, logic programming, cryptography, networking, signal processing, and chemistry. For modeling discrete systems with Petri nets, a solution in non-negative integer numbers is required, which represents an intractable problem. For this reason, solving such kinds of tasks with significant speedup is highly appreciated. In this paper we design a new solver of linear Diophantine systems based on the parallel-sequential composition of the system clans. The solver is studied and implemented to run on parallel architectures using a two-level parallelization concept based on MPI and OpenMP. A decomposable system is usually represented by a sparse matrix; a minimal clan size of the decomposition restricts the granulation of the technique. MPI is applied for solving systems for clans using a parallel-sequential composition on distributed-memory computing nodes, while OpenMP is applied in solving a single indecomposable system on a single node using multiple cores. A dynamic task-dispatching subsystem is developed for distributing systems on nodes in the process of compositional solution. Computational speedups are obtained on a series of test examples, e.g., illustrating that the best value constitutes up to 45 times speedup obtained on 5 nodes with 20 cores each. %B IEEE Transactions on Parallel and Distributed Systems %V 30 %P 1158-1169 %8 2019-05 %G eng %U https://ieeexplore.ieee.org/document/8482295 %N 5 %R http://dx.doi.org/10.1109/TPDS.2018.2873354