基于Java多線程的預(yù)處理迭代并行求解器

武瑞嬋,鄧華麗

（湖北文理學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院，湖北襄陽 441053）

基于Java多線程的預(yù)處理迭代并行求解器

武瑞嬋,鄧華麗

（湖北文理學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院，湖北襄陽 441053）

預(yù)處理技術(shù)在改善系數(shù)矩陣條件數(shù)和保證收斂的問題上起到了舉足輕重的作用。文中將Java多線程技術(shù)與SSOR-PCG算法相結(jié)合，設(shè)計并實現(xiàn)了一個可交互的并行求解器，為用戶的求解過程提供了許多便利。通過算例表明，二者的有機結(jié)合可以有效地提高運算效率，同時也可看出運算速度與線程數(shù)量并不成正比。

Java多線程；預(yù)處理技術(shù)；并行計算

對實際問題的數(shù)值模擬常常歸結(jié)為稀疏線性方程組的求解問題，如何提高計算效率一直是這些領(lǐng)域的研究熱點，求解的方法也是層出不窮。隨著云平臺的興起，并行求解又引發(fā)了新一輪的研究熱潮[1]，研究成果不斷有新的進(jìn)展，應(yīng)用的領(lǐng)域也越來越廣泛[2]。在迄今為止眾多的迭代方法中，超松弛迭代（SSOR）[3]可以通過對參數(shù)的調(diào)整來改善矩陣的病態(tài)特性，預(yù)處理共軛梯度法[4]（PCG）在解決對稱正定大型稀疏矩陣的問題上不僅具有良好的精度和穩(wěn)定性，而且還可以使系數(shù)矩陣A的特征值分布密集，保證較快的收斂速度。SSOR-PCG算法在文獻(xiàn)[5-6]中分別從不同角度對這一理論進(jìn)行了全方位的論證，衛(wèi)加寧[3]等還進(jìn)一步論證了SSOR參數(shù)的取值范圍。

預(yù)處理技術(shù)可以改變收斂性，也可以在一定程度上提高運算效率，但若能與多線程并行計算技術(shù)進(jìn)行完美融合，將會使運算效率得到進(jìn)一步提升。本文將SSOR-PCG算法與Java多線程技術(shù)相結(jié)合設(shè)計和實現(xiàn)了一款并行求解器。計算過程也對串行計算和并行計算的效率進(jìn)行了詳細(xì)比較，并使用可視化界面技術(shù)將這種計算過程直觀化，用戶可以通過并行求解器對大型稀疏方程組進(jìn)行更為方便、有效地求解，極大地方便了用戶。最后文章還借鑒了多核環(huán)境下的多線程思想[7-8]，旨在尋求更為合適的并行求解模式。

1 并行求解器設(shè)計原理

其中D=diag(a11,a22,…,ann)，為系數(shù)矩陣A的主對角線元；CL為嚴(yán)格下三角矩陣，它的元素是由A相應(yīng)部分元素取負(fù)號以后構(gòu)成的。

任取初始向量 x0，則計算得 r0=b-Ax0，z0=M-1r0，p0=z0，對于 k=0,1,…,計算：

2 并行求解器的實現(xiàn)

主要技術(shù)：Jsp+css+Sqlserver2005,開發(fā)工具：MyEclipse+SQL Server 2005。

求解器所具備的主要功能：導(dǎo)入、輸入和隨機生成方程組，運用單、多線程來進(jìn)行計算。

當(dāng)用戶選擇“導(dǎo)入已有方程組”并點擊時，系統(tǒng)會顯示后臺數(shù)據(jù)庫中所存放的所有矩陣信息，包括它的階數(shù)，如圖1所示。用戶可以任意選擇待計算的方程組，將系數(shù)矩陣的名稱填入框內(nèi)并點擊相應(yīng)計算按鈕即可跳轉(zhuǎn)至計算結(jié)果界面。界面中詳細(xì)說明了所計算的矩陣及矩陣的階數(shù)、計算結(jié)果、計算方式、計算時間等，用戶操作簡便，結(jié)果清晰明了。

若數(shù)據(jù)庫中沒有儲存所需計算的系數(shù)矩陣，用戶則可以點擊以上任一界面中的“輸入新的方程組”向數(shù)據(jù)庫中添加信息，如圖2～4所示。鑒于大型稀疏線性方程組系數(shù)矩陣零元素較多的特點，為方便用戶輸入，計算器在輸入新的矩陣時可以忽略零元素，只輸入非零元即可。

圖1 導(dǎo)入界面

圖2 單線程求解界面

圖3 雙線程求解界面

圖4 四線程求解界面

