jacobi矩陣特征值的并行算法

1、第 2 4卷第 1 期 紡 織 高 校 基 礎(chǔ) 科 學(xué) 學(xué) 報 V o 1 ． 2 4 ， N o ． 12 011年 3月B AS I CS C I E NC E SJ O UR NA LOFT E X T I L EUN I V E RS I T I E SMa r c h ， 2 011文 章編 號 ： 1 0 0 6 - 8 3 4 1 ( 2 0 1 1 ) 0 1 - 0 0 2 1 - 0 5J a c o b i 矩

2、 陣特征值 的并行算 法 劉艷 紅 ， 呂全 義 ( 西北工業(yè) 大學(xué) 應(yīng)用數(shù)學(xué)系 ， 陜西 西安 7 1 0 1 2 9 )摘 要 ： 提 出 了并行 求解 實三 對 角矩 陣特 征 值 方 法 ， 該 方 法主 要針 對 J a c o b i 矩 陣． 應(yīng) 用 求 多項 式根 的 S t u r m法， 將矩陣特征 多項式的求根 區(qū)間隔離成單根 區(qū)間； 對 已隔 離出的單根 區(qū)間先用二分法 求解 ， 達到一定精度后再 用牛頓法精確

3、求解． 考慮到處理機 負載平衡 問題 ， 將 求根 區(qū)間分成若干 等分 ， 然后按 區(qū)間循環(huán)地將其分給各個處理機． 各處理機并行地進行 求根計算， 它們之 間無通信．通過此方法實現(xiàn) 了處理機負載平衡 ， 算法并行效率達 0 ． 8 5以上． 數(shù)值算例表 明了此并行算法的高效性 ．關(guān)鍵詞 ： J a c o b i 矩陣； S t u r m 法； 牛頓法 ； 并行算法； 并行效率 中圖分 類號 ： 02 4 6文 獻標(biāo) 識碼 ： A矩陣

4、特征值問題不僅可直接解決諸如非線性規(guī)劃 、 優(yōu)化 、 常微分方程等各類數(shù)學(xué)計算問題 ， 而且在結(jié) 構(gòu)力學(xué)、 工程設(shè)計、 計算物理和量子力學(xué)中具有廣泛的應(yīng)用． 由于它具有重要的理論和實際意義 ， 所 以矩陣 特征值 問題成為當(dāng)前國內(nèi)外高性能計算機 的主要計算任務(wù)之一． 國內(nèi)外許 多學(xué)者對矩 陣特征值 問題進行 了深入研究 ， 其大多可歸結(jié)于計算三對角矩 陣的特征值． 目前 ， 三對角矩 陣特征值 的求解方法主要有 Q n法? 、 分而治之

5、法 ] 、 分裂一 合并法 【 3 ] 、 S t u r m序列法 L 4等． 文獻[ 1 ] 介紹 了帶 Wi l k i n s o n位移的 Q R法 ； 文獻 [ 2 — 3 ] 基于分治思想將矩陣做降階分塊處理 ， 然后并行求解 ； 文獻[ 4 ] 基 于二分法提出了并行求解算法 ， 但 負載平衡 問題沒有很好解決。 關(guān) 于大型三對角矩陣特征值的并行求解 問題 ， 實現(xiàn)負載平衡仍然面臨很大挑 戰(zhàn)． 本文提出并行求解 J a

6、 c o b i 矩陣全部特征值 的方法 ， 首先將求根區(qū)間分成 幻(為正整數(shù) ， P為處理機臺數(shù) ) 等分 ， 然后按區(qū)間循環(huán)地將其分給各個處理機． 各處理機在 明確 自己的所有求根 區(qū)問后 ， 進行并行求 根計算． 計算過程中處理機之問不需通信， 此方法有效地實現(xiàn)了負載平衡 ， 且達到最小耗時效果．1預(yù)備 知識 定義 1 [ 5實系數(shù)多項式序列 f 0 ()()() ， ?() ， 如果滿足條件 ( 1 )() 在( a ， 6 )

7、內(nèi)沒有實根 ；( 2 )相 鄰 的 2個 多項 式 一()()( 1≤ k≤ m)在 ( a， 6 )內(nèi)沒有 公共 根 ；( 3 )如果 是序列 中某多項式 ()( 1 ≤ k ≤m一1 ) 的根 ， 則A一() 和 + 。 () 異號； 則稱該多項 式 序列 為 )在 區(qū) 間 ( a ， b )的 S t u r m序列 ．定義 2 【 6設(shè)三對角矩陣 收稿 日期 ： 2 0 1 0 - 0 9 - 2 5基金項 目： 陜西 省 自

8、然科學(xué)基金資助項 目( 2 0 0 9 J M 1 0 0 8 )通 訊作者 ： 呂全義 ( 1 9 6 3 一 ) ，女 ， 遼寧省沈 陽市人 ， 西北 工業(yè)大學(xué)教授 ． E — ma i l ； l u q u a n @n w p u 。 c d u ． c n第 l 期 J a c o b i 矩陣特征值 的并行算法 2 3．， 、 、( A —b “ 1 )I ( A)一a k c II 一 1 ( A)+( A)“八^一

