Distributed representation of Sparse Matrix in Quadtree Format
Author: Šimeček I.
Sparse matrix format; space complexity.
Computations with sparse matrices are widespread in scientific projects. Used data format affects strongly the performance.
Efficient formats for storing sparse matrices are still under development, since the computation using widely-used formats (like
XY or CSR) is slow and specialized formats (like SPARSITY or CARB) have a large transformation overhead and are not designed for parallel processing.
In our previous work, we show that idea of using quadtree storage format for sparse matrix can either accelerate computations in numerical linear algebra or leads space efficient sparse matrix storage format.
In this paper, we present two approaches to change the representation of sparse matrix from common used formats to distributed quadtree storage format.
July 1, 2012 - version 0.2 of this project is released (conversion to a row-based format format).
October 1, 2012 - version 0.3 of this project is released (conversion to a balanced row-based format format).
December 1, 2012 - version 0.4 of this project is released (conversion based on the k-d format).
(Possible) future works
- Optimization of SpMV and other linear algebra routines for multi-level parallel system.
(Will be) used in papers
Distributed representation of Sparse Matrix in Quadtree Format (submitted to PPAM'13)
Parameters and output:
- Input is a sparse matrix in a MTX format and the given number of processors.
- Ouput are the parameters of quality of distribution among the given number of processors..
Quality of distribution 0.4