CFP last date
22 April 2024
Reseach Article

An Efficient Storage Format for Large Sparse Matrices based on Quadtree

by Nidhal K. El Abbadi, Elaf J. Al Taee
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 105 - Number 13
Year of Publication: 2014
Authors: Nidhal K. El Abbadi, Elaf J. Al Taee
10.5120/18439-9766

Nidhal K. El Abbadi, Elaf J. Al Taee . An Efficient Storage Format for Large Sparse Matrices based on Quadtree. International Journal of Computer Applications. 105, 13 ( November 2014), 25-30. DOI=10.5120/18439-9766

@article{ 10.5120/18439-9766,
author = { Nidhal K. El Abbadi, Elaf J. Al Taee },
title = { An Efficient Storage Format for Large Sparse Matrices based on Quadtree },
journal = { International Journal of Computer Applications },
issue_date = { November 2014 },
volume = { 105 },
number = { 13 },
month = { November },
year = { 2014 },
issn = { 0975-8887 },
pages = { 25-30 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume105/number13/18439-9766/ },
doi = { 10.5120/18439-9766 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:37:39.208714+05:30
%A Nidhal K. El Abbadi
%A Elaf J. Al Taee
%T An Efficient Storage Format for Large Sparse Matrices based on Quadtree
%J International Journal of Computer Applications
%@ 0975-8887
%V 105
%N 13
%P 25-30
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

There are serious problem for storage sparse matrix due to west of memory used for storage the non-zero values which represent more than 90% of sparse matrix. There are many algorithms suggested for solving this problem. A new storage method for large sparse matrices was presented in this paper based on quadtree. The suggested algorithm utilized the idea of quadtree to re-represent the sparse matrix in two vectors, which reduce the required memory space for storage sparse matrix. The suggested algorithm reduced the memory space required to store the zero values to more than 85%. The algorithm compared with many algorithms and it was more efficient than almost all the previous algorithms up to our knowledge. The current algorithm characterized by less space storage need, highly speed, and easy to implement.

References
  1. Ivan P. Stanimirovic´ and Milan B. Tasic´, 2009. "Performance Comparison of Storage Formats for Sparse Matrices", FACTA UNIVERSITATIS (NI?S) Ser. Math. Inform. 24 (2009), 39–51.
  2. Yousef Saad, "Iterative Methods for Sparse Linear Systems", 2003, 2nd edition, Siam publication, pp. 73-101, doi: 10. 1137/1. 9780898718003. ch3.
  3. Pinaki Mazumder, 1987. "Planar Decomposition for Quadtree Data Structure", Ccomputer Vision, Graphics, and Image Processing, Volume 38, Issue 3, June 1987, Pages 258–274, DOI: 10. 1016/0734-189X (87)90113-7.
  4. Anand Ekambaram, Eurípides Montagne, 2003. " An Alternative Compressed Storage Format for Sparse Matrices", Computer and Information Sciences - ISCIS 2003 , Lecture Notes in Computer Science, Volume 2869, 2003, pp 196-203, DOI: 10. 1007/978-3-540-39737-3_25.
  5. Mats Aspn¨as, Artur Signell, and Jan Westerholm, 2007. "E?cient Assembly of Sparse Matrices Using Hashing", B. K?agstro¨m et al. (Eds. ): PARA 2006, LNCS 4699, pp. 900–907, 2007. Springer-Verlag Berlin Heidelberg 2007
  6. Tomáš Oberhuber, Atsushi Suzuki, Jan Vacata, 2011, "New Row Grouped CSR Format for Storing Sparse Matrices on GPU with Implementation in CUDA", Acta Technica journal, 56, pp 447–466.
  7. Aiyoub Farzaneh, Hossein Kheiri, and Mehdi Abbaspour Shahmersi, 2009. "An Efficient Storage Formation for Large Sparse Matrices", Commun. Fac. Sci. Univ. Ank. Series A1 Volume 58, Number 2, Pages 110 (2009) ISSN 13035991.
  8. A. Dziekonski, A. Lamecki, and M. Mrozowski, 2011, "A MEMORY EFFICIENT AND FAST SPARSE MATRIX VECTOR PRODUCT ON A GPU", Progress In Electromagnetics Research, Vol. 116, pp. 49–63.
Index Terms

Computer Science
Information Sciences

Keywords

Sparse matrix quadtree compression decompression