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.