金沙娱乐场官方网-澳门金沙会官网-金沙集团股价实情信息最新

（1）面向非線(xiàn)性電路仿真的譜圖稀疏化算法

圖1：利用譜圖稀疏化為非線(xiàn)性電路生成預(yù)條件子的SOTA方法GPSCP與我們提出方法CSP的對(duì)比示意圖

如圖1所示，現(xiàn)有利用譜圖稀疏化來(lái)處理非線(xiàn)性電路矩陣的方法，在處理非對(duì)稱(chēng)矩陣時(shí)，會(huì)去除非對(duì)稱(chēng)邊，得到一個(gè)完全由線(xiàn)性元器件構(gòu)成的對(duì)稱(chēng)矩陣，進(jìn)而使用譜圖稀疏化算法處理對(duì)稱(chēng)矩陣。在得到預(yù)條件子之后再將非對(duì)稱(chēng)邊（即非線(xiàn)性元器件部分的元素）恢復(fù)到矩陣中。上述的方法中存在一些問(wèn)題，首先是對(duì)于存在大量非對(duì)稱(chēng)邊的矩陣（即非線(xiàn)性器件較多的電路），得到的預(yù)條件子的稠密度會(huì)大大增加，導(dǎo)致迭代求解時(shí)間開(kāi)銷(xiāo)的增加。其次是進(jìn)行譜圖稀疏化時(shí)忽略了非對(duì)稱(chēng)邊信息，影響預(yù)條件子的質(zhì)量。

（2）全面稀疏化預(yù)條件子算法

圖2：CSP方法的流程展示

與現(xiàn)有工作不同，CSP的核心思想是在非線(xiàn)性元器件線(xiàn)性化后，將非對(duì)稱(chēng)邊對(duì)稱(chēng)化，進(jìn)而得到包含所有元器件的對(duì)稱(chēng)圖，對(duì)其進(jìn)行譜圖稀疏化。之后，將得到的稀疏子圖與原始MNA矩陣進(jìn)行相交的“與”操作，僅保留原始圖中的非對(duì)稱(chēng)邊，去掉人為引入的非對(duì)稱(chēng)邊，進(jìn)一步降低預(yù)條件子的稀疏度。

• 大邊對(duì)稱(chēng)策略
  

      基于原始矩陣、對(duì)稱(chēng)化后的矩陣和稀疏化后的矩陣，通過(guò)推導(dǎo)得到如下公式：

其中代表了兩個(gè)矩陣間的相對(duì)條件數(shù)，該結(jié)果表明預(yù)條件子不僅減少了的相對(duì)條件數(shù)，還有效的減少了的相對(duì)條件數(shù)，有利于迭代求解器減少迭代次數(shù)，減少求解時(shí)間開(kāi)銷(xiāo)。

基于以上推導(dǎo)的啟發(fā)，我們采用大邊對(duì)稱(chēng)的策略對(duì)原始矩陣進(jìn)行對(duì)稱(chēng)化。我們首先將邊的分布情況分為了完全對(duì)稱(chēng)、值不對(duì)稱(chēng)和位置不對(duì)稱(chēng)等三類(lèi)，之后使用較大權(quán)重的邊更新其對(duì)稱(chēng)位置的權(quán)重，從而對(duì)原始矩陣實(shí)現(xiàn)了對(duì)稱(chēng)化，得到對(duì)稱(chēng)矩陣。

• 非對(duì)稱(chēng)矩陣的譜稀疏化

為了生成質(zhì)量更高的預(yù)條件子，我們?cè)谙∈杌瘯r(shí)應(yīng)該更多考慮非對(duì)稱(chēng)邊的信息，因此我們?cè)诙x有效權(quán)重時(shí)，充分利用了非對(duì)稱(chēng)邊的權(quán)重等信息，有效權(quán)重定義如下：

在該部分我們利用原始矩陣非對(duì)稱(chēng)邊的權(quán)重（節(jié)點(diǎn)體積），和對(duì)稱(chēng)矩陣的節(jié)點(diǎn)間距離等信息，綜合考慮邊在非對(duì)稱(chēng)矩陣和對(duì)稱(chēng)矩陣中的重要性。

•  “與”操作獲得預(yù)條件子

