基于自适应矩阵低秩分解的三维电容提取计算加速  

The Accelerated 3D Capacitance Extraction Based on Adaptive Low-Rank Matrix Factorization

作　　者：黄杰辰 冯栩 喻文健[1,2] Huang Jiechen;Feng Xu;Yu Wenjian(Department of Computer Science and Technology,Tsinghua University,Beijing 100084;Beijing National Research Center for Information Science and Technology,Tsinghua University,Beijing 100084)

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]清华大学北京信息科学与技术国家研究中心,北京100084

出　　处：《计算机辅助设计与图形学学报》2022年第7期1138-1146,共9页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61872206,62090025).

摘　　要：为了加速直接边界元法电容提取,利用方程组系数矩阵的局部低秩性进行定精度的低秩分解,用分解因子代替原矩阵参与线性方程组的迭代求解,在保持一定精度的同时加快求解速度.为了降低矩阵分解带来的额外开销,提出分解算法针对矩阵向量乘这一下游任务进行优化.在大量三维互连线结构上的实验结果表明,所提快速自适应低秩分解fastQB算法相比现有的randQB_EI算法的加速比达到1.5,引入矩阵低秩分解后方程组的迭代求解加速比达到16.8.In order to accelerate the direct boundary element method(DBEM)of capacitance extraction,the pro-posed method explores the local low-rank character of the coefficient matrix,and performs fixed-precision low-rank matrix factorizations to approximate it to accelerate the iterative solution without lost of accuracy.A fast adaptive low-rank matrix factorization algorithm is proposed aiming at higher efficiency on subse-quent matrix-vector multiplication.Experiments on several IC interconnect structures show that the pro-posed fast adaptive algorithm(called fastQB)achieves a maximum speedup of 1.5X over the existing randQB_EI algorithm.The iterative solution of the DBEM equations is accelerated by at most 16.8X with the proposed technique based on adaptive low-rank matrix factorization.

关 键 词：直接边界元法 三维寄生电容提取 自适应矩阵低秩分解 线性方程组求解 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]