Book mark: Current Research Projects | Research Highlights |

- Current Research Projects

 

- High-Capacity Computational Electromagnetic Methods

- Electromagnetic Solutions for High-Frequency Mixed-Signal IC Design (Completed)

- Accurate and Fast Broadband Modeling of the Die-Package Interaction (Completed)

- A Hierarchical Matrix Framework for Electromagnetics-Based Analysis and Design of Next-Generation ICs

- From O(N) to O(M): Scalable Algorithms for Large Scale Electromagnetics-Based Analysis and Design of Next Generation VLSI Circuits

- Simulation, Design and Fabrication of Interconnect Programmable Microwave Arrays (Completed)

- Rigorous and Fast Physics-Based Co-Simulation of Device-Structure-Material Interactions in Complex, Nonlinear, and Time-Variant Mixed-Signal Circuits (Completed)

- Direct Matrix Solutions of Linear Complexity for Rapid Modeling and Design of High Bandwidth Package Interconnects

- Say "No" to Extraction - A Transformative Circuit Simulation Paradigm Guided by First Principles

- Method for Fast and Accurate Signaling Analysis of Non-LTI Systems

- Solution to a Few Open Problems in Inverse Design for High-Performance Integrated Circuit Synthesis in Full Electromagnetic Spectrum

- Research Highlights

 

Book mark: Direct FEM | Direct IE | Direct Electrically Large Analysis | Low-Frequency Breakdown | Explicit Unconditionally Stable | Circuit Simulator


Direct Finite Element Solver of Linear Complexity for Large-Scale Electromagnetic Analysis:

 

    In general, to solve problems with N parameters, the optimal computational complexity is linear complexity O(N). State-of-the-art fast finite-element solvers rely on iterative approaches to solve large-scale problems. The computational complexity of an iterative solver is O(N_{it}N_{rhs}N) at best, where N_{it} is the number of iterations, and N_{rhs} is the number of right hand sides. When N_{it} and N_{rhs} are large,    state-of-the-art iterative solutions become inefficient since the entire iteration procedure has to be repeated for each right hand side. Furthermore, the complexity of an iterative solver is problem dependent since the iteration number N_{it} is, in general, problem dependent. In addition, most of the iterative solvers rely on preconditioners to reduce N_{it}, which further increases the overall computational complexity. The high computational complexity makes the analysis and design of many very large-scale engineering systems beyond the reach of existing solvers. In this work, we pioneer a direct FEM solver of O(N) (optimal) complexity for general electromagnetic analysis.     The linear complexity of this direct solver in CPU time and memory consumption is demonstrated by theoretical analysis and numerical experiments, for both electrically small and electrically large analyses. On a single 3 GHz CPU core, this solver has successfully solved an electrodynamic system matrix of over 22.8488 million unknowns resulting from an industry full package in 16 hours with first-principles-based full-wave accuracy; it has also rapidly analyzed large-scale antenna arrays of over 73 wavelengths with 3,600 antenna elements having 10.1472 million unknowns, neither of which was feasible before. The upper right figure shows the electric field distribution generated by this direct solver across the entire package area, and the correlation of simulation results with measurements. The lower left figure provides a time and complexity comparison with state-of-the-art direct sparse solvers. You can request a copy of this software on the "Software Release" page of this website.

Selected Publications:

[1] B. Zhou and D. Jiao, "A Linear Complexity Direct Finite Element Solver for Large-Scale 3-D Electromagnetic Analysis," IEEE International Symposium on Antennas and Propagation, pp. 1684-1685, July 2013. (BEST STUDENT PAPER FINALIST AWARD)

[2] B. Zhou, H. Liu, and D. Jiao, "A Direct Finite Element Solver of Linear Complexity for Large-Scale 3-D Circuit Extraction in Multiple Dielectrics," the 50th ACM/EDAC/IEEE Design Automation Conference (DAC), 6 pages, June 2013. (ONE OF THE 162 PAPERS ACCEPTED OUT OF 747 SUBMITTED)

