模型降階及論文閱讀心得

1、應用數學選講之論文閱讀報告模型降階問題以及關于“SAPOR:Second-Order Arnoldi Method for Passive Order Reduction of RCS Circuits”的論文報告第一章：模型降階第二章：關于SAPOR的論文閱讀報告第三章：模型降階領域的其他論文和書籍第一章：模型降階1. 模型降階的定義模型降階（Model Order Reduction，簡寫MOR），顧名思義，是在有合理的準確性的基礎上構建一個簡化的系統(tǒng)來近似原來的系統(tǒng)。2. 模型降階的應用當前隨著工程應用領域內的仿真、優(yōu)化和控制中會產生大型復雜系統(tǒng)，模型降階在快速科學計算上的優(yōu)越性顯露無遺

2、，因此也應用十分廣泛。很多非數學專業(yè)的其他領域，如電路仿真和自動控制的國際權威期刊上也會刊登著，很多情況下正是這些論文，才推動著模型降階，乃至科學計算的發(fā)展。本文介紹的論文是“SAPOR:Second-Order Arnoldi Method for Passive Order Reduction of RCS Circuits”，發(fā)表在ICCAD-04上.3. 模型降階的描述現(xiàn)對于一階線性時不變系統(tǒng)其中N很大。降階后：其中n<<N。針對以上形式，可以簡化成單輸入單輸出（SISO），也可以省去D或者E簡化成I等，當然這都是針對特殊的應用場合。類似的也可以進行推廣，有二階或二階以上的

3、高階系統(tǒng)，離散系統(tǒng)，雙線性系統(tǒng)，非線性系統(tǒng)，耦合系統(tǒng)，定常系統(tǒng)，偏微分系統(tǒng)等。有的可以是這些“變種”的疊加，如二階離散系統(tǒng)等。一般可以較簡單地將頻域內只應用于一階線性時不變的模型降階方法推廣到這些系統(tǒng)，然后掌握這些推廣后，又會反過來也會對模型降階方法的理解有更深刻的認識。當然，還有特殊的，如傳輸線系統(tǒng)，和本文后面介紹的SOPAR所應用的產生于互聯(lián)線的提取中的RCS系統(tǒng)。4. 輸入輸出系統(tǒng)特征自動控制領域會有可控性和可觀性的概念。范數作為一種衡量指標也是至關重要的。而穩(wěn)定性和無源性又是衡量模型降階方法是否可行的重要指標。5. 時域與復頻域下模型降階方法如果可以用微分方程表示的最簡單的一種形式，即

4、時域，當然也有Laplace變換后的代數形式，即復頻域。時域上大多采取正交分解模型降階方法，而復頻域上大多采用矩匹配。其他的方法有時域的本征正交分解（POD）和小波時域降階，頻域的積分全等變換和最優(yōu)化模型降階方法等。正交分解模型降階方法是在時間域上以正交多項式為基底的空間上展開，有Chebyshev多項式和Laguerre多項式等。矩匹配方法有較早的漸近波形估計（AWE）方法，基于Krylov子空間的方法，以及平衡截斷方法。當然，如果單點匹配不合適時，可以采用多點匹配甚至是擬合的方法（主要應用于非線性系統(tǒng)）。本文所介紹的SAPOR是應用于RCS二階系統(tǒng)，基于Krylov子空間的方法，采用了二階

5、Arnoldi迭代。第二章：關于SAPOR的論文閱讀報告1. 按論文順序下的論文介紹1 第一部分的“介紹”簡要分析了已有的互聯(lián)線（Interconnect）所用的AWE、PRIMA、ENOR、SMOR，并說明了本文是采取了RCS二階系統(tǒng)，引入了SOAR1論文中的二階Arnoldi算法。AWE6：Asymptotic Waveform Evaluation，漸近波形估計。優(yōu)點是可以顯式計算的（explicitly-calculated），缺點是不能產生高階模型，該方法的直接應用其實已經被淘汰了。3引入了基于Krylov子空間的方法，可以提供數值穩(wěn)定性，也可以滿足無源性。PRIMA5采用了Arno

