若干大型稀疏非線性矩陣方程的數(shù)值解法

隨著現(xiàn)代科學(xué)技術(shù)的迅速發(fā)展，非線性矩陣方程越來(lái)越多地出現(xiàn)在許多科學(xué)與工程計(jì)算領(lǐng)域，如海洋物理，控制論以及噪音污染，交通運(yùn)輸?shù)群芏鄦?wèn)題的解決最終往往歸結(jié)為一個(gè)非線性矩陣方程。因此，研究非線性矩陣方程的解的存在性，敏感性以及如何求解是非常有意義的。特別地，對(duì)于如何有效、快速、準(zhǔn)確的求出它們的解更是人們所關(guān)注的。非線性矩陣方程的數(shù)值求解已成為科學(xué)研究的熱點(diǎn)之一。為使所設(shè)計(jì)的算法更具有效性和可執(zhí)行性，我們希望算法適合在并行環(huán)境下運(yùn)行，這就需要算法中的公式運(yùn)算要基本，同時(shí)，要盡量使算法收斂速度快，計(jì)算量少，數(shù)值穩(wěn)定。尋求滿足上述條件的求解大型稀疏非線性矩陣方程的算法是我們將要研究的主要問(wèn)題。對(duì)該問(wèn)題的研究，將有利于其它相關(guān)學(xué)科的發(fā)展，也將促進(jìn)計(jì)算機(jī)實(shí)用軟件的開(kāi)發(fā)。 2100433B

在科學(xué)與工程領(lǐng)域中進(jìn)行數(shù)值計(jì)算時(shí)經(jīng)常需要處理大型的稀疏矩陣，這些矩陣的特征一是階數(shù)很大，二是含有大量的零元，使得無(wú)法使用傳統(tǒng)的稠密矩陣存儲(chǔ)方案和算法。由于矩陣階數(shù)太大，若存儲(chǔ)整個(gè)矩陣，將會(huì)占用大量的存儲(chǔ)空間，甚至?xí)鲇?jì)算系統(tǒng)的存儲(chǔ)容量，因此需要設(shè)計(jì)專門的稀疏存儲(chǔ)方案，盡可能的減少零元素的存儲(chǔ)。

稀疏矩陣算法是以稀疏矩陣作為核心數(shù)據(jù)結(jié)構(gòu)的算法。與稠密矩陣算法相比，稀疏矩陣算法的最大特點(diǎn)是通過(guò)只存儲(chǔ)和處理非零元素從而大幅度降低存儲(chǔ)空間需求以及計(jì)算復(fù)雜度，代價(jià)則是必須使用專門的稀疏矩陣壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)，因而在計(jì)算過(guò)程中引入了大量的離散間接尋址操作。稀疏矩陣算法是典型的不規(guī)則算法，計(jì)算訪存比很低，并且計(jì)算過(guò)程中的訪存軌跡與稀疏矩陣的稀疏結(jié)構(gòu)相關(guān)，很難發(fā)掘計(jì)算過(guò)程中的時(shí)空局部性，因此在傳統(tǒng)的基于Cache的處理器上稀疏矩陣算法的計(jì)算效率很低。為了提高稀疏矩陣算法的計(jì)算效率，需要從稀疏存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)和稀疏矩陣算法兩方面對(duì)現(xiàn)有算法進(jìn)行改進(jìn)。

按照應(yīng)用領(lǐng)域的不同，稀疏矩陣算法分為兩類，一類是非數(shù)值計(jì)算算法，典型代表是圖搜索算法，包括寬度優(yōu)先搜索等核心算法；另一類則是數(shù)值計(jì)算算法，典型代表是稀疏線性方程組求解，包括稀疏矩陣向量乘、稀疏三角方程組求解以及稀疏矩陣分解等核心算法。

