From $O(k^{2}N)$ to $O(N)$ : A Fast and High-Capacity Eigenvalue Solver for Full-Wave Extraction

The wave-propagation problem in an on-chip interconnect network can be modeled as a generalized eigenvalue problem. For solving such a generalized eigenvalue problem, the computational complexity of Arnoldi iteration is at best O(k ² N), where k is the number of dominant eigenvalues and N is the matrix size. In this paper, we reduce the computational complexity of the Arnoldi iteration for interconnect extraction from O(k ² N) to O(N), thus paving the way for full-wave extraction of very large scale on-chip interconnects, of which a typical value of k is on the order of hundreds of thousands. Numerical and experimental results have demonstrated the accuracy and efficiency of the proposed fast eigenvalue solver.