Premium
Divide‐and‐conquer approach for solving singular value decomposition based on MapReduce
Author(s) -
Zhao Shuoyi,
Li Ruixuan,
Tian Wenlong,
Xiao Weijun,
Dong Xinhua,
Liao Dongjie,
Khan Samee U.,
Li Keqin
Publication year - 2016
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3436
Subject(s) - singular value decomposition , computer science , divide and conquer algorithms , computation , parallel computing , message passing interface , scheduling (production processes) , matrix multiplication , algorithm , theoretical computer science , message passing , mathematical optimization , mathematics , physics , quantum mechanics , quantum
Summary Singular value decomposition (SVD) shows strong vitality in the area of information analysis and has significant application value in most of the scientific big data fields. However, with the rapid development of Internet, the information online reveals fast growing trend. For a large‐scale matrix, applying SVD computation directly is both time consuming and memory demanding. There are many works available to speed up the computation of SVD based on the message passing interface model. However, to deal with large‐scale data processing, a MapReduce model has many advantages over a message passing interface model, such as fault tolerance, load balancing and simplicity. For a MapReduce environment, existing approaches only focus on low rank SVD approximation and tall‐and‐skinny matrix SVD computation, and there are no implementations of full rank SVD computation. In this paper, we propose a MapReduce‐based implementation for solving divide‐and‐conquer SVD algorithm. To achieve high performance, we design a two‐stage task scheduling strategy based on the mathematical characteristics of divide‐and‐conquer SVD algorithm. To further strengthen the performance, we propose a row‐index‐based divide algorithm, a pipelined task scheduling method, and revised block matrix multiplication in MapReduce framework. Experimental result shows the efficiency of our algorithm. Our implementation can accommodate full rank SVD computation of large‐scale matrix very efficiently. Copyright © 2014 John Wiley & Sons, Ltd.