[發明專利]一種基于電阻電容網絡的矩陣快速分解方法

有效

• 申請號: 202110619288.0
• 申請日: 2021-06-03
• 公開（公告）號: CN113255253B
• 公開（公告）日: 2022-05-24
• 發明（設計）人: 陳婧蕊;周振亞;吳大可;程明厚;劉強
• 申請（專利權）人: 北京華大九天科技股份有限公司
• 主分類號: G06F30/30
• 分類號: G06F30/30;G06F30/398;G06F115/12
• 代理公司: 北京德崇智捷知識產權代理有限公司 11467
• 代理人: 王金雙

一種基于電阻電容網絡的矩陣快速分解方法，包括以下步驟：將已形成的對稱可逆矩陣進行重排序；對重排序的所述對稱可逆矩陣按列進行符號分解，建立矩陣的依賴關系，同時根據依賴關系進行矩陣列剪枝，確定所述矩陣中填入元的位置；利用喬里斯基公式以及符號分解結果，對重排序的所述對稱可逆矩陣進行數值分解。本發明的基于電阻電容網絡的矩陣快速分解方法，能夠提高電路仿真性能，加快整體仿真速度。

技術領域

本發明涉及集成電路計算機輔助設計(Integrated Circuit/Computer AidedDesign)技術領域，特別是涉及電路仿真中快速求解稀疏矩陣的LL^t分解的方法。

背景技術

集成電路瞬態仿真，根本問題是在每個時間點求解大規模非線性方程組，對于非線性方程組的求解，需要采用牛頓迭代方法。而牛頓迭代方法的每一步，都是在求解線性方程組Ax＝b。線性方程組求解一般可采用直接法(三角分解及回代求解)和迭代法。

通常情況下，線性方程組的直接法會使用LU分解，即將A分解為下三角矩陣L(對角線為1)與上三角矩陣U的乘積。對于求解復雜度高、耗費時間長的稀疏線性方程組直接求解法，如何高效得進行稀疏矩陣的三角分解，并進行回代求解，成為一個十分重要的研究方向。

對于線性電路，或電路的線性部分來講，A是由常數電阻和常數電容等無源器件生成的對稱矩陣，利用此性質，可將A分解為下三角矩陣L與其轉置的乘積。直觀地講，由于A的對稱性，在LL^t分解時的計算量會降為LU的一半。對于線性電阻電容網絡，此問題轉化為怎樣進行快速喬里斯基分解。

由于稀疏線性方程組求解占據了電路仿真總時間的最大比例，成為了電路仿真的性能瓶頸。

發明內容

為了解決現有技術存在的不足，本發明的目的在于提供一種基于電阻電容網絡的矩陣快速分解方法，能夠提高電路仿真性能，加快整體仿真速度。

為實現上述目的，本發明提供的一種基于電阻電容網絡的矩陣快速分解方法，包括以下步驟：

將已形成的對稱可逆矩陣進行重排序；

對重排序的所述對稱可逆矩陣按列進行符號分解，建立矩陣的依賴關系，同時根據依賴關系進行矩陣列剪枝，確定所述矩陣中填入元的位置；

利用喬里斯基公式以及符號分解結果，對重排序的所述對稱可逆矩陣進行數值分解。

進一步地，所述對重排序的所述對稱可逆矩陣按列進行符號分解，建立矩陣的依賴關系的步驟，還包括，

對重排序的所述對稱可逆矩陣按列從左至右進行符號分解；

在符號分解過程中構造矩陣依賴關系樹，將已分解完的列，緊鄰對角元的下一個位置的行號，作為其父節點；

將L矩陣轉置的列作為其依賴的后代；

根據依賴關系中的子列計算分解列，跳過依賴傳導的列。

進一步地，所述根據依賴關系進行矩陣列剪枝，確定所述矩陣中填入元的位置的步驟，還包括，

所述矩陣中每一列維護一個位置指針，讀取列位置指針到列尾的部分，進行列內剪枝。

進一步地，

所述利用喬里斯基公式以及符號分解結果，對重排序的所述對稱可逆矩陣進行數值分解的步驟，還包括，

根據符號分解確定的矩陣非零位置，對重排序的所述對稱可逆矩陣左下角按列從左至右進行數值分解。

進一步地，還包括，

根據依賴關系中的后代列，利用喬里斯基公式計算分解列的分解結果。

更進一步地，還包括，