一個在PC Cluster平台上的新Preconditioned Conjugate Gradient Method平行演算法;A New Parallel Algorithm of Preconditioned Conjugate Graduate Method on PC Cluster Platform

NCU Institutional Repository > 理學院 > 數學系 > 研究計畫 > Item 987654321/42517

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/42517

題名:	一個在PC Cluster平台上的新Preconditioned Conjugate Gradient Method平行演算法;A New Parallel Algorithm of Preconditioned Conjugate Graduate Method on PC Cluster Platform
作者:	吳維漢;沈澄宇
貢獻者:	數學系
關鍵詞:	數學類
日期:	2005-07-01
上傳時間:	2010-11-30 16:45:37 (UTC+8)
出版者:	行政院國家科學委員會
摘要:	使用 Conjugate Gradient method 來迭代求出線性方程組 AX=B 的根已經是發展相當的時間了，CG 方法收斂速度與矩陣 A 的 condition number 息息相關，為了加速此法的收斂速度，也發展出了各式的 preconditioner 用來降低 A 的condition number,，使得解可以快速的求在最蹧的情況下，一般而言，對n x n 的矩陣A 而言, 此迭代法保證可以在n 次迭代收斂，由於每次迭代須要計算到矩陣乘上向量，共須要O(n^2) 的運算，如此CG 方法最壞的情況下共須要O(n^3)的運算次數。然而對大多數的數值問題而言， A 矩陣多為稀疏矩陣，也就是說，矩陣中的每一行中僅有固定個數的元素不是零，如此在每次迭代中的矩陣乘上向量，只須要O(n) 的運算。當利用適當的資料結構，整個CG 方法只須要O(n^2)的計算量。傳統上的平行計畫都是針對每次迭代中的矩陣乘上向量過程的平行處理，假設有m 個CPU，則每次迭代的計算量在最佳的情況可以減為 O(n/m)。然而CG 法所須要的總迭代次數由於計算上的前後接序(sequential)性質仍然無法透過平行演算加以減少。與傳統CG 平行方式不同處，本計畫將在各別的處理器上發展一平行演算法，研究如何使用與分析各別處理器上的資料，校正各自處理器上的搜尋方向，以達到最佳搜尋路徑，共同架構出最佳的數值解搜尋方向，使得計算解可以更快的求得。研究期間：9308 ~ 9407
關聯:	財團法人國家實驗研究院科技政策研究與資訊中心
顯示於類別:	[數學系] 研究計畫

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	492	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....