Search

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]

This paper proposes a linear-time complex-valued eigenvalue solver for solving large-scale on-chip interconnect problems. The fast eigenvalue solution is achieved by eigenvalue clustering, fast system reduction with negligible computational cost, and fast linear-time solution of the reduced system. Numerical and experimental results are presented to demonstrate the accuracy and efficiency of the proposed method. [ABSTRACT FROM AUTHOR]