6、ldi迭代算法，可以無源性，在數值快速計算上卻不能對大規(guī)模電路適用，而且直接應用于RCS二階系統(tǒng)時不能保持無源性。EDA行業(yè)三大巨頭之一的Mentor Graphics開發(fā)的ENOR7是針對二階系統(tǒng)的，充分利用了對稱正定（symmetry positive define，簡稱s.p.d），可是卻采用了遞歸公式（recursive formula），因此不是數值穩(wěn)定的。Carnegie Mellon University(CMU)開發(fā)的SMOR9實在ENOR的基礎上采用了Krylov子空間的方法取代了遞歸公式，消去了ENOR中不正交的附加變量，提供了數值穩(wěn)定性和準確性。卻只是能近似地接近原系統(tǒng)，

7、不能精確的矩匹配。關于ENOR和SMOR，后面還會再詳細地講到。2、8提供了取代RCL，并采取RCS的思想，S，即Susceptance，電納。（注意：在嚴謹意義上是電容和電感合起來的電抗的逆，可該論文是作為電感的逆，也就是感納。本文后面都用電納來指代。）S具有短程效應，隨著距離的增加，互連之間的電納比電感要下降的快的很多。所以S矩陣是對角占優(yōu)，可以通過不破壞正定性的簡單截斷方法來稀疏化，這對快速仿真很有用。SAOR1提出了一種二階Arnoldi方法來解決二次特征值問題，充分利用了對稱正定性，所以SAPOR從中抽取了其算法來應用，數值上比ENOR更穩(wěn)定和效率，比SMOR更能精準地匹配原系統(tǒng)的矩

8、。2 第二部分的“背景回顧”分別對RCS、ENOR和SMOR進行了較為詳盡的介紹。RCS：電納矩陣等于電感矩陣的逆，即S=I-1。RCS電路的節(jié)點方程：（1）其中，未知向量V(t)：節(jié)點電壓，中間向量IS(t)：電納電流。J(t)：電流源向量，G、C、S分別是電導、電容和電納矩陣。ES、B：電納和電流源的關聯(lián)（incidence）矩陣。頻域下的節(jié)點方程即：（2）符號是對應于（1）式中的。從（2）中矩陣向量的第二行可知：（3）把（3）帶到（2）中矩陣向量的第一行，得：（4）這里，=ESSEST。C、G、是對稱半正定的。（4）與（2）等價，是消去電納電流的形式。然后通過使用列向量為正交規(guī)范基的Q，

9、做保持無源性的正交投影?？梢缘玫剑海?）其中，。7中證明了正交投影可以保持原系統(tǒng)的無源性。 ENOR：原系統(tǒng)的矩是通過遞歸公式（離散化，抽樣）來顯式地生成和正交規(guī)范化的。s=s0（1-z）（s0是選擇的頻率展開點），引入了附加變量，于是對于k0，有：（6）（7）這里P=s0C+G+1/s0，Vk，Yk和Jk分別是V，Y和J在s0處展開的k階矩。V的矩可以通過以上遞歸形式，用Gram-Schmidt方法計算到需要的階數。可是，上面的迭代關系容易導致數值不穩(wěn)定性。而且只有V向量是用Gram-Schmidt方法正交規(guī)范化得到的，Y向量沒有用正交化方法得到。9中提到的，隨著迭代次數的增多，Y向量的幅值

10、會快速增大，這也可能導致數值不穩(wěn)定性。因此，ENOR不是數值穩(wěn)定的。SMOR：為了解決ENOR的數值穩(wěn)定性問題，采用了一種基于Krylov子空間的方法來構建模型降階的正交規(guī)范基。從（7）中，可知：（8）因為脈沖響應通常對矩匹配是必需的，所以該論文后面都假設Jk=0（k1）。將（8）帶入（6），可以得到消去Y的新的迭代關系：（9）（10）SMOR正是以這個公式構建了Krylov子空間。為了加速模型降階，避免誤差累積，SMOR只保留了（9）式中右邊的后三階，即：（11）然后再用（10）和（11）的簡化遞歸關系，正交規(guī)范化產生Vk。通過在遞歸公式中消去Y向量，SMOR提高了模型降階過程中的數值穩(wěn)定性

