若干大型稀疏非線性矩陣方程的數值解法基本信息

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

在科學與工程領域中進行數值計算時經常需要處理大型的稀疏矩陣，這些矩陣的特征一是階數很大，二是含有大量的零元，使得無法使用傳統(tǒng)的稠密矩陣存儲方案和算法。由于矩陣階數太大，若存儲整個矩陣，將會占用大量的存儲空間，甚至會超出計算系統(tǒng)的存儲容量，因此需要設計專門的稀疏存儲方案，盡可能的減少零元素的存儲。

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

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

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

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

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

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

通用處理器與算法加速器協同計算策略

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

面向稀疏結構特征的數據結構和算法映射

不同應用領域的稀疏矩陣往往具有不同的稀疏結構特征，這些特征因問題而異；具有不同稀疏結構特征的稀疏矩陣往往對應不同的最優(yōu)存儲方案以及不同的并行算法實現。在計算過程中，對于稀疏矩陣算法的不同計算階段，會因稀疏結構導致的計算特征的不同而適合在通用處理器或算法加速器上運行或是由二者協同計算。因此，研究矩陣的稀疏結構并設計相應的數據結構和算法映射策略，能夠有效提高算法對于不同矩陣和不同計算平臺的適應性。 2100433B