From O(k2N) to O(N): A fast complex-valued eigenvalue solver for large-scale on-chip interconnect analysis

In general, the optimal computational complexity of Arnoldi iteration is O(k²N) for solving a generalized eigenvalue problem, with k being the number of dominant eigenvalues and N the matrix size. In this work, we reduce the computational complexity of the Arnoldi iteration from O(k²N) to O(N), thus paving the way for full-wave extraction of very large-scale on-chip interconnects, the k of which is hundreds of thousands. Numerical and experimental results have demonstrated the accuracy and efficiency of the proposed fast eigenvalue solver.