Computer Science ›› 2018, Vol. 45 ›› Issue (11): 298-303.doi: 10.11896/j.issn.1002-137X.2018.11.048

• Interdiscipline & Frontier • Previous Articles     Next Articles

Parallel CP Tensor Decomposition Algorithm Combining with GPU Technology

WU Yu, YAN Guang-hui, WANG Ya-fei, MA Qing-qing, LIU Yu-xuan   

  1. (School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730030,China)
  • Received:2017-10-20 Published:2019-02-25

Abstract: With the emergence of high-dimensional data,tensor and tensor decomposition have draw widespread attention in the field of data alanlysis.The high dimensionality and sparsity of tensor data results in a high computational complexity of tensor methods,which becomes an obstacle to the application of tensor decomposition in practical.Many researchers have introduced the parallel computing methods to improve the efficiency of tensor decomposition algorithm.Based on the existing research,this paper presented a GPU parallel CP tensor decomposition algorithm through simply calculating Khatri-Rao product,called ParSCP-ALS algorithm.The experimental results show that the proposed ParSCP-ALS algorithm can effectively improve the computational efficiency of CP tensor decomposition compared with the existing parallel algorithm.On the Movielens data set,the ParSCP-ALS algorithm reduces the computational time by about 58% compared with the existing parallel algorithm.

Key words: CP tensor decomposition, CP-ALS, CUDA, GPU

CLC Number: 

  • TP391
