武瑞嬋,鄧華麗

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

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

武瑞嬋,鄧華麗

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 導(dǎo)入界面

圖2 單線程求解界面

圖3 雙線程求解界面

圖4 四線程求解界面

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

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

圖5 輸入新的方程組界面

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

3 效率分析

以一個(gè)40階的系數(shù)矩陣為例如表1～2，通過(guò)該計(jì)算器來(lái)研究多線程并行計(jì)算的時(shí)間：

表1 某次計(jì)算時(shí)間

表2 多次平均計(jì)算時(shí)間

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

4 小結(jié)

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

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

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

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

[4]劉盎然.線性方程組的迭代和最速下降法[J].赤峰學(xué)院學(xué)報(bào)(自然科學(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è)計(jì)方法研究[D].鄭州：中原工學(xué)院,2014.

[8]馮佩,鐘誠(chéng),韋偉.多核多線程并行求解線性方程組[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(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é)任編輯 高?！?/p>

2016-11-15

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

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