[3] B. Zhou and D. Jiao, "Direct Finite-Element Solver of Linear Complexity for System-Level Signal and Power Integrity Co-Analysis," IEEE International Conference on Signal and Power Integrity (SIPI), pp. 721-726, 2014. (Invited Paper)

[4] B. Zhou and D. Jiao, "Linear (Optimal) Complexity Direct Full-Wave Solution of Full-Package Problems Involving over 10 Million Unknowns on a Single Computer," TECHCON 2014. (BEST PAPER AWARD, Chip-Package co-design session)

[5] B. Zhou and D. Jiao, "Direct Finite Element Solver of Linear Complexity for Analyzing Electrically Large Problems," the International Review of Progress in Applied Computational Electromagnetics (ACES 2015) Conference, Williamsburg, VA, Mar. 2015. (BEST STUDENT PAPER AWARD)

[6] H. Liu and D. Jiao, "Existence of H-matrix Representations of the Inverse Finite-Element Matrix of Electrodynamic Problems and H-Based Fast Direct Finite-Element Solvers," IEEE Trans. MTT, vol. 58, no. 12, pp. 3697-3709, Dec. 2010.

[7] H. Liu and D. Jiao, "A Theoretical Study on the Rank's Dependence with Electric Size of the Inverse Finite Element Matrix for Large-Scale Electrodynamic Analysis," IEEE International Symposium on Antennas and Propagation, 2012.


Direct Integral Equation Solvers (Inverse and LU) of Linear Complexity for Large-Scale Circuit Extraction:

 

     Prevailing fast integral equation (IE) solvers are iterative solvers relying on fast techniques that can perform a dense matrix-vector multiplication in O(N) or O(NlogN) complexity. The complexity of an iterative solver is at best O(N_{rhs}N_{it}N), where N_{it} is the number of iterations, and N_{rhs} the number of right hand sides. We have originated linear (optimal) complexity dense matrix inversion and LU factorization algorithms for general 3-D circuit extraction, including capacitance, resistance, inductance, and full-wave extraction of general 3-D structures involving inhomogeneous dielectrics and arbitrarily shaped lossy conductors. This work breaks the conventional computational barrier of IE-based methods.     In our direct surface IE solver for capacitance extraction, a dense matrix having 3.71 million unknowns is inverted in fast CPU time (1.6 h), modest memory consumption (4.4 GB), and with prescribed accuracy satisfied on a single core running at 3 GHz. In our O(N) direct surface IE solvers as well as O(N) direct volume IE solvers for full-wave extraction, we overcome the numerical challenge of solving a highly unstructured system matrix mixed with both square and rectangular dense and sparse matrices by developing a fast linear complexity direct solution. The inverse of a 2.68-million-unknown matrix arising from the full-wave extraction of a large-scale 3-D interconnect, which is a matrix solution for 2.68 million right hand sides, was obtained in less than 1.5 GB memory and 1.3 h on a single 3 GHz CPU core. Comparisons with both state-of the-art iterative and direct IE solvers for circuit extraction have demonstrated clear advantages of the O(N) direct IE solvers in both CPU time and memory consumption.

Selected Publications:

[1] W. Chai, D. Jiao, and C. C. Koh, "A Direct Integral-Equation Solver of Linear Complexity for Large-Scale 3D Capacitance and Impedance Extraction," 46th ACM/EDAC/IEEE Design Automation Conference (DAC), pp. 752-757, July 2009. (ONE OF 148 PAPERS ACCEPTED OUT OF 682 PAPERS SUBMITTED)

[2] W. Chai and D. Jiao, "Dense Matrix Inversion of Linear Complexity for Integral-Equation Based 3-D Capacitance Extraction," IEEE Trans. MTT, vol. 59, no. 10, pp. 2404-2421, Oct. 2011.

