关键词:
电路仿真
GMRES
LU分解
预条件重用
摘要:
大规模集成电路的设计和分析都依赖于电子设计自动化(Electronic Design Automat-ion,EDA)技术,需要通过数值模拟方法对电子电路进行仿真。电路系统数值模拟本质上是求解线性方程组Ax=b,其中A为非对称的大规模稀疏矩阵,b是已知向量,x是待求解向量。在如今的科学与工程计算任务中,线性方程组的未知量个数越来越多,导致计算需求越来越大,使得线性方程组(特别是系数矩阵为大型稀疏矩阵的方程组)的快速求解变得至关重要。一般来说,直接法求解方程组所需要的运算次数为O(n3)(n为系数矩阵A的维数),但该方法不可避免地需要耗费巨量的存储资源和计算资源,同时也可能会导致系数矩阵的结构遭到破坏。此外,若n的数值过大,直接法的计算效率将显著降低。与直接法不同,迭代法是逐步逼近线性方程组的解,其求解稀疏线性方程组所需的计算量相对较小。此外,迭代法的程序设计简单,并能够有效地利用矩阵的稀疏性来节省内存,因此在解决大规模问题时,通常采用迭代法。与直接法相比,合适的迭代解法计算量更小,且误差更可控,有望较大幅度地提高大规模稀疏矩阵方程组求解的计算效率,在复杂电路仿真的加速问题上有重要的工程应用价值。GMRES(Generalize Minimal Residuals,广义最小残差法)方法是求解大型稀疏非对称方程组极为有效的迭代法之一,该方法是利用Krylov子空间的方式近似求解方程组,即通过寻找能够使残差最小的向量来逼近实际解。但是,如果采用GMRES方法进行计算,随着迭代次数的增加,计算和存储的需求也随之增加,有时GMRES方法可能不会收敛。为了解决这一问题,研究者们在算法方面进行了多项改进和优化,深入探索了 G MRES方法的预处理技术。预处理技术可以使方程组系数矩阵的结构特征改变,从而进一步提升计算效率。因此,本文的关键研究方向在于寻找恰当的预处理方法。本文立足于Krylov子空间方法,尝试研究一些有效的加速策略,旨在提高电路仿真中预处理GMRES迭代法的求解速度。电路仿真中现有的求解大规模稀疏系统使用的预处理GMRES迭代法收敛性不能很好地满足工程计算需求,针对此弊端,本文提出了预条件重用LU广义最小残差法(RPLUGMRES),该方法结合电路矩阵的特点,采用预处理GMRES迭代法,将LU分解导出的L、U作为预条件进行重用。首先将预处理GMRES迭代法用于求解线性系统问题,再针对预处理GMRES迭代法求解过程中的不良问题,利用预条件重用有效提高了算法的收敛速度,减少了矩阵向量乘次数和CPU时间,并对ILU(Incomplete LU)分解做预条件重用的数值稳定性进行了分析,最后在数值实验中验证了 RPLUGMRES的有效性。另一方面,针对预处理GMRES迭代法初始值设置简单随意的问题,RPLUGMRES将初始值设置为预矩阵求解的值,即在t0时刻,对A0进行LU分解,将分解产生的L、U代入下一时刻线性方程组A1x=b1中得LUx=b1并求解,所得解向量作为下一时刻预处理GMRES迭代的初始值,并与初始值设置为零的策略进行了对比评估,结果表明RPLUGMRES方法初始值设置策略的有效性。本文提出的RPLUGMRES方法主要在预条件重用和初始值设置两个方面,较预处理GMRES迭代法有较为显著的提升和改进。实验结果表明,本文RPLUGMRES方法具有较强的工程实用性,能够在实际电路求解问题中较大幅度地提高计算效率、降低计算成本。