求解电路仿真中超大规模稀疏线性方程组的改进分块对角加边方法  

AN IMPROVED BORDERED BLOCK DIAGNAL METHOD FOR SOLVING LARGE SCALE SPARSE LINEAR EQUATIONS IN CIRCUIT SIMULATION

作　　者：陈炳旭 寇彩霞 陈圣杰 Chen Bingxu;Kou Caixia;Chen Shengjie(Key Laboratory of Mathematics and Information Networks(Beijing University of Posts and Telecommunications),Ministry of Education,Beijing 100876,China;School of Sciences,Beijing University of Posts and Telecommunications,Beijing 100876,China;Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China;School of Mathematical Sciences,University of Chinese Academy of Sciences,Beijing 100049,China)

机构地区：[1]数学与信息网络教育部重点实验室(北京邮电大学),北京100876 [2]北京邮电大学理学院,北京100876 [3]中国科学院数学与系统科学研究院,北京100190 [4]中国科学院大学数学科学学院,北京100049

出　　处：《计算数学》2024年第4期529-546,共18页Mathematica Numerica Sinica

基　　金：国家重点研发计划(2021YFA1003601);国家自然科学基金(12171052);中央高校基本科研业务费专项资金资助(2023ZCJH02)资助.

摘　　要：针对电路仿真中瞬态分析产生的超大规模稀疏线性方程组,分块对角加边(Bordered Block Diagonal,BBD)方法是一类经典的求解方法.本文提出了一种改进的BBD方法,通过使用基础列分解和流水线分解结合的方式,改善了传统BBD方法中负载不均衡的问题.在矩阵边界分解时,本文通过引入流水线分解克服了传统方法边界难以并行的缺陷.通过求解16个真实电路上产生的超大规模稀疏线性方程组,我们验证了改进BBD方法的有效性.相较于传统的BBD方法,改进方法在不同线程下的求解速度均有一定提升.The Bordered Block Diagonal(BBD)method is a classical approach for solving the largescale sparse linear equation systems generated in transient analysis of circuits simulations.In this paper,a new BBD method is proposed,which improves upon the traditional BBD method by addressing the issue of load imbalance through a combination of basic column decomposition and pipelined decomposition.During the matrix boundary decomposition,the introduction of pipelined decomposition overcomes the difficulty in parallelizing boundaries in traditional methods.By solving the large-scale sparse linear equations generated from 16 real-world circuits,we have verified the effectiveness of the improved BBD method.Compared to the traditional BBD method,the improved method has certain improvements in solution speed with various numbers of parallel threads.

关 键 词：分块对角加边方法 超大规模稀疏线性方程组 电路方程组 稀疏LU分解 电路仿真 并行计算 

分 类 号：O241.6[理学—计算数学]