[3] W. Chai and D. Jiao, "Direct Matrix Solution of Linear Complexity for Surface Integral-Equation Based Impedance Extraction of High Bandwidth Interconnects," the 48th ACM/EDAC/IEEE Design Automation Conference (DAC), pp. 206-211, June, 2011. (ONE OF THE 156 PAPERS ACCEPTED OUT OF 690 SUBMITTED)

[4] W. Chai and D. Jiao, "Direct Matrix Solution of Linear Complexity for Surface Integral-Equation Based Impedance Extraction of Complicated 3-D Structures," invited paper, Proceedings of the IEEE, Special Issue on "Large Scale Electromagnetic Computation for Modeling and Applications," vol. 101, no. 2, pp. 372-388, Feb. 2013.

[5] W. Chai and D. Jiao, "An LU Decomposition Based Direct Integral Equation Solver of Linear Complexity and Higher-Order Accuracy for Large-Scale Interconnect Extraction," IEEE Trans. Advanced Packaging, vol. 33, no. 4, pp. 794-803, 2010.

[6] W. Chai and D. Jiao, "Linear-Complexity Direct and Iterative Integral Equation Solvers Accelerated by a New Rank-Minimized H2-Representation for Large-Scale 3-D Interconnect Extraction," IEEE Trans. Microw. Theory Tech, vol. 61, no. 8, pp. 2792-2805, Aug. 2013.

[7] S. Omar and D. Jiao, "A Linear Complexity Direct Volume Integral Equation Solver for Full-wave 3-D Circuit Extraction in Inhomogeneous Materials," accepted for publication, IEEE Trans. Microw. Theory Tech., 2015.


Direct Integral Equation Solvers for Electrically Large Analysis:

 

Unlike electrically small problems, the rank of an electrodynamic IE operator increases with electric size for achieving a prescribed accuracy, which results in a higher computational complexity if no advanced algorithms are conceived to effectively manage the rank's growth with electric size. The true indicator of this rank's growth is singular value decomposition (SVD), which is computationally O(N^3) and is thus not used explicitly.

Prevailing source-observer separated representations of the IE operator adopted by existing fast IE solvers do not lead to a minimal rank representation required by accuracy. These representations include interpolation-based, Taylor series expansion based, plane wave expansion based methods, etc. In fact, these representations result in a full-rank representation of the IE operator for electrically large problems, which makes the compression of the IE operator sub-optimal for general electrodynamic analysis.

In view of the pivotal importance of the rank of the off-diagonal blocks in an IE operator, we have carried out a theoretical study on its growth with electric size in integral equations. The significance of this study lies in the fact that it derives a closed-form analytical expression of the rank of the coupling Green's function, which has the same scaling as that depicted by SVD-based rank revealing. The findings on the rank are summarized as follows:

1- The rank (r) of the off-diagonal block, irrespective of the electric size, is far less than the size of the block (m), thus the off-diagonal block has a low rank representation i.e. r << m.

2- For electrically small and one-dimensional configurations of sources and observers, the rank required by a prescribed accuracy remains constant irrespective of the problem size.

3- For 2- and 3-D configurations, the rank varies as square root of logarithm and linearly with the electric size, respectively.

Based on the above findings, we have developed fast direct integral equation solvers for electrically large analysis. In our direct surface IE solvers, a dense matrix for a 96-wavelength problem with over 1 million unknowns was directly factorized in 20 hours with 85-seconds LU solution time on a single 3 GHz CPU core. In our electrically large volume IE solver, we have achieved O(N) complexity in matrix-vector multiplication, and O(NlogN) complexity in inverse irrespective of electrical size.

Selected Publications:

[1] W. Chai and D. Jiao, "A Theoretical Study on the Rank of Integral Operators for Broadband Electromagnetic Modeling from Static to Electrodynamic Frequencies," IEEE Trans. on Components, Packaging and Manufacturing Technology, vol. 3, no. 12, pp. 2113-2126, December 2013.

[2] W. Chai and D. Jiao, "A Complexity-Reduced H-Matrix Based Direct Integral Equation Solver with Prescribed Accuracy for Large-Scale Electrodynamic Analysis," the 2010 IEEE International Symposium on Antennas and Propagation, 4 pages, July 2010.

