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

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

为了加速直接边界元法电容提取,利用方程组系数矩阵的局部低秩性进行定精度的低秩分解,用分解因子代替原矩阵参与线性方程组的迭代求解,在保持一定精度的同时加快求解速度.为了降低矩阵分解带来的额外开销,提出分解算法针对矩阵向量乘这一下游任务进行优化.在大量三维互连线结构上的实验结果表明,所提快速自适应低秩分解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.