第31卷第4期
2001年7月
东南大学学报
(自然科学版 )
JOURNAL OF SOUTHEAST UNIVERSITY (Natural Science Edition )
Vol.31 No.4
July 2001
半导体器件模拟中求解线性系统的预条件处理方法
刘其贵 吴 金 肖志强 魏同立
(东南大学微电子中心 ,南京 210096 )
摘要 :对半导体器件模拟中求解线性方程组的预条件处理方法 ,即不完全 LU 分解方法进行了
研究 .首先介绍了 ILU 分解的理论基础 ,说明了采用预条件处理方法对解决线性方程组迭代求
解收敛的重要性 .然后介绍了由 ILU 方法发展而来的 ILUV 方法 ,并在对 ILU 和 ILUV 方法的理
论研究和算法分析的基础上 ,提出了兼容以上 2 种方法优点的 ILUVP 方法 ,解决了 ILUV 方法
中参数ψ的选取无法兼顾计算量和收敛速度不同要求的难题 .最后通过对一个存在陡峭层分
布的漂移扩散方程进行求解的实例 ,验证了算法的可行性和有效性 .
关键词 : ILU ;ILUV ; ILUVP ; 预条件
中图分类号 : TN402 文献标识码 : A 文章编号 :
1001 - 0505(2001 )04-0014-04
收稿日期 :2000-11-23 . 作者简介 : 刘其贵 ,男 ,1977 年生 , 博士研究生 .
基金项目 : 国 家 自 然 科学 基 金(698060 02 )和江 苏 省自 然科学 基 金 (BK97006 )资 助 项目 .
对半导体器件性能的模拟 ,其核心问题最终可归结为线性方程组 Ax = b 的求解
[1 ]
.系数矩阵 A 为大
型稀疏矩阵 ,通常采用迭代法求解 ,迭代解的收敛性能与矩阵的条件数或谱半径密切相关 .在绝大多数条
件下 ,由于 A 严重病态 ,导致收敛速度很慢甚至无法收敛 ,因此 ,实际中常采用预条件的处理方法以解决
上述问题 .
目前 ,最常用的预条件方法是不完全 LU 分解 ,即 ILU 分解
[2 ,3 ]
,以及在此基础上改进的 ILUV 分解
[4 ]
.
对于根据非零元素位置进行的 ILU 分解 ,保持了 K
L
和 K
U
与 A 对应部分相同的稀疏性 , A 中非零元素位
置在 R 中一定为零 ,而 A 中零元素位置在 R 中却可能为非零 ,由于稀疏矩阵 A 中大量为零元素 ,导致 R 中
非零元素数量过多 ,而且绝对值大小也得不到有效控制 ,在某些场合下预条件处理效果并不理想 .
ILUV 方法不再强求相同的稀疏性 ,可以有选择地保留或丢弃 K 中的元素 ,被丢弃的元素放入到 R 的
对应位置中 .根据以上要求 ,K 中保留的元素数值应大 ,而放入 R 中的元素数值应尽可能小 .虽然 ILUV 方
法在实现方面需要花费较多的时间 ,但由于元素数值的大小及在两矩阵中的具体分配可通过阈值参数 ψ
进行调控 ,因此灵活性较高 .ILUV 分解的质量与 ψ密切相关 ,本文在兼顾以上 2 种方法基础上提出的
ILUVP 方法 ,可以较好解决计算量及收敛速度对参数 ψ的不同要求 .
1 矩阵 ILU 分解的理论基础
对于特定矩阵 A ,可分解为 A = K + R .分解的一个基本要求是 K 应与 A 充分近似 ,剩余矩阵 R 的模
应尽可能小 ,而且 K可进一步分解为单位上三角与下三角矩阵的乘积 K
L
K
U
.这样 ,与原方程互为等效的形
式为 ( K
-1
L
AK
-1
U
)( K
U
x )= K
-1
L
b ,令 B = K
-1
L
AK
-1
U
,y = K
U
x ,c = K
-1
L
b ,则得到等价的求解形式为
By = c ,其系数矩阵 B 的条件数将强烈地依赖于所分解的 K
-1
L
和 K
-1
U
,只 要 K
L
和 K
U
的分解得当 ,可使 B
的条件数得到大幅度改善.考虑到 B = I + E ,要求
E
2
<1,由于 E = K
-1
L
RK
-1
U
,则
E
2
≤
K
-1
L
2
R
2
K
-1
R
2
,因此 ,对矩阵分解提出的一个重要限制就是剩余矩阵 R 的模应尽可能的小 ,即要求
R 中非零元素的数量和绝对数值均应较少 .
2 不完全分解的 ILUV 方法
ILUV 方法是 ILU 方法的发展 ,也是本文的重点理论基础 .首先 ,考虑系数矩阵 A 为对称正定矩阵的情
况
[5 ]
,此时由矩阵 K 分解得到下三角矩阵 K
L
与上三角矩阵 K
U
的乘积 .由于 A 为对称矩阵 ,则应有 K
U
=