[3] W. Chai and D. Jiao, "A Complexity-Reduced H-Matrix Based Direct Integral Equation Solver with Prescribed Accuracy for Large-Scale Electrodynamic Analysis," TR-ECE-11-04, School of Electrical Engineering, Purdue University, Feb. 2011, 20 pages.

[4] W. Chai and D. Jiao, "A New H2-Matrix-Based Representation of Electrodynamic Systems with Minimized Rank and Prescribed Accuracy," IEEE Int. Symp. Antennas and Propagation, July 2010.

[5] S. Omar and D. Jiao, "O(N) Iterative and O(NlogN) Direct Volume Integral Equation Solvers for Large-Scale Electrodynamic Analysis," ICEAA, pp. 593-596, 2014.


Low-Frequency Breakdown:

 

RCS of a sphere at 1e-32 Hz    A full-wave solution of Maxwell's equations breaks down at low frequencies, which was observed as early as when the area of Computational EM came into existence. The same breakdown is observed when there exist dense discretizations or fine features relative to working wavelength. This problem is very critical in today's engineering problems analyzed via EM simulators. This is not only because the breakdown frequency of full-wave solvers can fall right within the operating frequencies of an engineering product, but also because there could exist a range of frequencies in which the solution to Maxwell's equations is unknown, since a full-wave solver breaks down while static- and quasi-static solutions are invalid especially in highly multiscaled problems. The root cause of low-frequency breakdown is finite machine precision, thus the problem is very challenging to solve. We are able to overcome the barrier imposed by the finite machine precision, and successfully find the solution to the original full-wave system of equations from an arbitrarily high electrodynamic frequency all the way down to zero frequency. Our solution is applicable to both PDE- and IE-based methods.   A fast method is also developed to speed up the low-frequency computation in a reduced system of O(1). Moreover, we have demonstrated, both theoretically and numerically, that although the problem is termed low-frequency breakdown, the solution at breakdown frequencies can be a full-wave solution for which static and quasi-static assumptions are invalid for use. This is especially true in multi-scale problems, the geometrical scales of which are many orders of magnitude different. The upper right figure illustrates the RCS of a sphere of 1 m radius at 1e-32 Hz generated by the proposed method in comparison with analytical data. The lower left figure shows the electric field distribution of an on-chip interconnect structure at 1 Hz generated by the proposed method (upper subfigure) in comparison with the field distribution obtained by a conventional method (lower subfigure).

[1] J. Zhu and D. Jiao, "A Theoretically Rigorous Full-Wave Finite-Element-Based Solution of Maxwell's Equations from DC to High Frequencies," IEEE Trans. Advanced Packaging, vol. 33, no. 4, pp. 1043-1050, 2010.

[2] J. Zhu and D. Jiao, "A Rigorous Solution to the Low-Frequency Breakdown in Full-Wave Finite-Element-Based Analysis of General Problems Involving Inhomogeneous Lossless/Lossy Dielectrics and Non-ideal Conductors," IEEE Trans. MTT, vol. 59, no. 12, pp. 3294-3306, Dec. 2011.

[3] J. Zhu and D. Jiao, "A Fast Full-Wave Solution that Eliminates the Low-Frequency Breakdown Problem in a Reduced System of Order One," IEEE Trans. on Components, Packaging, and Manufacturing Technology, vol. 2, no. 11, pp. 1871 - 1881, 2012.

[4] J. Zhu, S. Omar and D. Jiao, "Solution of the Electric Field Integral Equation When It Breaks Down," IEEE Trans. Antennas Propagat., vol. 62, no. 8, pp. 4122-4134, Aug. 2014.

[5] J. Zhu and D. Jiao, "Solution to the low-frequency breakdown problem in computational electromagnetics," Chapter 8 in the Computational Electromagnetics: Recent Advances and Engineering Applications edited by Raj Mittra. Springer, 2013, pp. 259-316.


