Graph Theory

The efficient solution of a linear system is the computational core for the majority of electromagnetic numerical methods. An example is represented by the mode-matching case. Though this method is extremely fast, when complex circuits are simulated, the CPU time can become surprisingly long.
Graph theory is an effective approach to improve the efficiency of numerical methods. The basic idea is the representation of the matrix A in the linear system with a so-called “adjacence graph”, a graph where for each row/column a node is created, and node i and j are connected if and only if the entry a ij in the matrix is not zero.
An example is reported in the figure.



Thanks to special algorithms, developed by the group, the suitable handling of the graph allows the evaluation of a permutation matrix P, so that the resulting matrix PAP T is a banded matrix, with minimum bandwidth. This allows a strong reduction in simulation times, as well as an improvement in the condition number of the matrix itself.

The substantial effectiveness of the approach has been proved on several circuits and for different numerical methods, namely mode-matching, FEM, method-of-moments, etc.

The group has also developed a specific technique, called Adjacence-graph Recursive-thresholding (AG-RT) which turns a single, large and bad-conditioned problem into a variety of smaller and well-conditioned independent subproblems, with relevant advantages both for the solution time, and for the affordability of the simulation on entry-level platforms.