并行符號(hào)算法若干問題的研究與應(yīng)用.pdf

1、符號(hào)計(jì)算是數(shù)學(xué)和計(jì)算機(jī)領(lǐng)域融合產(chǎn)生的一個(gè)新的交叉學(xué)科,主要利用計(jì)算機(jī)嚴(yán)格處理準(zhǔn)確的數(shù)學(xué)運(yùn)算,沒有舍入誤差,因此在許多領(lǐng)域有著非常重要的應(yīng)用。由于準(zhǔn)確計(jì)算需要耗費(fèi)大量內(nèi)存和CPU運(yùn)算的緣故,符號(hào)計(jì)算關(guān)于復(fù)雜問題的計(jì)算效率一直不能滿足實(shí)用要求,主要表現(xiàn)為計(jì)算速度慢和中間表達(dá)式膨脹兩個(gè)問題,嚴(yán)重阻礙問題的求解。另一方面,隨著計(jì)算機(jī)軟硬件普及和技術(shù)水平的日益提升,并行計(jì)算已經(jīng)成為高性能計(jì)算的核心力量。利用集群計(jì)算機(jī)中多個(gè)處理器協(xié)同工作的計(jì)算優(yōu)勢(shì)

2、,并行計(jì)算不僅可以大幅度加快問題的求解速度,而且可以平衡計(jì)算過程中內(nèi)存負(fù)載。因此,如何將并行計(jì)算引入到符號(hào)計(jì)算過程中,既能發(fā)揮并行計(jì)算的優(yōu)勢(shì),又能推廣符號(hào)計(jì)算的應(yīng)用領(lǐng)域,這是目前在符號(hào)計(jì)算和高性能計(jì)算領(lǐng)域里的一個(gè)非常重要的問題。 本文立足于并行計(jì)算和符號(hào)計(jì)算的基礎(chǔ)上,主要討論符號(hào)計(jì)算中若干個(gè)問題以及并行化解決方法的研究。本文主要的工作包含以下五點(diǎn)： (1).多項(xiàng)式矩陣行列式展開是符號(hào)計(jì)算中一個(gè)很基礎(chǔ)的數(shù)學(xué)運(yùn)算。我們討論了

3、將多項(xiàng)式行列式展開轉(zhuǎn)化為多項(xiàng)式插值的方法。利用多項(xiàng)式插值的思想,將繁雜的行列式展開問題,轉(zhuǎn)化為大量的數(shù)值插值點(diǎn)計(jì)算和解線性方程組兩個(gè)步驟。由于計(jì)算量很大,特將并行計(jì)算引入整個(gè)計(jì)算過程。首先在插值點(diǎn)計(jì)算上,由于需要計(jì)算的插值點(diǎn)很多,可以在多個(gè)處理器上并行計(jì)算插值點(diǎn),最后將所有的插值點(diǎn)匯總起來。并行計(jì)算采用粗粒度方式,每個(gè)處理器獨(dú)立計(jì)算自己的插值點(diǎn),只需要很少的消息傳遞。在線性方程組求解上,擴(kuò)展了兩個(gè)變?cè)腂jorck-Pereyra方法,

4、并且將計(jì)算中重點(diǎn)運(yùn)算部份分配到多個(gè)節(jié)點(diǎn)同時(shí)進(jìn)行。將原有的文獻(xiàn)[135]的Bjorck-Pereyra方法的復(fù)雜程度下降到O(rn+1/nc)。通過計(jì)算機(jī)代數(shù)系統(tǒng)MAPLE程序語言實(shí)現(xiàn)了以上并行行列式展開方法,并對(duì)若干個(gè)實(shí)際例子進(jìn)行驗(yàn)證,結(jié)果是非常有效的。并行計(jì)算不僅加快插值點(diǎn)的求值計(jì)算,而且平衡了單個(gè)機(jī)器過高的內(nèi)存負(fù)載,有效克服了中間表達(dá)式膨脹的問題。 (2).不等式的證明一直是個(gè)比較困難的問題。我們討論了差分代換方法。差分代換

5、方法使用起來非常簡單,但是卻能夠非常有效證明許多不平凡的不等式。對(duì)于某些次數(shù)較高或者變?cè)^多的不等式,其它不等式證明的方法幾乎都無法求解,而差分代換卻能夠化繁為簡,利用簡單多項(xiàng)式合并和化簡步驟就可以證明不等式。而且整個(gè)證明過程是可讀的,容易被讀者理解和驗(yàn)證。在連續(xù)差分代換方法的基礎(chǔ)上,結(jié)合并行計(jì)算技術(shù),將差分代換所產(chǎn)生的大量分支不等式分散到多個(gè)計(jì)算節(jié)點(diǎn)上,每個(gè)節(jié)點(diǎn)獨(dú)立計(jì)算,并將結(jié)果匯總到一起,完成整個(gè)不等式的證明。通過若干個(gè)實(shí)際例子證明

