From O(k²N) to O(N): A Fast and High-Capacity Eigenvalue Solver for Full-Wave Extraction of Very Large Scale On-Chip Interconnects.

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 interconnectextraction 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. [ABSTRACT FROM AUTHOR]