11、。然而因為（11）式中的簡化，SMOR產生的子空間只是原始系統(tǒng)的矩展開的子空間的近似。因此，SMOR產生的降階系統(tǒng)不會精確地矩匹配。因此，降階模型的準確性難以保證。3 第三部分的“SAPOR方法”為了建立一個針對RCS的穩(wěn)定無源的模型降階過程，構建以V的矩展開的子空間的正交規(guī)范基，用它作為投影矩陣Qn，然后通過對原始的系統(tǒng)（4）做正交投影，我們得到了降階系統(tǒng)（5）。與SMOR相同，也有脈沖響應是必需的，也就是：Jk=0（k1）。那么，（4）可以改寫為：（12）采用s=s0+的變換，有：（13）這里，D=2s0C+G,K=s02C+s0G+,b0=s0BJ0,b1=BJ0。將V在s0處Taylo

12、r展開，有：（14）這里V0，V1，V2，是V的矩。通過比較上式的兩側，我們有以下的遞歸關系：（15）（16）（17）然而，如果只是按上述式子來顯式計算V的矩，數值上是不穩(wěn)定的?；贙rylov子空間的技術則相反是更理想的。（13）式是一個二次參數化矩陣方程（QPE）。1針對二次特征值問題（可以看成有式子右邊是零的QPE）提出一種二階Arnoldi方法SOAR。該論文將把SOAR方法提取出來，應用到RCS電路的模型降階上去。系統(tǒng)線性化：引入了一個新變量Z()，它滿足：（18）將（18）帶入（13），有：（19）結合（18）、（19）式，有：（20）這里，q0=K-1b0，p0=b1。通過把（I

13、-A）移到（20）的右邊，Maclaurin展開，有：（21）很明顯，是的第i階矩。（20） 式是（13）式的線性形式，右邊沒有。如果是（20）的解，V必然是（13）的解，這意味著的第i階矩的上部分，即，必須等于V的第i階矩。正交規(guī)范化步驟：該論文這一部分主要采用了SOAR的算法，來構建V的矩張成的子空間的正交規(guī)范基。算法1：SOAR的推廣輸入：A，q，p，正整數階數n輸出：正交規(guī)范矩陣Qn圖1.SOAR推廣算法定理1：如果SOAR推廣算法沒有在第十步停止，q1，q2，qn便形成了V矩空間的正交規(guī)范基。定理2：如果我們采用Qn來對系統(tǒng)（4）進行投影，得到系統(tǒng)（5），降階系統(tǒng)（5）會匹配原系統(tǒng)（

14、4）的前n階矩。定理1、2的證明在1中均有。定理1保證了無源性，定理2保證了精確矩匹配。如果在第十步停止，1中的解決技術也可以在這里使用，來提供正交規(guī)范化的穩(wěn)定性。在正交規(guī)范化過程中，唯一的矩陣求逆是K-1。由于K是對稱正定的（s.p.d.），稀疏的，有很多有效的方法來計算K的稀疏Cholesky分解，然后有效地應用到求K-1的矩陣-向量乘積。而且，SOAR推廣算法可以修正到一種節(jié)省存儲的變體，向量p1,p2,pn都不用顯式地存儲。該論文并沒有展開闡述。SAPOR的步驟：1) 形成如二階系統(tǒng)（4）所示的RCS電路；2) 用s=s0+來變換（4），得到（13）；3) 引入滿足（18）的變量Z()

15、，產生線性化系統(tǒng)（20）；4) 用圖1中的SOAR推廣算法來構建正交規(guī)范矩陣Qn；5) 對原始系統(tǒng)做正交投影，得到降階系統(tǒng)（5）。SAPOR的優(yōu)點：1) 對比ENOR方法，采用Krylov子空間技術來達到數值上更穩(wěn)定的正交規(guī)范化過程。SAPOR與ENOR的關系就像一階系統(tǒng)下基于Arnoldi迭代的方法與AWE。2) 對比SMOR方法，如定理1、2所說，SAPOR能精確地矩匹配。3) 在時間復雜度上相同，因為SAPOR、SMOR和ENOR對同一階數下模型降階過程有相同的操作。4 第四部分的“數值實驗”是在Matlab，展示了SAPOR的有效性，把SAPOR與ENOR和SMOR比較。電路模型由8比

