Sparse Approximate Inverse per il precondizionamento di matrici = Sparse Approximate Inverse for matrix preconditioning

Una caratteristica fondamentale di ogni sistema lineare è il suo numero di condizionamento, che è definito mediante la matrice del sistema. Tale quantità è strettamente connessa alla stabilità del processo risolutivo e all'accuratezza della soluzione ottenuta. Proprio per questo motivo si introducono i precondizionatori, costruiti per ottimizzare il condizionamento di un sistema lineare. I precondizionatori del tipo Sparse Approximate Inverse costituiscono una nuova categoria di precondizionatori, nati dall'idea di minimizzare, in norma di Frobenius, la differenza fra la matrice del sistema lineare A e la matrice identità, attraverso una matrice M sparsa che approssima l'inversa di A. Da questa idea si sviluppano gli algoritmi SPAI, ideato per matrici generiche, e FSAI, ideato per matrici simmetriche definite positive. L'input principale di questi algoritmi è lo sparsity pattern di M, e partendo da uno sparsity pattern predefinito, si risolve il problema di minimizzazione per ottenere M. In questo studio si presenteranno i due algoritmi citati e alcune procedure comunemente adottate per ottenere un'euristica sullo sparsity pattern in input. Si osserverà inoltre, dall'esposizione degli algoritmi stessi, che grazie alle proprietà della norma di Frobenius il problema di minimizzazione è suddivisibile in sottoproblemi indipendenti, rivelando quindi la natura intrinsecamente parallela degli algoritmi SPAI e FSAI, ed evidenziando dunque il loro potenziale uso in sistemi di calcolo paralleli.