矩陣分解的低延遲並行算法

《矩陣分解的低延遲並行算法》是依託武漢大學，由向華擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：矩陣分解的低延遲並行算法
• 項目類別：青年科學基金項目
• 項目負責人：向華
• 依託單位：武漢大學

項目摘要

在並行計算中通訊延遲的改進要慢於浮點運算速度和網路頻寬的提高，針對並行LU分解中的通訊延遲，提出一種新的選主元策略以減少其通訊開銷，改進目前ScaLAPACK中的PDGETRF函式。考察此分解過程的增長因子和向後誤差，用統計和分析的方法總結分析這一選主元策略的數值穩定性。對於大規模稀疏矩陣的LU分解，非零元的填充需要大量記憶體，矩陣重排技術變得格外重要，對矩陣重排整體上利用圖剖分技術，如hMetis，PaToH等；局部用MMD，AMD等方法，來減少非零元的填充，並使重排後的數據結構適合於並行化。類似的並行策略用到Rank Revealing QR，以少的通訊次數選出範數較大的列，從而減少通訊延遲，改進ScaLAPACK中的PxGEQPF函式，提高現有數值軟體的效率。並將結果用於低秩逼近，構造Schur補預條件子，改善Krylov子空間疊代法的收斂。

結題摘要

該項目主要考慮並行計算中通訊延遲的改進要慢於浮點運算速度和網路頻寬的提高（浮點運算每年提高的速度是59%，頻寬每年提高26%，而通訊延遲提高的幅度則小得多，每年只有15%左右），針對並行LU分解中的通訊延遲，提出基於binary tree和flat tree的選主元策略，並保持算法數值穩定性；相關工作已接收發表。算法用於大規模稀疏矩陣，由於非零元素的填充需要大量記憶體，涉及到矩陣重排技術（整體上用圖剖分，如hMetis，PaToH等；局部用MMD，AMD等）。該並行策略還可用於RRQR，據分解所得上三角陣判定數值秩。相關內容已整理完稿即將發表。這裡涉及到的LU和QR矩陣分解是數值計算中非常基本的問題，對它們的改進將會使已有數值軟體更高效，具有理論意義和實際意義。