通過(guò)對(duì)非對(duì)稱(chēng)邊和對(duì)稱(chēng)邊的綜合考慮得到稀疏子圖后，我們通過(guò)“與”操作將稀疏子圖和原始圖進(jìn)行合并處理，因此，我們得到的預(yù)條件子的稀疏度會(huì)進(jìn)一步降低，并且可以進(jìn)一步保留原始圖中的非對(duì)稱(chēng)邊信息。

（3）并行譜圖稀疏化算法

圖3：并行譜圖稀疏化算法示意圖

• 塊范圍最大查詢(xún)算法

在譜圖稀疏化算法中，在構(gòu)建生成樹(shù)后，為了進(jìn)一步降低相對(duì)條件數(shù)，需要計(jì)算所有樹(shù)外邊的有效電阻，并依據(jù)樹(shù)外邊的有效電阻和兩端節(jié)點(diǎn)恢復(fù)一定數(shù)量的邊到生成樹(shù)中。在這個(gè)過(guò)程中計(jì)算有效電阻我們需要獲得樹(shù)外邊兩端節(jié)點(diǎn)的最近公共祖先，然而，傳統(tǒng)的求取最近公共祖先的算法難以并行化。如圖3（a）所示，本文提出了一種有效的策略，將LCA問(wèn)題轉(zhuǎn)化為歐拉序上的范圍最大查詢(xún)問(wèn)題。并通過(guò)對(duì)數(shù)據(jù)塊劃分，我們可以對(duì)每個(gè)塊進(jìn)行并行操作，從而保持它們之間的最大間隔。

• 點(diǎn)獨(dú)占算法

      當(dāng)考慮添加樹(shù)外邊時(shí)，我們需要標(biāo)記生成樹(shù)上樹(shù)其他樹(shù)外邊。然而，在新添加的邊和其他非樹(shù)邊之間建立連接會(huì)帶來(lái)挑戰(zhàn)。在本文中，為了提高效率，我們創(chuàng)建了一個(gè)以節(jié)點(diǎn)和為起點(diǎn)的互斥區(qū)域，作用于邊，這樣就可以跳過(guò)具有由同一邊標(biāo)記的互斥端點(diǎn)的離樹(shù)外部，如圖3（b）所示。最后，為了減少內(nèi)存和時(shí)間開(kāi)銷(xiāo)，我們將LCA作為一個(gè)集合對(duì)邊進(jìn)行分組。

（1）預(yù)條件子質(zhì)量對(duì)比

表1：CSP、feGRASS、GPSCP等方法預(yù)條件子和迭代次數(shù)對(duì)比

在實(shí)驗(yàn)中，為了展現(xiàn)我們CSP算法生成的預(yù)條件子質(zhì)量，我們與feGRASS、GPSCP等方法進(jìn)行了對(duì)比，并分別與廣義最小殘差法結(jié)合，統(tǒng)計(jì)迭代法解法器的迭代次數(shù)。實(shí)驗(yàn)表明，CSP算法可以生成相比f(wàn)eGRASS、GPSCP更稀疏的預(yù)條件子，同時(shí)相對(duì)條件數(shù)和迭代次數(shù)也更加優(yōu)秀，證明了我們CSP算法的有效性。

（2）CSP算法加速矩陣求解的有效性

圖4：（a）CSP算法相對(duì)SOTA方法加速比；（b）預(yù)條件迭代求解相對(duì)KLU求解加速比

我們對(duì)不同大小和非對(duì)稱(chēng)邊占比的矩陣進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果表明與最先進(jìn)的GPSCP、feGRASS等譜圖稀疏化算法生成的預(yù)條件子+GMRES迭代法解法器，以及直接法解法器KLU相比，使用CSP算法求解非線(xiàn)性電路矩陣時(shí)，串行平均加速比分別為2.50x、13.46x、2.18x。

（3）譜圖稀疏化算法并行效率和求解器內(nèi)存占用對(duì)比

圖4：（a）不同線(xiàn)程下并行效率          （b）不同方法的內(nèi)存開(kāi)銷(xiāo)

由圖可知，我們的并行策略實(shí)現(xiàn)了平均2.99倍的加速，并且由于我們生成的預(yù)條件子更加稀疏，CSP方法在求解時(shí)占用的內(nèi)存消耗最低，且顯著低于直接法解法器的內(nèi)存開(kāi)銷(xiāo)。