Explicit and Unconditionally Stable Time-Domain Methods:

 

The time-domain methods in computational electromagnetics can be categorized into two classes. One is the explicit time-domain method; the other is the implicit time-domain method. Explicit methods can avoid solving a matrix, while implicit methods generally require a matrix solution. The time step of a traditional explicit method is restricted by the smallest space step for ensuring the stability of a time-domain simulation. Existing unconditionally stable methods are all implicit methods. RCS of a sphere at 1e-32 Hz     This problem has prevented the existing time-domain methods from analyzing large-scale multiscaled problems in feasible run time and memory, where fine features can be orders of magnitude smaller than the largest feature size. In this work, we create explicit time-domain methods that are unconditionally stable, which removes a major limit in time-domain analysis. The method retains the strength of an explicit time-domain method in being matrix free, while eliminating its shortcoming in time step when the smallest space step is small as compared to the working wavelength. In the example shown in the figure, a conventional explicit method requires a time step as small as 1.0363e-15 s to be stable, whereas the time step required by sampling accuracy for the input spectrum is 13 orders of magnitude larger. As shown in the figure, first, the proposed method is stable regardless of the choice of the time step; second, it is capable of using the time step solely determined by sampling accuracy to generate accurate results.

Selected Publications:

[1] Q. He, H. Gan, and D. Jiao, "Explicit Time-Domain Finite-Element Method Stabilized for an Arbitrarily Large Time Step," IEEE Trans. Antennas and Propagation, vol. 60, no. 11, pp. 5240 - 5250, 2012.

[2] M. Gaffar and D. Jiao, "An Explicit and Unconditionally Stable FDTD Method for Electromagnetic Analysis," IEEE Trans. Microw. Theory Tech., vol. 62, no. 11, pp. 2538-2550, Nov. 2014.

[3] M. Gaffar and D. Jiao, "An Alternative Method for Making an Explicit FDTD Unconditionally Stable," IEEE International Microwave Symposium, 2015.

[4] W. Lee and D. Jiao, "A New Explicit and Unconditionally Stable Time-Domain Finite-Element Method," IEEE Int. Symposium Antennas and Propagation, 2015.


Extraction-Free Circuit Simulators:

 

The prevailing circuit simulation paradigm involves first the extraction of the linear network. The extracted model of the linear network is then stitched with the nonlinear devices for the simulation of the entire circuit. Besides various inaccuracy issues due to circuit extraction and the stitching of circuit models, existing circuit simulators have not achieved optimal complexity. We developed an extraction-free circuit simulator that bypasses circuit extraction altogether. Guided by electromagnetics-based first principles, this extraction-free simulator has not only accomplished an optimal complexity both in time and space, but also offered uncompromised accuracy and linear speedup in parallelization, overcoming the shortcomings of the existing extraction-based circuit simulation frameworks. Application to die-package co-simulation as well as very large-scale on-chip circuits involving close to 1 million CMOS transistors and interconnects having hundreds of millions of unknowns has demonstrated the superior performance of the new extraction-free circuit simulator.

Selected Publications:

[1] Q. He, D. Chen, and D. Jiao, "From Layout Directly to Simulation: A First-Principle Guided Circuit Simulator of Linear Complexity and Its Efficient Parallelization," IEEE Trans. on Components, Packaging, and Manufacturing Technology, vol. 2, no. 4, pp. 687 - 699, April 2012.

[2] D. Chen, D. Jiao, and C. Koh, "A Parallel Transient Simulator of Linear Speedup and Electromagnetic Accuracy for the Simulation of Die-Package Interaction," IEEE Trans. on Components, Packaging, and Manufacturing Technology, vol. 1, no. 5, pp. 752-759, May 2011.

[3] D. Chen and D. Jiao, "Time-Domain Orthogonal Finite-Element Reduction-Recovery (OrFE-RR) Method for Electromagnetics-Based Analysis of Large-Scale Integrated Circuit and Package Problems," IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, vol. 28, no. 8, pp. 1138-1149, Aug. 2009.