Complex dielectric image Green´s function method combined with FDHT for on-chip interconnects

A fast discrete Hadamard transform (FDHT) is proposed through a butterfly iterative algorithm involving only additions and subtractions. To speed the extraction of frequency-dependent capacitance and conductance for on-chip transmission lines and interconnects, the novel FDHT method is used for the first time to sparsify the full matrix established by the method of moments combined with a complex dielectric image Green´s function method accelerated by a Pade approximation. Numerical results show that the proposed efficient method sparsifies the matrix significantly. For the whole solution of matrix equations the computational speed of the FDHT sparsification method combined with GMRES iterations is faster than that of the wavelet sparsification method with Schultz iterations. Capacitance and conductance calculated from the proposed method with high sparse ratio are in good agreement with the results computed from FastCap and the complex dielectric image Green´s function method.