Development of Innovative Library for Singular Value Decomposition Suited to Multi-Core Processors

适合多核处理器的奇异值分解创新库的开发

• 批准号: 20246027
• 负责人: NAKAMURA Yoshimasa
• 金额: $ 17.72万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (A)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20246027/
• 关键词: 数理工学(数理的解析・計画・設計・最適化); 特異値分解; マルチコアプロセッサ; 特異値計算; 原点シフト戦略; GPGPU; 並列計算; ライブラリ; クラウドコンピューティング; ライブラリー; 可積分系; 計算アルゴリズム; ダルブ変換; グラフィックスプロセッサ; 単精度GPU; 倍精度GPU; GPU; 原点シフト

This project obtains the following fruits in parallel computations with multi-core CPU environments. 1) A shift strategy based on the generalized Newton shift is completed for computing bidiagonal singular values by the mdLVs. 2) A speed up is established in reorthogonalization of singular vectors by using the Householder transformation with the compact WY representation. 3) A speed up of preconditioning process from given dense matrix to bidiagonal is performed. 4) Evaluation both of performance and accuracy of some singular value decomposition algorithms including I-SVD and D & C in double precision computation in GPGPU are discussed. 5) New integrable algorithms for computing eigenvalues and singular values of some class of band matrices are designed. The resulting code DBDSLV of the fast I-SVD algorithm in terms of 1)-4) can be downloaded in the web page as well as many presentations have been given in international workshops and annual meetings and many research papers have been published.

本项目在多核CPU环境下的并行计算中取得了以下成果。 1) 完成了基于广义牛顿位移的位移策略，用于通过 mdLV 计算双对角奇异值。 2) 通过使用具有紧凑 WY 表示的 Householder 变换，在奇异向量的重新正交化中建立加速。 3) 执行从给定稠密矩阵到双对角矩阵的预处理过程的加速。 4)讨论了I-SVD和D&C等奇异值分解算法在GPGPU双精度计算中的性能和精度评估。 5)设计了计算某类带状矩阵的特征值和奇异值的新可积算法。 1)-4)的快速I-SVD算法的结果代码DBDSLV可以在网页下载，并在国际研讨会和年会上进行了多次演示，并发表了许多研究论文。

项目成果

On parallelization of the I-SVD algorithm and its evaluation for clustered singular values

I-SVD算法的并行化及其聚类奇异值评估

• 发表时间: 2009
• 期刊: Proceedings of The 2009 International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA2009)
• 作者: Hiroki Toyokawa;Kinji Kimura;Masami Takata and Yoshimasa Nakamura
• 通讯作者: Masami Takata and Yoshimasa Nakamura

Subtraction-free recurrence relations for lower bounds of the minimal singular value of an upper bidiagonal matrixx

上双对角矩阵 x 的最小奇异值下界的免减递推关系

• 发表时间: 2012
• 期刊: J. Math-for-Industry
• 作者: Takumi Yamashita;Kinji Kimura;and Yoshimasa Nakamura
• 通讯作者: and Yoshimasa Nakamura

Implementation and performance evaluation of new inverse iteration algorithm with Householder transformation in terms of the compact WY representation

基于紧凑 WY 表示的 Householder 变换新逆迭代算法的实现和性能评估

• 发表时间: 2011
• 期刊: Proceedings of The 2011 International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA2011)
• 作者: Hiroyuki Ishigami;Kinji Kimura and Yoshimasa Nakamura
• 通讯作者: Kinji Kimura and Yoshimasa Nakamura

Conserved quantities of the discrete finite Toda equation and lower bounds of the minimal singular value of upper bidiagonal matrices

离散有限Toda方程的守恒量与上双对角矩阵最小奇异值的下界

• 发表时间: 2011
• 期刊: J. Phys. A : Math. Theor
• 作者: Kinji Kimura;Takumi Yamashita and Yoshimasa Nakamura
• 通讯作者: Takumi Yamashita and Yoshimasa Nakamura

Performance Modeling of Multishift QR Algorithms for the Parallel Solution of Symmetric Tridiagonal Eigenvalue Problems

对称三对角特征值问题并行求解的多移 QR 算法性能建模

• 发表时间: 2010
• 期刊: Lecture Notes in Computer Science
• 作者: T.Miyata;Y.Yamamoto;S.-L.Zhang
• 通讯作者: S.-L.Zhang