Teoria dei Grafi

La soluzione efficiente di sistemi lineari è il collo di bottiglia computazionale per la maggior parte dei metodi numerici elettromagnetici.
Un esempio è rappresentato dal caso del mode-matching.
Sebbene questo metodo è estremamente semplice ed efficiente, quando vengono simulati circuiti molto complessi, il tempo di CPU necessario diventa sorprendentemente lungo.
La teoria dei grafi è un approccio efficace per migliorare l’efficienza dei metodi numerici. L’idea base è la rappresentazione della matrice A nel sistema lineare con un cosiddetto “grafo di adiacenza”, un grafo in cui per ogni riga/colonna della matrice viene creato un nodo, e nodo i e nodo j sono connessi se e solo se l’elemento aij nella matrice non è zero.
Un esempio è riportato nella figura:

GraphTheory

 

Grazie ad uno speciale algoritmo, sviluppato da questo gruppo di ricerca, è possibile stimare con grande efficienza la matrice P di permutazione, così che il risultato della matrice PAPT è una matrice bandata con una minima larghezza di banda. Questo permette una forte riduzione del tempo di simulazione, come pure un miglioramento delle proprietà numeriche della matrice stessa.
L’efficacia sostanziale degli approcci è stata provata su diversi circuiti analizzati con diversi metodi numerici, come il mode-matching, FEM, metodo dei momenti, etc..
Il gruppo ha inoltre messo a punto una specifica tecnica, chiamata Adjacence-graph Recursive-thresholding (AG-RT) che trasforma un singolo sistema di grandi dimensioni, denso, e con cattivo condizionamento, in una varietà di sottosistemi piccoli, ben condizionati ed indipendenti, con rilevanti vantaggi per il tempo di soluzione richiesto, anche su piattaforme a basso costo.