From O(N) to O(M): Time-domain layered finite-element reduction-recovery methods for large scale electromagnetics-based analysis and design of on-chip circuits

As on-chip design scales into the nanometer regime, full-wave electromagnetics (EM)-based analysis has increasingly become essential for four main reasons: (1) reduced feature sizes that lead to subwavelength optical lithography, (2) increased clock frequency, (3) the transition from single core to multicore, and (4) increased level of integration. However, the design of next- generation ICs results in numerical problems of very large scale, requiring billions of parameters to describe them accurately. In general, to solve problems with TV parameters, the optimal computational complexity one can hope for is linear complexity 0(N). For the next generation VLSI circuit problem, however, even 0(N) is prohibitively high since N is too large. Our research objective is to overcome the large problem size of 0(N) to achieve a complexity of 0(M), with MLtN, also in a rigorous fashion.