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

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.