稀疏矩陣
關(guān)注創(chuàng)建者：寒江雪_123 創(chuàng)建時(shí)間：2022-09-23
稀疏矩陣的視頻教程
新一代強(qiáng)大的柔性多體動(dòng)力學(xué)仿真解決方案——ANSYS Motion
專門為剛性體和柔性體混合系統(tǒng)定制的稀疏矩陣求解器已得到驗(yàn)證，可以更好地處理大規(guī)模自由度系統(tǒng)仿真分析。 ANSYS Motion通過腳本、FMI可以與其他軟件集成交互，并提供了專門的Matlab接口。在機(jī)械系統(tǒng)的運(yùn)動(dòng)學(xué)分析、車輛動(dòng)力學(xué)、大變形結(jié)構(gòu)分析、高速大旋轉(zhuǎn)系統(tǒng)、3D接觸系統(tǒng)、以及多體運(yùn)動(dòng)、結(jié)構(gòu)變形、動(dòng)力學(xué)耐久性分析等應(yīng)用場景下，ANSYS Motion 都能夠提供卓越的解決方案。
免費(fèi) 1小時(shí)20分鐘 1617播放
查看
稀疏矩陣的實(shí)例教程
4.得到K稀疏矩陣后可通過spy(K)來進(jìn)行稀疏矩陣的結(jié)構(gòu)可視化，以及通過命令K_full=full(K)將稀疏矩陣轉(zhuǎn)換為完整（密集）矩陣。
在有限元求解中，最終通常要求解的是一個(gè)關(guān)于場變量的線性方程組，在常見的位移場有限元中，要求解的是各個(gè)節(jié)點(diǎn)的位移，該線性方程組的系數(shù)矩陣通常稱為剛度矩陣，方程組右邊通常稱為右端項(xiàng)或者荷載向量。一般情況下，由于網(wǎng)格劃分后并不是所有節(jié)點(diǎn)都兩兩連接，因此實(shí)際上最終形成的整體剛度矩陣中大部分元素為0，這種矩陣稱為稀疏矩陣。在有限元求解中，對(duì)于這種系數(shù)矩陣為稀疏矩陣的方程組，一種常見的方法是僅保存剛度矩陣的非0元素到內(nèi)存中，0元素不保存，這樣就可以以更小的內(nèi)存保存大型結(jié)構(gòu)的剛度矩陣。
那具體矩陣中有多少元素為0，就可以認(rèn)為其是稀疏矩陣呢？這個(gè)界限實(shí)際上比較模糊，有文獻(xiàn)給出如下定義：如果矩陣的A的非0元素?cái)?shù)量為O(n)，其中n是A的階數(shù)，則矩陣為稀疏矩陣。
稀疏矩陣經(jīng)常通過非0元素分布圖表示其稀疏性質(zhì)，以下是兩個(gè)常見的稀疏矩陣的分布圖：
在有限元分析中，非0元素的分布，實(shí)際上主要取決于單元的節(jié)點(diǎn)連接，以下圖中的單元連接為例：
假設(shè)圖中每個(gè)節(jié)點(diǎn)一個(gè)自由度，則整體剛度矩陣為16x16的矩陣，而具體非0元素的分布，可以通過單元連接得到鄰接點(diǎn)得到，所謂鄰接點(diǎn)，指的是相對(duì)于當(dāng)前單元位于同一單元內(nèi)的所有點(diǎn)的集合。以節(jié)點(diǎn)6為例，其鄰接點(diǎn)是1,2,3,5,7,9,10,11。
獲得上述鄰接點(diǎn)后，剛度矩陣中第6行的非0元素的位置實(shí)際上就確定了：k(6,1),k(6,2),k(6,3),k(6,5),k(6,6),k(6,7),k(6,9),k(6,10),k(6,11)。
在實(shí)際采用稀疏矩陣求解有限元問題時(shí)，獲得上述非0元素位置后，就可以對(duì)剛度矩陣采用稀疏矩陣存儲(chǔ)，常見的存儲(chǔ)方式有COO，CSR，CSC和DIA等。
展開 在有限元求解中，最終通常要求解的是一個(gè)關(guān)于場變量的線性方程組，在常見的位移場有限元中，要求解的是各個(gè)節(jié)點(diǎn)的位移，該線性方程組的系數(shù)矩陣通常稱為剛度矩陣，方程組右邊通常稱為右端項(xiàng)或者荷載向量。一般情況下，由于網(wǎng)格劃分后并不是所有節(jié)點(diǎn)都兩兩連接，因此實(shí)際上最終形成的整體剛度矩陣中大部分元素為0，這種矩陣稱為稀疏矩陣。在有限元求解中，對(duì)于這種系數(shù)矩陣為稀疏矩陣的方程組，一種常見的方法是僅保存剛度矩陣的非0元素到內(nèi)存中，0元素不保存，這樣就可以以更小的內(nèi)存保存大型結(jié)構(gòu)的剛度矩陣。
那具體矩陣中有多少元素為0，就可以認(rèn)為其是稀疏矩陣呢？這個(gè)界限實(shí)際上比較模糊，有文獻(xiàn)給出如下定義：如果矩陣的A的非0元素?cái)?shù)量為O(n)，其中n是A的階數(shù)，則矩陣為稀疏矩陣。
稀疏矩陣經(jīng)常通過非0元素分布圖表示其稀疏性質(zhì)，以下是兩個(gè)常見的稀疏矩陣的分布圖：
在有限元分析中，非0元素的分布，實(shí)際上主要取決于單元的節(jié)點(diǎn)連接，以下圖中的單元連接為例：
假設(shè)圖中每個(gè)節(jié)點(diǎn)一個(gè)自由度，則整體剛度矩陣為16x16的矩陣，而具體非0元素的分布，可以通過單元連接得到鄰接點(diǎn)得到，所謂鄰接點(diǎn)，指的是相對(duì)于當(dāng)前單元位于同一單元內(nèi)的所有點(diǎn)的集合。以節(jié)點(diǎn)6為例，其鄰接點(diǎn)是1,2,3,5,7,9,10,11。
獲得上述鄰接點(diǎn)后，剛度矩陣中第6行的非0元素的位置實(shí)際上就確定了：k(6,1),k(6,2),k(6,3),k(6,5),k(6,6),k(6,7),k(6,9),k(6,10),k(6,11)。
在實(shí)際采用稀疏矩陣求解有限元問題時(shí)，獲得上述非0元素位置后，就可以對(duì)剛度矩陣采用稀疏矩陣存儲(chǔ)，常見的存儲(chǔ)方式有COO，CSR，CSC和DIA等。
展開 以自由度數(shù)為41w的如下分布的稀疏矩陣為例，
該稀疏矩陣形成的系數(shù)方程組在matlab中采用直接求解為1.5s,采用一定預(yù)處理下的PCG求解時(shí)間為0.55s。
用筆者自行開發(fā)的稀疏矩陣PCG求解器運(yùn)行此算例，方程組求解時(shí)間為0.628s。
此時(shí)，整個(gè)程序的運(yùn)行時(shí)間瓶頸實(shí)際上并不在方程求解，而在于從文件中讀取稀疏矩陣對(duì)應(yīng)的數(shù)據(jù)。一般情況下采用fscanf讀取數(shù)據(jù)會(huì)快于用fstream讀取。改用fscanf讀取數(shù)據(jù)后，程序總運(yùn)行時(shí)間從原來的16s變?yōu)?s。
【完】
歡迎關(guān)注公眾號(hào) 有限元術(shù)
一個(gè)講有限元技術(shù)的公眾號(hào)
展開 PARDISO是一個(gè)商用的高速的稀疏矩陣線性方程組直接法求解器，其可以用于大型稀疏對(duì)稱或非對(duì)稱線性方程組的求解，商用版支持的并行方式包括共享內(nèi)存，分布式內(nèi)存和NVIDA的GPU并行。多次實(shí)踐已經(jīng)表明，PARDISO求解器具有優(yōu)秀的性能，在各種稀疏矩陣直接求解器的比較中通常處于第一梯隊(duì)，其他常見的直接法求解器包括SuiteSparse，MUMPS，SPOOLES等，商用有限元軟件COMSOL的官方文檔甚至直接指出在COMSOL中PARDISO求解速度快于MUMPS。。
對(duì)于線性方程組求解來說，一般常見的求解方法可分為直接法和迭代法。直接法常見的方法是高斯消去，LU分解法等，在求解過程中不需要迭代，但是在求解中可能需要較大內(nèi)存，商業(yè)軟件中經(jīng)常使用的一種直接法叫做多波前法。迭代法又可分為兩個(gè)大類，分裂迭代和Krylov迭代。前者通過將系數(shù)矩陣進(jìn)行拆分形成迭代列式，常見的是雅克比迭代，高斯賽德爾迭代等，分裂迭代這一類型的迭代法在商業(yè)軟件中很少直接使用，但是經(jīng)常作為Krylov迭代的預(yù)處理基礎(chǔ)；后者以Krylov子空間為基礎(chǔ)上，常見的包括共軛梯度法，廣義最小殘差法等，Krylov迭代法在商業(yè)軟件中較為常見。
在稀疏矩陣直接法求解中，一個(gè)常見的技術(shù)是矩陣重排，通過矩陣重排，可以使得矩陣的帶寬減小（即非0元素位置相對(duì)更趨近于對(duì)角線），從而使得直接求解效率更高，一種常見的矩陣重排方法是Cuthill_McKee，常見的可以實(shí)現(xiàn)矩陣重排的庫是METIS。以下是采用Cuthill_McKee重排前和重排后的非0元素分布。
重排前非0元素分布
重排后非0元素分布
商用版本的PARDISO個(gè)人一般較少直接使用（主要是要買）。實(shí)際中較為廣泛使用的其中一個(gè)版本是配置在MKL庫的PARDISO版本。
展開 
稀疏矩陣的相關(guān)專題、標(biāo)簽、搜索
稀疏矩陣的最新內(nèi)容
核心技術(shù)原理
基于拉格朗日方程與牛頓 - 歐拉方程，采用變步長剛性積分算法 + 稀疏矩陣技術(shù)，高效求解大規(guī)模非線性動(dòng)力學(xué)方程；支持剛?cè)狁詈稀⒎蔷€性接觸、摩擦、疲勞、振動(dòng)等多物理場耦合分析，兼顧計(jì)算精度與效率。
二、核心優(yōu)勢
1.
04/稀疏表示
為讓光源、掩模圖形更簡潔易制造，我們采用“稀疏表示”對(duì)其做參數(shù)變換：
?光源稀疏化：以單位矩陣為稀疏基，將光源轉(zhuǎn)換為對(duì)應(yīng)的光源稀疏系數(shù)；
?掩模稀疏化：先對(duì)掩模圖形做參數(shù)變換，再以2D-DCT（二維離散余弦變換）為稀疏基，得到掩模稀疏系數(shù)。
傳統(tǒng)僅依賴矩陣帶寬、稀疏度等淺層特征的方法無法充分捕捉復(fù)雜結(jié)構(gòu)關(guān)聯(lián)，而圖神經(jīng)網(wǎng)絡(luò)（GNN）正提供新途徑。GNN 可在任意尺寸、任意拓?fù)涞木仃噲D上工作，通過靈活的鄰域聚合將變長輸入映射為固定維度嵌入，從而刻畫出矩陣的深層拓?fù)淠Ｊ胶蛿?shù)值分布。
HSMO采用41×41光源矩陣（密集采點(diǎn)），OPC采用9×9光源矩陣（稀疏采點(diǎn)）。
03/掩模延拓和測量點(diǎn)
為量化工藝變化穩(wěn)定性，需計(jì)算初始光源掩模、OPC優(yōu)化后、HSMO優(yōu)化后的PW。
它通過稀疏矩陣自動(dòng)生成層次化的粗網(wǎng)格與限制/延拓算子，從而加速 Krylov 子空間迭代方法的收斂。
核心結(jié)論速覽表
仿真領(lǐng)域
核心算法/方法
計(jì)算特點(diǎn)
主要計(jì)算平臺(tái)
備注
結(jié)構(gòu)力學(xué)分析
隱式/顯式有限元法
隱式: 求解大型稀疏矩陣
核心結(jié)論速覽表
仿真領(lǐng)域核心算法/方法計(jì)算特點(diǎn)主要計(jì)算平臺(tái)備注飛行器氣動(dòng)設(shè)計(jì)
計(jì)算流體力學(xué) (CFD)
求解大型稀疏矩陣、高內(nèi)存帶寬、網(wǎng)格規(guī)模巨大
CPU多核 ≈ GPU
GPU加速已成主流，尤其在RANS和LES中。
4.得到K稀疏矩陣后可通過spy(K)來進(jìn)行稀疏矩陣的結(jié)構(gòu)可視化，以及通過命令K_full=full(K)將稀疏矩陣轉(zhuǎn)換為完整（密集）矩陣。
Wisim DC：重塑電源完整性分析新標(biāo)桿6個(gè)月前
基于三維全波電磁場有限元FEM理論，運(yùn)用2D/3D自適應(yīng)網(wǎng)格剖分技術(shù)和自動(dòng)對(duì)齊約簡技術(shù)，搭配大規(guī)模稀疏矩陣求解器和先進(jìn)的并行計(jì)算技術(shù)。使得Wisim DC可以仿真跨多個(gè)數(shù)量級(jí)的大尺度的多層版圖時(shí)表現(xiàn)出卓越的HPC仿真計(jì)算能力。
Wisim DC主界面
Wisim DC集成了最新的電源完整性分析技術(shù)和先進(jìn)的設(shè)計(jì)理念，旨在為設(shè)計(jì)工程師提供一個(gè)高效、準(zhǔn)確且易于上手的分析平臺(tái)。
稀疏矩陣向量乘：
用COO格式稀疏矩陣向量乘進(jìn)行測試。隨著矩陣元素維度變化，UNAT最高加速比和單核組Flops分別達(dá)到近27 倍和3.5 GFlops（0.46%理論性能）。與手工優(yōu)化的代碼相比，UNAT API實(shí)現(xiàn)了其大約70%的性能。考慮到兼容性和通用性帶來的額外開銷，其效果是相當(dāng)可觀的。
