一個隱含稀疏變換的三維電容抽取演算法

Abstract

本篇論文主要闡述在三維電容抽取中有效地產生一個隱含稀疏變換的電位係數矩陣，之前所有的電容抽取演算法都是基於邊界元素法並且以所有的葉節點來定義電位係數矩陣，基於任一小導體表面均可視為基底的前提下，ICCAP發現以所有葉節點作為基底的變換將會得到一個最緊密的線性方程式。因此，ICCAP提出一個可以在線性時間內找出最佳基底的演算法，它可以保證在線性時間內建立出一個僅含有O(n)元素的電位係數矩陣。由此，這個稀疏變換可以使用前置式疊代解矩陣的方法加速整個線性方程式的求解速度。

This thesis presents ICCAP to efficient generate sparsified potential coefficient matrices for three-dimensional capacitance extraction. Previous capacitance extraction algorithms based on boundary element formulate the potential coefficient matrix in terms of surface potentials and charges on the most delicate panels (leaf panels). By introducing the concept of basis panels, ICCAP reveals that leaf panels compose the worst basis which leads to the densest system. Therefore, ICCAP proposes a linear time basis panel selection algorithm to choose a new set of basis panels. It is provable that the n x n potential coefficient matrix constructed in terms of the new basis contains O(n) non-zero entries and hence the sparse system can be solved more efficiently by preconditioned iterative matrix solvers.