http://swrc.ontoware.org/ontology#Article
Implementation of Computing Partial Singular Value Decomposition for Principal Component Analysis Using ARPACK
en
[オリジナル論文] Krylov subspace method, IRA algorithm, IRL algorithm, sparse matrix, matrix-vector multiplication
Nara Women's University
Kyoto University
Kyoto University
Kyoto University
Kyoto University
Masami Takata
Sho Araki
Kinji Kimura
Yuki Fujii
Yoshimasa Nakamura
In this paper, we propose a new implementation for computing partial SVD (singular value decomposition) for principal component analysis, which is introduced from the viewpoint of the computational order and the caches of shared-memory multi-core processors. In the new implementation, a target matrix is a sparse matrix, which should be stored in CRS (compressed row storage) or CCS (compressed column storage) formats. SVD can be transformed into eigenvalue problem. In the case when only the partial eigenvalues and eigenvectors from the absolute maximum or the absolute minimum eigenvalue of a target matrix are needed, we use an effective software package, called ARPACK (ARnoldi PACKage). To get the SVDs using ARPACK, the transformed eigenvalue problems can be generally solved through the use of two matrix-vector operations at each iteration. If the size of the target matrix is large, the large number of the elements in the target matrix cause the caches of the shared-memory multi-core processors to overflow. On the other hand, the proposed implementation can achieve a high cache hit ratio because each row in the target matrix can be reused. The proposed implementation is evaluated by experimentation. The experimental results show that the computation time of the proposed implementation is about 75% of that of the conventional implementation.
In this paper, we propose a new implementation for computing partial SVD (singular value decomposition) for principal component analysis, which is introduced from the viewpoint of the computational order and the caches of shared-memory multi-core processors. In the new implementation, a target matrix is a sparse matrix, which should be stored in CRS (compressed row storage) or CCS (compressed column storage) formats. SVD can be transformed into eigenvalue problem. In the case when only the partial eigenvalues and eigenvectors from the absolute maximum or the absolute minimum eigenvalue of a target matrix are needed, we use an effective software package, called ARPACK (ARnoldi PACKage). To get the SVDs using ARPACK, the transformed eigenvalue problems can be generally solved through the use of two matrix-vector operations at each iteration. If the size of the target matrix is large, the large number of the elements in the target matrix cause the caches of the shared-memory multi-core processors to overflow. On the other hand, the proposed implementation can achieve a high cache hit ratio because each row in the target matrix can be reused. The proposed implementation is evaluated by experimentation. The experimental results show that the computation time of the proposed implementation is about 75% of that of the conventional implementation.
AA11464803
情報処理学会論文誌数理モデル化と応用（TOM）
11
1
37-44
2018-03-14
1882-7780