Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/90719
標題: 一個在MapReduce架構下可降低計算量的矩陣相乘演算法
A Computation-Reduction Matrix-Multiplication Algorithm in MapReduce
作者: Yen-Lin Chen
陳彥霖
關鍵字: MapReduce
Matrix-Multiplication
Strassen Algorithm
MapReduce架構
矩陣乘法
Strassen演算法
引用: [1] G. Aggarwal, M. Data, S. Rajagopalan and M. Ruhl, 'On the Streaming Model Augmented with a Sorting Primitive,' Proceedings of Symposium on Foundations of Computer Science, 2004, pages 540-549. [2] J. Dean and S. Ghemawat, 'Mapreduce: Simplified Data Processing on Large Clusters,' Communications of the ACM, 51(1), 2008, pages 107-113. [3] S.Ghemawat, H. Gobioff, and S.-T. Leung, 'The Google File System,' Proceedings of the 9th ACM Symposium on Operating Systems Principles, 2003, pages 29-43. [4] U. Kang, H. Tong, J. Sun, C.-Y. Lin and C. Faloutsos, 'Gbase: AScalable and General Graph Management System,' Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011, pages 1091-1099. [5] U. Kang, C. Tsourakakis and C. Faloutsos, 'Pegasus: A Peta-Scale Graph Mining System Implementation and Observations,' Proceedings of the 9th IEEE International Conference on Data Mining, 2009, pages 229-238. [6] R. Lämmel, 'Google's Mapreduce Programming Model - Revisited,' Science of Computer Programming, 70(1), 2008, pages 1-30. [7] C. Olston, B. Reed, U. Srivastava, R. Kumar and A. Tomkins, 'Pig Latin: a Not-Soforeign Language for Data Processing,' ACM SIGMOD, 2008, pages 1099-1110. [8] V. Strassen, 'Gaussian Elimination is not Optimal,' Numerische Mathematik, 13(4), 1969, pages 354-356. [9] S. Seo, E. Yoon, J. Kim, S. Jim, J.-S. Kim and S. Maeng, 'HAMA: An Efficient Matrix Computation with the MapReduce Framework.' Proceedings of IEEE 2nd International Conference on Cloud Computing Technology and Science, 2010, pages 721-726. [10] Z. Sun, T. Li and N. Rishe, 'Large-Scale Matrix Factorization Using MapReduce,' Proceedings of IEEE International Conference on Data Mining Workshops, 2010, pages 1242-1248. [11] J. Zheng, L.-J. Zhang, R. Zhu, K. Ning and D. Liu, 'Parallel Matrix Multiplication Algorithm Based on Vector Linear CombinationUsing MapReduce,' Proceedings of IEEE 9th World Congress on Services, 2013, pages193-200. [12] D. Cutting, Apache Hadoop, Available at http://hadoop.apache.org/. [13] B. Huang and Y. Wu, Matrix Multiplication in MapReduce,Available: https://www.cs.duke.edu/courses/cps216/current/Project/Project/projects/Matrix_Multiply/proj_report.pdf.
摘要: 矩陣相乘是在線性代數中廣泛被各種應用所使用的方法,例如:科學計算、圖分析等。矩陣相乘需要很多的計算時間,特別是矩陣的大小越大的情況越是顯著。MapReduce架構是一個常使用在雲端運算的平行運算架構,它提供良好的擴展性與容錯能力。在MapReduce架構中,矩陣相乘方法一般以所產生並傳遞的鍵值對(Key-Value Pairs)來判斷方法的複雜度[6][10][12],而矩陣乘法的乘法運算整體的時間複雜度為 ;隨著矩陣大小增大,其效率變得非常差。本研究探討如何運用MapReduce的特性,並參考使用Strassen演算法的概念和以列為單位的設計,來減少計算過程所產生的鍵值對,以有效達到減少傳遞的鍵值對的矩陣相乘方法。本研究運用Strassen演算法的拆解矩陣的概念,並設計非遞迴的方式運算矩陣相乘以達到減少鍵值對的產生。因為Strassen矩陣乘法演算法會遞迴切割原有矩陣成小矩陣之後才進行運算,而在MapReduce架構下的遞迴成本較高,所以本研究設計出新的非遞迴的鍵值比對方式,異於原有Strassen演算法的合併與運算矩陣方式。本研究針對MapReduce架構的特性設計出比其他方法產生更少的鍵值對的矩陣相乘演算法,實驗結果顯示隨著矩陣大小增大,本研究的矩陣相乘演算法所減少矩陣乘法的計算則越顯著,可以有效減少矩陣相乘的時間花費。
URI: http://hdl.handle.net/11455/90719
其他識別: U0005-1108201513325700
文章公開時間: 2018-08-13
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.