DATA DISTRIBUTIONS FOR SPARSE-MATRIX VECTOR MULTIPLICATION

Sparse matrix vector multiplication (SpMxV) is often one of the core c omponents of many scientific applications. Many authors have proposed methods for its data distribution in distributed memory multiprocessor s. We can classify these into four groups: Scatter, D-Way Strip, Recur sive and Miscellaneous. In this work we propose a new method (Multiple Recursive Decomposition (MRD)), which partitions the data using the p rime factors of the dimensions of a multiprocessor network with mesh t opology. Furthermore, we introduce a new storage scheme, storage-by-ro w-of-blocks, that significantly increases the efficiency of the Scatte r method. We will name Block Row Scatter (BRS) method this new variant . The MRD and BRS methods achieve results that improve those obtained by other analyzed methods, being their implementation easier. In fact, the data distributions resulting from the MRD and BRS methods are a g eneralization of the Block and Cyclic distributions used in dense matr ices.