一种改进的IC互连线3D电容提取快速层级算法

快速层级算法(FHM)是边界元法求解3D电容积分方程的一种加速方法,该方法基于分层近似对电势系数矩阵隐式表示,使求解的时间复杂度降低到O(n).改进算法对FHM做了两点改进:(1)给出了分层近似的理论依据,这种分层依据适用于所有导体结构而无需重复试验.(2)利用层级关系,直接计算面电荷,避免了迭代过程,加速了电荷求解.一系列典型3D互连线结构的测试显示:改进后的算法不仅提高了求解精度,而且计算时间也减少到改进前的1/3.