Numerica
 
<<< Numerica
La libreria numerica di M3E per l'Algebra Lineare
M3E ha sviluppato e mantiene una libreria numerica che colleziona un gran numero di precondizionatori allo stato dell'arte che possono essere usati sia su calcolatori scalari che paralleli. Questi precondizionatori possono essere usati in maniera efficace in combinazione con qualsiasi solutore iterativo per la soluzione di sistemi lineari (Gradiente Coniugato, GMRES, SQMR, Bi-CGStab, etc.) o problemi agli autovalori (DACG, Jacobi-Davidson, Lanczos, etc.). Il precondizionatore è una matrice capace di trasformare un problema "difficile" in un problema "facile", in modo da accelerare la convergenza del solutore e aumentarne la robustezza. La ricerca sulle tecniche di precondizionamento è un campo molto attivo, perché è la chiave per migliorare le prestazioni dei metodi iterativi.


Come esempio, sono riportate le prestazioni di tre precondizionatori paralleli inclusi nella libreria di M3E su 10 matrici di grandi dimensione provenienti dalla collezione pubblica di matrici dell'Università della Florida:
  • Block Jacobi, una fattorizzazione incomplete dei blocchi diagonali della matrice;
  • FSAI, un'inversa approssimata in forma fattorizzata
  • ABF-IC, un precondizionatore ibrido che accoppia un'inversa approssimata ad una fattorizzazione incomplete a blocchi
Mentre Block Jacobi e FSAI sono precondizionatori standard, ABF-IC è una strategia nuova ed originale sviluppata all'interno di M3E. Le prove riportate sono state effettuate in parallelo utilizzando il Gradiente Coniugato come solutore su di un cluster dotato di processori Intel CORE i7 a 2.67 GHz.



Name # of equations # of non-zeroes Problem description Sequential time [s]
G3_circuit 1,585,478 7,660,826 Circuit simulation 28.22
thermal2 1,228,045 8,580,313 Thermal 43.04
ecology2 999,999 4,995,991 2D/3D problem 23.76
bone010 986,703 47,851,783 Model reduction 616.58
Idoor 952,203 42,493,817 Structural 258.32
tmt_sym 726,713 5,080,961 Electromagnetics 22.53
apache2 715,176 4,817,870 Structural 17.32
parabolic_fem 525,825 3,674,625 CFD 8.62
F1 343,791 13,590,452 Structural 235.09
Serena 1,391,349 64,531,701 Structural 137.40

Tabella 1 Nome, dimensione, numero di non-zeri, breve descrizione del problema e tempo di calcolo in scalare per le matrici usate nei test.




Figura 1 Performance dei precondizionatori paralleli JACOBI, FSAI e ABF-IC con 8 (sinistra) e 32 (destra) processori rapportata al tempo di soluzione in scalare.



In Tabella 1 sono riportati nome, dimensione, numero di non-zeri e una breve descrizione delle matrici test. In ultima colonna è riportato il tempo totale di soluzione necessario in scalare utilizzando come precondizionatore una decomposta incompleta che può essere considerata come la performance ottimale in un calcolo sequenziale. La Figura 1 mostra le prestazioni dei precondizionatori Block Jacobi, FSAI e ABF-IC con 8 e 32 processori normalizzate con il tempo di soluzione in sequenziale riportato in Tabella 1. Si noti che la scala verticale del diagramma più a destra è un quarto di quello a sinistra, in modo tale che l'altezza di ciascuna colonna rimanga inalterata per un algoritmo perfettamente parallelo. Block Jacobi non è in grado di risolvere i sistemi relativi a ldoor e F1, ma con 8 core è efficiente su tutti gli altri problemi. Tuttavia, aumentando il numero di core la sua efficienza si deteriora in fretta, in quanto Block Jacobi non è un precondizionatore perfettamente parallelo. Al contrario, FSAI è generalmente meno efficiente ma è efficace su tutte le matrici testate ed è perfettamente parallelelo, infatti aumentando il numero di core le prestazioni di FSAI si avvicinano a quelle di Block Jacobi. Infine, ABF-IC può essere impiegato con successo su tutti i problemi testati e risulta il metodo di soluzione più efficiente. Inoltre, sebbene ABF-IC non sia un precondizionatore perfettamente parallelo, la sua performance risulta sempre superiore a quella di FSAI come si può notare dalla Figura 2 che confronta il tempo di calcolo richiesto da FSAI e ABF-IC su un singolo caso test al variare del numero di processori.



Figura 2 Wall time [s] vs. numero di processori per FSAI e ABF-IC su un singolo caso test.
La linea tratteggiata indica la condizione limite di speed-up perfetto per ABF-IC.




Bibliografia:
L. Bergamaschi, M. Ferronato, G. Gambolati. Novel preconditioners for the iterative solution to FE-discretized coupled consolidation equations. Computer Methods in Applied Mechanics and Engineering, 196, pp. 2647-2656, 2007.
M. Ferronato, C. Janna, G. Gambolati. Mixed constraint preconditioning in computational contact mechanics. Computer Methods in Applied Mechanics and Engineering, 197, pp. 3922-3931, 2008.
C. Janna, M. Ferronato, G. Gambolati. Multilevel incomplete factorizations for the iterative solution of non-linear FE problems. International Journal for Numerical Methods in Engineering, 80, pp. 651-670, 2009.
C. Janna, M. Ferronato, G. Gambolati. A Block FSAI-ILU parallel preconditioner for symmetric positive definite linear systems. SIAM Journal on Scientific Computing, 32, pp. 2468-2484, 2010.
C. Janna, M. Ferronato. Adaptive pattern research for Block FSAI preconditioning. SIAM Journal on Scientific Computing, to appear.
Chi siamo
La società
- Profilo dei soci
- Partner industriali
Attività
Modellistica
- Geomeccanica
- Idrologia sotterranea
- Qualità dell'aria
Numerica
Ottimizzazione
Partner
I nostri partner
News
Archivio notizie
Download
Contratti
Opportunità di lavoro
Contatti
Contatti