Objectives
To access the presentation, please click here
Abstract: Decomposition is a basic approach to speed-up solving sparse systems on parallel-architectures. Though classic task of a matrix (graph) decomposition is known to be hard. A new kind of decomposition into clans is offered which complexity is linear in the number of nonzero elements. The technique is applicable for solving sparse systems over arbitrary rings (fields) with sign. Analysis of collections of matrices for real-life application shows that lots of matrices are decomposable into clans. A minimal clan size of the decomposition restricts the granulation of the technique. The system decomposition into clans is represented by a weighted graph. The task of constructing a sequence of systems of lower dimension is called an optimal collapse of a weighted graph. Upper and lower bounds for the collapse width, corresponding to the maximal dimension of systems, are derived. A heuristic greedy algorithm of (quasi) optimal collapse is presented and validated statistically. Then the parallel-sequential composition of the system clans is studied. A solver ParAd for Diophantine homogeneous systems is implemented to run on parallel architectures using a two-level parallelization concept: 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.
Basic references
1. Zaitsev D.A., Tomov S., Dongarra J. Solving Linear Diophantine Systems on Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, 05 October 2018.
2. Zaitsev D.A. Sequential composition of linear systems’ clans, Information Sciences, Vol. 363, 2016, 292–307.
3. Zaitsev D.A. Compositional analysis of Petri nets, Cybernetics and Systems Analysis, Volume 42, Number 1 (2006), 126-136.
4. Zaitsev D.A. Decomposition of Petri Nets, Cybernetics and Systems Analysis, Volume 40, Number 5 (2004), 739-746.
Dmitry A. Zaitsev received the Eng. degree in applied mathematics from Donetsk Polytechnic Institute, Donetsk, Ukraine, in 1986, the Ph.D. degree in automated control from the Kiev Institute of Cybernetics, Kiev, Ukraine, in 1991, and the Dr.Sc. degree in telecommunications from the Odessa National Academy of Telecommunications, Odessa, Ukraine, in 2006. He is a Professor of Computer Science at Vistula University, Warsaw, Poland since 2014. He developed the analysis of infinite Petri nets with regular structure, the decomposition of Petri nets in clans, generalized neighborhood for cellular automata, and the method of synthesis of fuzzy logic function given by tables. His current research interests include Petri net theory and its application in networking, computing and automated manufacture. Recently he started working in the area of exascale computing applying his theory of clans to speed-up solving sparse linear systems on parallel and distributed architectures. He was a co-director of joint projects with China and Austria. Recently he has been a visiting professor to Technical University of Dortmund, Germany on DAAD scholarship, to University of Tennessee Knoxville, USA on Fulbright scholarship and to Eindhoven University of Technology, Netherlands. He published a monograph, 3 book chapters and more than a hundred of papers including issues listed in JCR. He is a senior member of ACM and IEEE. For more info please see http://daze.ho.ua
