Distributed representation of Sparse Matrix in Quadtree Format

Author: Šimeček I.


Keywords
Sparse matrix format; space complexity.


Abstract
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.


What's new
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).

Known bugs


(Possible) future works

(Will be) used in papers
Distributed representation of Sparse Matrix in Quadtree Format (submitted to PPAM'13)



Parameters and output:
Download:
Quality of distribution 0.4

BACK