[1]LI X T.Research on Key Technologies of Multi-Relational Graph Mining Based on Tensors[D].Harbin:Harbin Institute of Technology,2013.(in Chinese)
李旭涛.基于张量的多关系图挖掘关键技术研究[D].哈尔滨:哈尔滨工业大学,2013.
[2]YANG B,LIU D Y,LIU J M,et al.Complex Network Clustering Algorithms[J].Journal of Software,2009,20(1):54-66.(in Chinese)
杨博,刘大有,LIU J M,等.复杂网络聚类方法[J].软件学报,2009,20(1):54-66.
[3]MØRUP M.Applications of tensor (multiway array) factorizations and decompositions in data mining[J].Wiley Interdisciplinary Reviews Data Mining & Knowledge Discovery,2011,1(1):24-40.
[4]HITCHCOCK F L.The expression of a tensor or a polyadic as a sum of products[J].Journal of Mathematics and Physics,1927,6(1-4):164-189.
[5]KOLDA T G,BADER B W.Tensor Decompositions and Applications[J].Siam Review,2009,51(3):455-500.
[6]HARSHMAN R A.Foundations of the PARAFAC procedure:Model and conditions for an ‘explanatory’multi-mode factor analysis [J].UCLA Working Papers in Phonetics,1970,16:1-84.
[7]CARROLL J D,PRUZANSKY S,KRUSKAL J B.CAN- DELINC:a general approach to multi dimension analysis of many-way arrays with linear constraints on parameters[J].Psychometrika,1980,45(1):3-24.
[8]PAPALEXAKIS E E,FALOUTSOS C,SIDIROPOULOS N D.ParCube:Sparse Parallelizable Tensor Decompositions[J].Acm Transactions on Knowledge Discovery from Data,2012,10(1):521-536.
[9]ANTIKAINEN J,HAVEL J,JOSTH R,et al.Nonnegative Tensor Factorization Accelerated Using GPGPU[J].IEEE Transactions on Parallel & Distributed Systems,2011,22(7):1135-1144.
[10]ZOU B,LI C,TAN L,et al.GPUTENSOR:Efficient tensor factorization for context-aware recommendations[J].Information Sciences,2015,299:159-177.
[11]KANG U,PAPALEXAKIS E,HARPALE A,et al.GigaTensor:scaling tensor analysis up by 100 times-algorithms and discoveries[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2012:316-324.
[12]COOK S.CUDA Programming-A Developer’s Guide to Parallel Computing with GPUs[M].Beijing:China Mechine Press,2014.(in Chinese)
COOK S.CUDA并行程序设计[M].北京:机械工业出版社,2014.
[13]BELL N,GARLAND M.Efficient Sparse Matrix-Vector Multiplication on CUDA[OL].http://www.users.csbsju.edu/~mheroux/fau2013_csci317/SPMV-Garland-Bell.pdf.
[14]LEY M.DBLP:some lessons learned[J].Proceedings of the VLDB Endowment,2009,2(2):1493-1500.
[15]HARPER F M,KONSTAN J A.The MovieLens Datasets:History and Context[J].ACM Transactions on Internactive Intelligent Systmes(TiiS),2015,5(4):19.
[1] GUO Zheng-wei, FU Ze-wen, LI Ning, BAI Lan. Study on Acceleration Algorithm for Raw Data Simulation of High Resolution Squint Spotlight SAR [J]. Computer Science, 2022, 49(8): 178-183.
[2] ZONG Di-di, XIE Yi-wu. Model Medial Axis Generation Method Based on Normal Iteration [J]. Computer Science, 2022, 49(6A): 764-770.
[3] WANG Jin, LIU Jiang. GPU-based Parallel DILU Preconditioning Technique [J]. Computer Science, 2022, 49(6): 108-118.
[4] LI Fan, YAN Xing, ZHANG Xiao-yu. Optimization of GPU-based Eigenface Algorithm [J]. Computer Science, 2021, 48(4): 197-204.
[5] HU Rong, YANG Wang-dong, WANG Hao-tian, LUO Hui-zhang, LI Ken-li. Parallel WMD Algorithm Based on GPU Acceleration [J]. Computer Science, 2021, 48(12): 24-28.
[6] WEN Min-hua, WANG Shen-peng, WEI Jian-wen, LI Lin-ying, ZHANG Bin, LIN Xin-hua. DGX-2 Based Optimization of Application for Turbulent Combustion [J]. Computer Science, 2021, 48(12): 43-48.
[7] WANG Liang, ZHOU Xin-zhi, YNA Hua. Real-time SIFT Algorithm Based on GPU [J]. Computer Science, 2020, 47(8): 105-111.
[8] LIU Shi-fang, ZHAO Yong-hua, YU Tian-yu, HUANG Rong-feng. Efficient Implementation of Generalized Dense Symmetric Eigenproblem StandardizationAlgorithm on GPU Cluster [J]. Computer Science, 2020, 47(4): 6-12.
[9] ZUO Xian-yu, ZHANG Zhe, SU Yue-han, LIU Yang, GE Qiang, TIAN Jun-feng. Extraction Algorithm of NDVI Based on GPU Multi-stream Parallel Model [J]. Computer Science, 2020, 47(4): 25-29.
[10] XU Xin-peng, HU Bin-xing. Fast Calculation Method of Aircraft Component Strength Check Based on ICCG [J]. Computer Science, 2020, 47(11A): 624-627.
[11] KANG Lin-yao, TANG Bing, XIA Yan-min, ZHANG Li. GPU-accelerated Non-negative Matrix Factorization-based Parallel Collaborative Filtering Recommendation Algorithm [J]. Computer Science, 2019, 46(8): 106-110.
[12] ZHENG Hong-bo, SHI Hao, DU Yi-cheng, ZHANG Mei-yu, QIN Xu-jia. Fast Stripe Extraction Method for Structured Light Images with Uneven Illumination [J]. Computer Science, 2019, 46(5): 272-278.
[13] ZHANG Yi-ran, CHEN Long, AN Xiang-zhe, YAN Shen-gen. Study on Performance Optimization of Reduction Algorithm Targeting GPU Computing Platform [J]. Computer Science, 2019, 46(2): 306-314.
[14] LU Xian-hua, WANG Hong-jun. Design of Distributed News Clustering System Based on Big Data Computing Framework [J]. Computer Science, 2019, 46(11A): 220-223.
[15] ZHU Chao, WU Su-ping. Parallel Harris Feature Point Detection Algorithm [J]. Computer Science, 2019, 46(11A): 289-293.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!