9、( A —b “ 1 )I ( A )一a k c II一 1( A )’再利 用 D( A)=( A )( A ) ， 得遞 推公 式 △+ l ( A )= [ ( A—b I + 1 ) △ I ( A ) D I ( A )一a k C ‘ △ ‘ 一 l ( A )+D( A ) ] ／ [ ( A—b “ ． 1 ) D I ( A )一a k C I ] ．( 2 )由新序列的構(gòu)造中式 D( A )=一1 知 ， 當(dāng) D

10、¨ ( A )=0時， 對 D( A ) 做 了特殊處理 ， 即用 D( A )=一1 代替 ( A )=一∞． 這種處理方法不影響變號數(shù) ( A ) 的計算 ， 但當(dāng)計算式 ( 2 ) 中的△ 川 ( A ) 時會 出現(xiàn)錯 誤 ， 需要重新處理． 本文采用的方法為當(dāng) D( A )=0 時 ， 對式 ( 2 )右端取極限 ， 得 擊 ㈨+再 由△ 。 ( A )=。 ( A ) ／。 ( A )=0 ， △( A )：l

11、／ ( A—b) ， D()=A一6， 可遞推求得 △( A ) ． 最終 ， 得 N e w t o n 迭代公式為 A=A—l ／ △( A) ．3實現(xiàn)處理機之 間負載平衡 方案 設(shè)有P 臺處理機 ， 在算法的并行實現(xiàn)過程中， 如果直接將求根區(qū)間P 等分 ， 每臺處理機計算一個 區(qū)間上 的特征值 ， 這種處理方法對于特征值分布比較均勻 的矩 陣， 負載基本上是均衡 的． 但對 于特征值分 布不均 勻的矩陣， 每個區(qū)問所包含 的特征值

12、個數(shù)不同， 特征值 的計算量和計算時間不 同 ， 使得處理機之間的負載 不均衡． 此時一部分機子處于閑置狀態(tài)而一部分機子處于忙碌狀態(tài) ， 由于等待個別處理機的計算結(jié)果 ， 使 得計算 時間加長． 為此 ， 采用如下方案 ， 保證處理機之問負載平衡．方案如圖 1 所示 ， 首先將包含矩陣特征值的求根區(qū)間分成 個小區(qū)間 ， 然后按區(qū)問循環(huán)地將其分給各 個處理機． 第一輪區(qū)間分配 ： 將第一個 區(qū)間給第一個進程 ， 第二個區(qū)間給第二個進程 ，

13、 依次下去， 第 P個區(qū) 問給第 P個進程 ； ??； 第 i 輪區(qū)問分配 ： 將第 ( i 一1 ) p+1 個區(qū)間給第一個進程 ， 第 ( i 一1 ) p+2 個區(qū)問給 第二個進程 ， ??， 第 個 區(qū)間給第P 個進程 ； 如此周期性循環(huán)地將小區(qū)間分給各個處理機． 當(dāng)把所有 的 個區(qū)間分配給各個處理機之后 ， 各個處理機開始并行計算各 自所得 k 個區(qū)問上的特征值． 在計算過程 中，進程之問不需要通信． 各處理機將 自己所得到的

14、 k 個 區(qū)間上 的特征值計算完成后 ， 主進程對所有進程的計 算結(jié)果進行一次收集 ， 從而得到區(qū)間的所有特征值．1 p2 p圖 1負載平衡 示意 圖 周期性循環(huán)分配區(qū)間法 ， 使得各進程在特征值分布稠密的一段區(qū)間上都有稠密的小區(qū)間 ， 在特征值分 布稀疏的一段區(qū)間上也都有稀疏的小區(qū)問， 較好地實現(xiàn)負載平衡． 而且進程在并行求根 計算時 ， 不需要通 信 ， 只在各進程將 自己所有的任務(wù)完成后 ， 主進程收集計算結(jié)果．4算 法 的并行

15、實現(xiàn) 步驟及 算例4 ． 1算 法步 驟 ( 1 )利用 G e r s c h g o r i n圓盤定理確定矩陣特征值的下界 a a和上界 6 6 ， 得到求根區(qū)間[ a a ， b b ] ．( 2 )將包含矩陣特征值的求根 區(qū)間[ a a ， b b ] 分成 個小 區(qū)間， 再利用上述周期性循環(huán)方案給各機子 分配區(qū)間 ， 則第 i 臺機子的求根區(qū)間為[ a j ， 6 ， ] ， J=0 ， 1 ， ? ， k—I ， 其 中口

16、 ， =[ ( 6 6一 a a ) ／ ( k× P ) ] ( J × P+)+a a ， 6 ， =[ ( 6 6 一。 口 ) ／ (× P ) ] ( 口 ， × P十i 十 1 )十a(chǎn) a ， 每臺處理機在得到 后 個小區(qū)間后 ， 各 自并行計算 所 得 k 個 區(qū)間 上的特 征值．( 3 )每臺處理機計算時， 用新序列構(gòu)造中處理后的 S t u r m法將根隔離在獨立的小區(qū)間中．(