Approximate multiplication of nearly sparse matrices with decay in a fully recursive distributed task-based parallel framework

arXiv1906.08148MaRDI QIDQ6320740FDOQ6320740

Authors: Anton G. Artemov 

Publication date: 19 June 2019

Abstract: In this paper we consider parallel implementations of approximate multiplication of large matrices with exponential decay of elements. Such matrices arise in computations related to electronic structure calculations and some other fields of computational science. Commonly, sparsity is introduced by dropping out small entries (truncation) of input matrices. Another approach, the sparse approximate multiplication algorithm [M. Challacombe and N. Bock, arXiv preprint 1011.3534, 2010] performs truncation of sub-matrix products. We consider these two methods and their combination, i.e. truncation of both input matrices and sub-matrix products. Implementations done using the Chunks and Tasks programming model and library [E. H. Rubensson and E. Rudberg, Parallel Comput., 40:328-343, 2014] are presented and discussed. We show that the absolute error in the Frobenius norm behaves as $Oleft(n^{1/2}ight),nlongrightarrowinfty$ and $Oleft(a{u}^{p/2}ight),aulongrightarrow0,,,forallp<2$ for all three methods, where $n$ is the matrix size and $au$ is the truncation threshold. We compare the methods on a model problem and show that the combined method outperforms the original two. The methods are also applied to matrices coming from large chemical systems with $sim10^6$ atoms. We show that the combination of the two methods achieves better weak scaling by reducing the amount of communication by a factor of $approx2$.

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)

This page was built for publication: Approximate multiplication of nearly sparse matrices with decay in a fully recursive distributed task-based parallel framework

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320740)