本教材根據(jù)（全日制、在職）工程碩士研究生的特點(diǎn)和培養(yǎng)創(chuàng)新型人才的要求，將矩陣論與數(shù)值分析的有關(guān)理論與方法按內(nèi)容體系編寫.全書共6章，分別是矩陣運(yùn)算與矩陣分解、線性空間與線性變換、矩陣的若爾當(dāng)標(biāo)準(zhǔn)形與矩陣函數(shù)、方程與方程組的數(shù)值解法、數(shù)值逼近方法與數(shù)值微積分、常微分方程的數(shù)值解法.為提高工程碩士研究生應(yīng)用數(shù)學(xué)方法和科學(xué)計(jì)算解決實(shí)際問(wèn)題的能力，各章最后一節(jié)給出了一些應(yīng)用案例，對(duì)一些重要的問(wèn)題給出了求解問(wèn)題的MATLAB程序.

本書可供工程碩士研究生以及理工科非計(jì)算數(shù)學(xué)專業(yè)的大學(xué)生閱讀，也可供科技工作者參考.

面向算法加速器的稀疏矩陣算法并行化方法

由于算法加速器采用了與通用處理器完全不同的體系結(jié)構(gòu)和編程模型，因此需要專門設(shè)計(jì)針對(duì)算法加速器的并行程序。與通用處理器相比，算法加速器能夠運(yùn)行更多的線程，因此一方面需要將計(jì)算任務(wù)劃分為更多的子任務(wù)，實(shí)現(xiàn)細(xì)粒度并行；另一方面需要考慮線程間的負(fù)載均衡和數(shù)據(jù)局部性，特別是線程間的通信和同步開(kāi)銷。與通用處理器相比，算法加速器更容易受到不規(guī)則訪存和計(jì)算的影響，因此必須通過(guò)矩陣預(yù)處理等手段提高計(jì)算的規(guī)則性和數(shù)據(jù)的局部性。

通用處理器與算法加速器協(xié)同計(jì)算策略

異構(gòu)體系結(jié)構(gòu)的計(jì)算單元包括通用處理器和算法加速器兩部分。在學(xué)術(shù)研究中通常分別針對(duì)這兩種計(jì)算單元設(shè)計(jì)并行算法，但在實(shí)際應(yīng)用中，需要同時(shí)利用計(jì)算系統(tǒng)的所有計(jì)算資源以獲取最高性能。然而，現(xiàn)有的針對(duì)通用處理器和算法加速器的并行算法分別采用了不同的編程模型和優(yōu)化策略，無(wú)法直接互相遷移，并且在協(xié)同計(jì)算過(guò)程中，不但需要在兩個(gè)平臺(tái)上都能高效運(yùn)行的并行程序，而且需要實(shí)現(xiàn)通信與計(jì)算的重疊以隱藏?cái)?shù)據(jù)傳輸?shù)拈_(kāi)銷，這些都要求對(duì)現(xiàn)有的算法針對(duì)異構(gòu)平臺(tái)進(jìn)行重新設(shè)計(jì)。

面向稀疏結(jié)構(gòu)特征的數(shù)據(jù)結(jié)構(gòu)和算法映射

不同應(yīng)用領(lǐng)域的稀疏矩陣往往具有不同的稀疏結(jié)構(gòu)特征，這些特征因問(wèn)題而異；具有不同稀疏結(jié)構(gòu)特征的稀疏矩陣往往對(duì)應(yīng)不同的最優(yōu)存儲(chǔ)方案以及不同的并行算法實(shí)現(xiàn)。在計(jì)算過(guò)程中，對(duì)于稀疏矩陣算法的不同計(jì)算階段，會(huì)因稀疏結(jié)構(gòu)導(dǎo)致的計(jì)算特征的不同而適合在通用處理器或算法加速器上運(yùn)行或是由二者協(xié)同計(jì)算。因此，研究矩陣的稀疏結(jié)構(gòu)并設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法映射策略，能夠有效提高算法對(duì)于不同矩陣和不同計(jì)算平臺(tái)的適應(yīng)性。 2100433B