數(shù)據(jù)輸入完成后，用戶可以點擊“只存儲數(shù)據(jù)”或“存儲并計算”按鈕進(jìn)行相應(yīng)的操作。若點擊“存儲并計算”則會得到如圖5類似結(jié)果。該界面所設(shè)計的默認(rèn)計算是單線程計算，若用戶需要計算其它線程的結(jié)果，同樣可以選擇不同的按鈕進(jìn)行計算。

為滿足某些理論研究需要，求解器還提供了“隨機生成系數(shù)矩陣”的功能，如圖6。用戶只需要輸入所求矩陣的階數(shù)即可獲得一個隨機矩陣，以它作為系數(shù)矩陣也可以點擊數(shù)據(jù)存儲或存儲并計算按鈕，其計算過程類似于求解器的前兩個功能，這里不再贅述。

圖5 輸入新的方程組界面

圖6 隨機生成系數(shù)矩陣界面

3 效率分析

以一個40階的系數(shù)矩陣為例如表1～2，通過該計算器來研究多線程并行計算的時間：

表1 某次計算時間

表2 多次平均計算時間

從表1～2可以看出，由于多線程的特性是各線程在排隊等待享用CPU資源，因而每次計算順序和計算時間都不確定。而隨著線程分配數(shù)目的增多，計算用的時間相應(yīng)減少，這也說明了利用多線程并行求解確實可以提高運算效率。但是，從無論從單線程到雙線程，還是從雙線程到四線程，計算時間都不是直接減半。尤其是從雙線程到四線程，這種情況體現(xiàn)得尤為明顯，這也說明了線程的數(shù)量與運算效率并不成比例。

4 小結(jié)

在大型稀疏線性方程組的求解中，為了克服系數(shù)矩陣病態(tài)特性，保證求解過程中的數(shù)值穩(wěn)定性及高效性，本文運用SSOR-PCG算法與Java多線程技術(shù)相結(jié)合來模擬并行計算，完成了一個求解大型稀疏線性方程組的并行求解器的設(shè)計。通過實例計算可知，基于多線程技術(shù)的并行計算確實可以提高運算效率，但線程數(shù)量與運算效率并不成正比。不足的是，大型稀疏矩陣的多樣化決定了本文研究的片面性，本文并沒有找到一個適合所有大型稀疏線性方程組求解的方法。而且并行算法的設(shè)計模式也具有多樣性，同樣值得深入研究。

[1]劉師范.并行計算方法研究與應(yīng)用[J].數(shù)字技術(shù)與應(yīng)用,2014(1)：109-110.

[2]張冬姣,孟慶偉,王萍.基于Java多線程的并行計算技術(shù)研究及應(yīng)用[J].科學(xué)中國人,2014（10）：15-16.

[3]衛(wèi)加寧,武瑞嬋.預(yù)處理迭代的性質(zhì)及其應(yīng)用[J].武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版),2006,30(4)：646-648.

[4]劉盎然.線性方程組的迭代和最速下降法[J].赤峰學(xué)院學(xué)報(自然科學(xué)版),2014(2)：10-13.

[5]薛秋芳.解線性方程組的幾種迭代法的收斂性分析[D].西安：陜西師范大學(xué),2014.

[6]KURDI YEl,GROSS W J,GIANNACOPOULOS D，et al.Parallel Multigrid Acceleration for the Finite-Element Gaussian Belief Propagation Algorithm[J].IEEE Transactions on Magnetics,2014,50(2)：7014304-1-7014304-4.

[7]王晗.基于多核環(huán)境下的多線程并行程序設(shè)計方法研究[D].鄭州：中原工學(xué)院,2014.

[8]馮佩,鐘誠,韋偉.多核多線程并行求解線性方程組[J].合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2011(2)：237-240.

Parallel Solver about the Preconditioned Iterative Based on the Java Multithread

WU Rui-chan,DENG Hua-li
(School of Mathematical and Computer Sciences,Hubei University of Arts and Science,Xiangyang Hubei,441053)

The pretreatment technology is very important to improve the condition number of coefficient matrix and ensure its convergence problem.In this paper,an interactive parallel solver is designed;it will offer many convenient for the user.The technology of this solver is Java multi-thread and SSOR pretreatment iterative.Numerical example shows that the efficiency of operation can be improved effectively by using these technologies,but the computing speed is not proportional to the number of threads.

java multithread;preconditioned;parallel computing

O245

A

1674-0874(2017)02-0009-03

〔責(zé)任編輯 高海〕

2016-11-15

國家自然科學(xué)青年基金資助項目[71501064]

武瑞嬋（1978-），女，山西昔陽人，碩士，講師，研究方向：計算數(shù)學(xué)。