16、特總線和2根屏蔽線組成(該論文的圖2)。未知的有330個結點電壓和160個電納電流，即N=490。圖3是對n取40、60、80時的頻率響應對比。圖4、5、6分別顯示了在SAPOR、ENOR、SMOR這三種方法中，在三種降階階數下的絕對誤差。SAPOR在低頻段均能十分精確地匹配，絕對誤差只有10-12，頻率越高誤差越大。頻率較高時，絕對誤差近乎趨向于1，而且n越大，開始接近1的頻率越高。SAPOR降階階數越高，越能矩匹配，匹配的頻率范圍越寬，降階系統(tǒng)越能適應越快轉換時間的信號（這對高速電路的仿真很重要）。對于ENOR，降階階數增加，誤差幾乎保持相同，體現(xiàn)了ENOR對高階模型的數值不穩(wěn)定性；對于S

17、MOR，由于自身方法采取了近似手段，不同降階階數在低頻時，誤差卻不相同。圖7是同一降階階數（n=80）下對SAPOR、ENOR、SMOR的誤差對比。低頻時SAPOR十分精確，只有在頻率相當高（20GHz）時，誤差才開始與ENOR和SMOR相同。隨著電路的復雜，需要降階系統(tǒng)更高階數，更準確，所以SAPOR的優(yōu)越性會隨著電路尺寸的持續(xù)增加而愈發(fā)明顯。2. 與SAPOR有關的論文間引證發(fā)展關系系統(tǒng)矩陣結構的完善：PRIMASAPOR和SPRIM11二階Arnoldi算法的繼承：SOARSAPOR和TS-SOAR12RCS系統(tǒng)的繼承：2、8SAPOR互連線模型降階領域的軟件更迭：ENORSMORSAP

18、OR3. 關于該篇論文的看法文章清晰分明，對之前工作，尤其是互連線方面的模型降階軟件進行了剖析，分析了它們的缺點，充分結合了當時最前沿的各種技術。但是因為主要的算法是對SOAR論文中的二階Arnoldi算法，所以被引少，對模型降階方法的學術貢獻較?。ㄏ噍^而言，SOAR則被引較多，更別提PRIMA等經典的算法了）?？墒且驗樗菍ｉT針對于集成電路仿真中的互連線的開發(fā)出的軟件，所以在實際的工程應用還是非常廣泛的。與該文章共同在發(fā)表在ICCAD-04的還有同一領域的SPRIM（相較而言，SPRIM被引較多，可能更知名些），基本思想有所類同。由此也可見該領域的研究十分火熱。第三章：模型降階領域的其他論文

19、和書籍：1 Z. Bai and Y. Su，SOAR：A Second-Order Arnoldi Method for the Solution of the Quadratic Eigenvalue Problem. Computer Science Technical Report，CSE-2003-21，University of California，Davis，2003.2 A. Devgan，H. Ji and W. Dai，How to Efficiently Capture On-Chip Inductance Effects：Introducing a New Circu

20、it Element K. Proc. Of IEEE/ACM ICCAD 2000，pp.150-155，2000.3 R.W. Freund，Reduced-Order Modeling Techniques Based on Krylov Subspaces and Their Use in Circuit Simulation. Numerical Analysis Manuscript，No.98-3-02，Bell Laboratories，F(xiàn)eb. 1998.4 D. Ling and A. Ruehli，Circuit Analysis, Simulation and Desi

21、gn-Advances in CAD for VLSI. Vol.3,Part, Chap.11，Elsevier Science Publisher，1987.5 A. Odabasioglu，M. Celik and L. Pileggi，PRIMA: Passive Reduced-Order Interconnect Macromodeling Algorithm. IEEE Trans. On CAD of Integrated Circuits and Systems，vol.17，no.8，pp.645-654，Aug. 1998.6 L. Pillage and R. A. Rohrer，Asymptotic Waveform Evaluation for Timing Analysis. IEEE Trans. On CAD of Integrated Circuits and Systems，Vol.9，No.4，pp.352-366，Apr. 1990.7 B. N. Sheehan，ENOR：Model Order Reduction of RLC Circuits Using Nodal Equat