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

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

如圖1所示，現有利用譜圖稀疏化來處理非線性電路矩陣的方法，在處理非對稱矩陣時，會去除非對稱邊，得到一個完全由線性元器件構成的對稱矩陣，進而使用譜圖稀疏化算法處理對稱矩陣。在得到預條件子之后再將非對稱邊（即非線性元器件部分的元素）恢復到矩陣中。上述的方法中存在一些問題，首先是對于存在大量非對稱邊的矩陣（即非線性器件較多的電路），得到的預條件子的稠密度會大大增加，導致迭代求解時間開銷的增加。其次是進行譜圖稀疏化時忽略了非對稱邊信息，影響預條件子的質量。

（2）全面稀疏化預條件子算法

圖2：CSP方法的流程展示

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

• 大邊對稱策略
  

      基于原始矩陣、對稱化后的矩陣和稀疏化后的矩陣，通過推導得到如下公式：

其中代表了兩個矩陣間的相對條件數，該結果表明預條件子不僅減少了的相對條件數，還有效的減少了的相對條件數，有利于迭代求解器減少迭代次數，減少求解時間開銷。

基于以上推導的啟發，我們采用大邊對稱的策略對原始矩陣進行對稱化。我們首先將邊的分布情況分為了完全對稱、值不對稱和位置不對稱等三類，之后使用較大權重的邊更新其對稱位置的權重，從而對原始矩陣實現了對稱化，得到對稱矩陣。

• 非對稱矩陣的譜稀疏化

為了生成質量更高的預條件子，我們在稀疏化時應該更多考慮非對稱邊的信息，因此我們在定義有效權重時，充分利用了非對稱邊的權重等信息，有效權重定義如下：

在該部分我們利用原始矩陣非對稱邊的權重（節點體積），和對稱矩陣的節點間距離等信息，綜合考慮邊在非對稱矩陣和對稱矩陣中的重要性。

•  “與”操作獲得預條件子

通過對非對稱邊和對稱邊的綜合考慮得到稀疏子圖后，我們通過“與”操作將稀疏子圖和原始圖進行合并處理，因此，我們得到的預條件子的稀疏度會進一步降低，并且可以進一步保留原始圖中的非對稱邊信息。

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

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

• 塊范圍最大查詢算法

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

• 點獨占算法

      當考慮添加樹外邊時，我們需要標記生成樹上樹其他樹外邊。然而，在新添加的邊和其他非樹邊之間建立連接會帶來挑戰。在本文中，為了提高效率，我們創建了一個以節點和為起點的互斥區域，作用于邊，這樣就可以跳過具有由同一邊標記的互斥端點的離樹外部，如圖3（b）所示。最后，為了減少內存和時間開銷，我們將LCA作為一個集合對邊進行分組。

（1）預條件子質量對比

表1：CSP、feGRASS、GPSCP等方法預條件子和迭代次數對比

在實驗中，為了展現我們CSP算法生成的預條件子質量，我們與feGRASS、GPSCP等方法進行了對比，并分別與廣義最小殘差法結合，統計迭代法解法器的迭代次數。實驗表明，CSP算法可以生成相比feGRASS、GPSCP更稀疏的預條件子，同時相對條件數和迭代次數也更加優秀，證明了我們CSP算法的有效性。

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

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

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

（3）譜圖稀疏化算法并行效率和求解器內存占用對比

圖4：（a）不同線程下并行效率          （b）不同方法的內存開銷

由圖可知，我們的并行策略實現了平均2.99倍的加速，并且由于我們生成的預條件子更加稀疏，CSP方法在求解時占用的內存消耗最低，且顯著低于直接法解法器的內存開銷。