Fast Matrix Multiplication with Big Sparse Data

Somasekhar, G.; Karthikeyan, K.

doi:10.1515/cait-2017-0002

Abstract

Big Data becameabuzz word nowadays due to the evolution of huge volumes of data beyond peta bytes. This article focuses on matrix multiplication with big sparse data. The proposed FASTsparse MULalgorithm outperforms the state-of-the-art big matrix multiplication approaches in sparse data scenario.

References

1. Di Felice, P., A. Agnifili, E. Clementini. Data Structures for Compact Sparse Matrices Representation. - J. Adv. Eng. Software, Vol. 11, 1989, No 2, pp. 75-83.10.1016/0141-1195(89)90064-8
Search in Google Scholar Back to article
2. Abadi, D. J. Column-Stores for Wide and Sparse Data. - In: Proc. of 3rd Biennial Conference on Innovative Data Systems Research (CIDR), January 2007, pp. 1-6.
Search in Google Scholar Back to article
3. Neelima, B., S. R. Prakash. Effective Sparse Matrix Representation for the GPU Architectures. - Int. J. of Computer Science, Engineering and Applications (IJCSEA), Vol. 2, 2012, No 2, pp. 151-165.10.5121/ijcsea.2012.2213
Search in Google Scholar Back to article
4. Yuster, R., U. Zwick. Fast Sparse Matrix Multiplication. - J. ACM Transactions on Algorithms (TALG), Vol. 1, 2005, No 1, pp. 2-13.10.1145/1077464.1077466
Search in Google Scholar Back to article
5. Dean, J., S. Ghemawat. Map Reduce: Simplified Data Processing on Large Clusters. - Communications of the ACM, Vol. 51, 2008, No 1, pp. 107-113.10.1145/1327452.1327492
Search in Google Scholar Back to article
6. White, T. H. The Definitive Guide. O’Reilly Media, USA, 2009.
Search in Google Scholar Back to article
7. Buluc, A., J. R. Gilbert. Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments. - Siam J. Sci. Comput., Vol. 34, 2011, No 4, pp. C170-C191.10.1137/110848244
Search in Google Scholar Back to article
8. Ballard, G., A. Bulluc, J. Demmel, L. Grigori, B. Lipshitz, O. Schwartz, S. Toledo. Communication Optimal Parallel Multiplication of Sparse Random Matrices. - In: Proc. of 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures, New York, July 2013, pp. 222-231.10.1145/2486159.2486196
Search in Google Scholar Back to article
9. Smith, S., N. Ravindran, N. D. Sidiropoulos, G. Karypis. SPLATT: Efficient and Parallel Sparse Tensor-Matrix Multiplication. - In: Proc. of 29th IEEE International Parallel & Distributed Processing Symposium, May 2015.10.1109/IPDPS.2015.27
Search in Google Scholar Back to article
10. Sun, Z., T. Li, N. Rishe. Large-Scale Matrix Factorization using Map Reduce. - In: Proc. of International Conference on Data Mining Workshops, December 2010, pp. 1242-1248.10.1109/ICDMW.2010.155
Search in Google Scholar Back to article
11. Seo, S., E. J. Yoon, J. Kim, S. Jin, J. S. Kim, S. Maeng. HAMA: An Efficient Matrix Computation with the Map Reduce Framework. - In: Proc. of IEEE 2nd International Conference on Cloud Computing Technology and Science (Cloud Com), November 2010, pp. 721-726.10.1109/CloudCom.2010.17
Search in Google Scholar Back to article
12. Seo, S., I. Jang, K. Woo, I. Kim, J. S. Kim, S. Maeng. HPMR: Prefetching and Pre-Shuffling in Shared Map Reduce Computation Environment. – In: Proc. of 11th IEEEInternational Conference on Cluster Computing, New Orleans, August 2009, pp. 1-8.10.1109/CLUSTR.2009.5289171
Search in Google Scholar Back to article
13. Myung, J., S. Lee. Matrix Chain Multiplication via Multi Way Join Algorithms in Mapreduce.– In: Proc. of 6th International Conference on Ubiquitous Information Management and Communication, Article No 53, February 2012.10.1145/2184751.2184817
Search in Google Scholar Back to article
14. Zheng, J. H., L. J. Zhang, R. Zhu, K. Ning, D. Liu. Parallel Matrix Multiplication Algorithm Based on Vector Linear Combination Using Map Reduce. – In: Proc. of IEEE 11th World Congress on Services, July 2013, pp.193-200.10.1109/SERVICES.2013.67
Search in Google Scholar Back to article
15. Ceccarello, M., F. Silvestr i. Experimental Evaluation of Multi-Round Matrix Multiplication on Map Reduce. – In: Proc. of ALENEX’15 Meeting on Algorithm Engineering & Experiments, Society for Industrial and Applied Mathematics Philadelphia, January 2015, pp. 119-132.10.1137/1.9781611973754.11
Search in Google Scholar Back to article
16. Choi, J., J. J. Dongarra, R. Pozo, D. W. Walker. Sca LAPACK: A Scalable Linear Algebra Library for Distributed Memory Concurrent Computers. – In Proc. of 4th Sysmposium on the Frontiers of Massively Parallel Computation, IEEE, October 1992, pp. 120-127.
Search in Google Scholar Back to article
17. Bosilca, G., A. Bouteiller , A. Danalis, T. Herault, P. Lemarinier, J. Dongarra. DAGu E: A Generic Distributed DAG Engine for High Performance Computing. – J. Parallel Computing, Vol. 38, 2010, No 1-2, pp. 37-51.10.1016/j.parco.2011.10.003
Search in Google Scholar Back to article
18. Qian, Z., X. Chen, N. Kang, M. Chen, Y. Yu, T. Mosc ibroda, Z. Zhang. Mad LINQ: Large-Scale Distributed Matrix Computation for the Cloud. – In Proc. of 7th ACM European Conference on Computer Systems Euro Sys’2012, Berne, Switzerland, April 2012, pp. 197-210.10.1145/2168836.2168857
Search in Google Scholar Back to article

Fast Matrix Multiplication with Big Sparse Data

Abstract

Paradigm

My account