6、了并行差分代換方法是非常有效的,不僅加快了計(jì)算求解速度,而且還能將計(jì)算過程中大多項(xiàng)式所引起的內(nèi)存消耗峰值平均分配到多個(gè)計(jì)算節(jié)點(diǎn)上,充分克服了符號(hào)計(jì)算中內(nèi)存瓶頸的問題,使得求解更加迅速,且延擴(kuò)了串行差分代換所證明的不等式范圍。 (3).差分代換方法的進(jìn)一步討論。我們討論了基于差分代換方法證明的不等式所組成的集合的拓?fù)浣Y(jié)構(gòu),證明了這個(gè)集合是一個(gè)有限生成錐,并且給出一個(gè)實(shí)用算法用來計(jì)算錐的端點(diǎn)。通過連續(xù)差分代換,可以對(duì)這個(gè)錐進(jìn)行了擴(kuò)展,使之能

7、夠證明更多的不等式。我們還比較差分代換和Schur分拆兩種不等式證明方法進(jìn)行比較,證明了能夠被Schur分拆證明的不等式同樣可以用差分代換方法來證明,這表明差分代換方法在不等式證明部分可以替代Schur分拆方法。 (4).Heilbronn七點(diǎn)問題。Heilbronn問題是離散組合幾何中一個(gè)經(jīng)典的問題,其中七點(diǎn)的Heilbronn問題到目前為止還沒有一個(gè)滿意的解決方法。我們給出了一個(gè)合理的解決方法。首先利用蒙特卡羅隨機(jī)搜索方法,

8、在單位正方形內(nèi)隨意放入七個(gè)點(diǎn)后,進(jìn)行最優(yōu)化搜索,利用Matlab自帶的非線性規(guī)劃求解得到的結(jié)果是目前為止最好的。雖然隨機(jī)搜索隨意性很大,但是經(jīng)過大量重復(fù)的取值后,在某種程度上彌補(bǔ)了結(jié)果的隨機(jī)性。這種隨機(jī)搜索的方法原理簡單,可以推廣到其它離散幾何問題。接著,利用數(shù)值計(jì)算和符號(hào)計(jì)算等工具證明這個(gè)結(jié)果是最優(yōu)的。根據(jù)H5,H6等已知結(jié)果,將H7分成兩個(gè)大類十五個(gè)小類分別進(jìn)行討論,將最終問題轉(zhuǎn)化為456427個(gè)非線性問題求解問題。利用數(shù)值計(jì)算軟件

9、Matlab產(chǎn)生非線性問題的基本條件,然后結(jié)合符號(hào)計(jì)算中Gr(o)bner基、區(qū)間代數(shù)等多種方法,求出非線性問題的形式實(shí)解。由于非線性問題個(gè)數(shù)高達(dá)幾十萬個(gè),計(jì)算量很大,所以采用并行計(jì)算策略,在多個(gè)計(jì)算節(jié)點(diǎn)上并發(fā)計(jì)算,加快問題的求解。由于方程的次數(shù)較高,我們的最優(yōu)結(jié)果是以區(qū)間表示的形式實(shí)解。 (5).計(jì)算機(jī)代數(shù)軟件是符號(hào)計(jì)算的最重要的研究基礎(chǔ)。如何高效利用這些計(jì)算機(jī)代數(shù)軟件在集群計(jì)算機(jī)的基礎(chǔ)上協(xié)同工作提升符號(hào)計(jì)算效率,是一個(gè)非常重

10、要的問題。集群環(huán)境下計(jì)算機(jī)代數(shù)軟件協(xié)同工作需要兩個(gè)基礎(chǔ)：集群管理軟件和合適的數(shù)學(xué)表達(dá)式表示方法。首先討論了集群管理軟件SGE和并行消息通訊庫MPI,分析它們?cè)诓⑿杏?jì)算和任務(wù)管理調(diào)度方面的特性。然后描述了數(shù)學(xué)表達(dá)式在計(jì)算機(jī)中合理表示的多種方法,分析了它們相應(yīng)的優(yōu)缺點(diǎn)。最后在詳細(xì)分析異構(gòu)的計(jì)算機(jī)代數(shù)系統(tǒng)之間通訊調(diào)用機(jī)制的基礎(chǔ)上,提出了一種高性能計(jì)算機(jī)代數(shù)環(huán)境HHPCAS,綜合多種現(xiàn)有的多種計(jì)算機(jī)代數(shù)軟件,結(jié)合集群管理軟件和并行環(huán)境,可以提供