2024-11-02T23:44:35Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001867092020-10-27T05:02:56Z00934:00989:09407:09408
Implementation of Computing Partial Singular Value Decomposition for Principal Component Analysis Using ARPACKImplementation of Computing Partial Singular Value Decomposition for Principal Component Analysis Using ARPACKeng[オリジナル論文] Krylov subspace method, IRA algorithm, IRL algorithm, sparse matrix, matrix-vector multiplicationhttp://id.nii.ac.jp/1001/00186621/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=186709&item_no=1&attribute_id=1&file_no=1Copyright (c) 2018 by the Information Processing Society of JapanNara Women's UniversityKyoto UniversityKyoto UniversityKyoto UniversityKyoto UniversityMasami, TakataSho, ArakiKinji, KimuraYuki, FujiiYoshimasa, NakamuraIn 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）11137442018-03-141882-77802018-03-08