Aggregation of clans to speed-up solving linear systems on parallel architectures

Abstract

The paper further refines the clan composition technique that is considered a way of matrix partitioning into a union of block-diagonal and block-column matrices. This enables solving the individual systems for each horizontal block on a separate computing node, followed by solving the composition system. The size of minimal clans, obtained as a result of matrix decomposition, varies considerably. For load balancing, early versions of ParAd software were using dynamic scheduling of jobs. The present paper studies a task of static balancing the clan size. Rather good results are obtained using a fast bin packing algorithm with the first fit on a sorted array which are considerably improved applying a multi-objective graph partitioning with software package METIS. Aggregation of clans allows us to obtain up to three times extra speed-up, including systems over fields of real numbers, on matrices from Model Checking Contest and Matrix Market.

Keywords:

• Linear system
• parallel architecture
• clan composition
• graph partitioning
• speed-up
• load balancing

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The paper is partially supported by the Fullbright Scholar Programme for the first author's scholarship to visit the Innovative Computing Laboratory at the University of Tennessee, Knoxville, USA, during autumn of 2017.