Call for Paper - September 2022 Edition
IJCA solicits original research papers for the September 2022 Edition. Last date of manuscript submission is August 22, 2022. Read More

An Efficient Storage Format for Large Sparse Matrices based on Quadtree

Print
PDF
International Journal of Computer Applications
© 2014 by IJCA Journal
Volume 105 - Number 13
Year of Publication: 2014
Authors:
Nidhal K. El Abbadi
Elaf J. Al Taee
10.5120/18439-9766

Nidhal El K Abbadi and Elaf Al J Taee. Article: An Efficient Storage Format for Large Sparse Matrices based on Quadtree. International Journal of Computer Applications 105(13):25-30, November 2014. Full text available. BibTeX

@article{key:article,
	author = {Nidhal K. El Abbadi and Elaf J. Al Taee},
	title = {Article: An Efficient Storage Format for Large Sparse Matrices based on Quadtree},
	journal = {International Journal of Computer Applications},
	year = {2014},
	volume = {105},
	number = {13},
	pages = {25-30},
	month = {November},
	note = {Full text available}
}

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

  • 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.
  • Yousef Saad, "Iterative Methods for Sparse Linear Systems", 2003, 2nd edition, Siam publication, pp. 73-101, doi: 10. 1137/1. 9780898718003. ch3.
  • 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.
  • 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.
  • 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
  • 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.
  • 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.
  • 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.