,
SYNASC'2012
Minimal Quadtree Format for Compression of Sparse Matrices Storage
Author: Šimeček, I. and Langr, D. and Tvrdik, P.
Keywords

sparse matrix; quadtree; numerical linear algebra;space complexity;space-optimal;storage schemes;


Abstract

Computations with sparse matrices are widespread in scientific projects. Commonly used storage formats (such as COO or CSR) are not suitable for I/O file operations with sparse matrices due to their high space complexities. Memory-efficient formats are still under development. In this paper, we present a new storage format called the {\em Minimal quadtree} (MQ) as well as algorithms for converting matrices from common storage formats to the MQ format. We compare the space complexity of common storage formats and of the MQ format and prove that the idea of using the quadtree as the data structure for sparse matrices is viable.

 



BibTex entry:
@INPROCEEDINGS{JA_SYNASC12,
author = {Šimeček, I. and Langr, D. and Tvrdik, P.},
title = {Minimal Quadtree Format for Compression of Sparse Matrices Storage},
booktitle = {14th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC'2012)},
year = {2012},
series = {SYNASC'2012},
pages = {359-364},
address = {Timisoara, Romania},
month = {sept.},
isbn = {978-0-7695-4934-7},
keywords = {sparse matrix; quadtree; numerical linear algebra;space complexity;space-optimal;storage schemes;} }

BACK