Area Scientifico Disciplinare: Scienze Matematiche

Fabio Di Benedetto, nato a La Spezia il 17/5/1963, ha conseguito la laurea in Matematica nel 1987 presso l'Università di Pisa con la votazione finale di 110/110 e lode. Dopo alcune borse di studio CNR, ha vinto nel 1990 il concorso per Ricercatore di Analisi Numerica presso il Dipartimento di Matematica dell'Università di Genova; dal 2000 è Professore Associato di Analisi Numerica presso lo stesso Dipartimento.
Svolge dal 1994 corsi di Calcolo Numerico per i corsi di laurea e diploma in Informatica, Scienze dei Materiali e Matematica, ed è relatore di numerose tesi di laurea in Matematica. È stato inoltre supervisore di una tesi di dottorato in Matematica Computazionale e Ricerca Operativa.
I suoi principali interessi di ricerca riguardano l'algebra lineare numerica e in particolare le matrici strutturate (ad esempio le matrici di Toeplitz) e le relative applicazioni all'elaborazione di immagini. È autore e coautore di circa 25 articoli e svolge attività di referee per il Mathematical Reviews e per le riviste internazionali SIAM Journal on Numerical Analysis, SIAM Journal on Matrix Analysis and Applications, SIAM Journal on Scientific Computing, Linear Algebra and its Applications, BIT e Calcolo.
Ha collaborato all'organizzazione di due Workshop INDAM sulle matrici strutturate svoltisi a Cortona nel 1996 (curando la pubblicazione dei relativi proceedings) e nel 2000.

1. DI BENEDETTO F. (1995). Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices. SIAM JOURNAL ON SCIENTIFIC COMPUTING. vol. 16, pp. 682-697.
2. DI BENEDETTO F., SERRA CAPIZZANO S. (1999). A unifying approach to abstract matrix algebra preconditioning. NUMERISCHE MATHEMATIK. vol. 82, pp. 57-90.
3. DI BENEDETTO F. (1997). Generalized updating problems and computation of the eigenvalues of rational Toeplitz matrices. LINEAR ALGEBRA AND ITS APPLICATIONS. vol. 267, pp. 187-219.
4. BERTERO M., BOCCACCI P., DI BENEDETTO F., ROBBERTO M. (1999). Restoration of chopped and nodded images in infrared astronomy. INVERSE PROBLEMS. vol. 15, pp. 345-372.
5. D. BINDI, P. BRIANZI, DI BENEDETTO F. (2002). A Fourier approach to the natural pixel discretization of brain single-photon emission computed tomography. INTERNATIONAL JOURNAL OF IMAGING SYSTEMS AND TECHNOLOGY. vol. 12-1, pp. 1-8.

1.7.2 Personale universitario di altre Università

Nº	Cognome	Nome	Università	Dipart./Istituto	Qualifica	Settore scient.	Mesi uomo
							2002	2003
Personale docente:
1	BERTACCINI	DANIELE	ROMA "La Sapienza"	MATEMATICA	Ricercatore	MAT/08	7 (ore: 959)	3 (ore: 411)
2	FASINO	DARIO	UDINE	MATEMATICA E INFORMATICA	Prof. associato	MAT/08	8 (ore: 1100)	5 (ore: 685)
3	SERRA CAPIZZANO	STEFANO	INSUBRIA	SCIENZE CHIMICHE, FISICHE E MATEMATICHE	Prof. associato	MAT/08	8 (ore: 1100)	5 (ore: 685)
4	TABLINO POSSIO	CRISTINA	MILANO-BICOCCA	MATEMATICA E APPLICAZIONI	Ricercatore	MAT/08	8 (ore: 1100)	5 (ore: 685)
Altro personale:

1.7.3 Titolari di assegni di ricerca

Nº	Cognome	Nome	Dipart./Istituto	Anno del titolo	Mesi uomo
					2002	2003

1.7.4 Titolari di borse per Dottorati di Ricerca e ex L. 398/89 art.4 (post-dottorato e specializzazione)

Nº	Cognome	Nome	Dipart./Istituto	Anno del titolo	Mesi uomo

1.7.5 Personale a contratto da destinare a questo specifico programma

Nº	Qualifica	Costo previsto	Mesi uomo
1.	assegno di ricerca	15000	11  (ore: 1507)

1.7.6 Personale extrauniversitario dipendente da altri Enti

Nº	Cognome	Nome	Ente	Qualifica	Mesi uomo
1.	ESTATICO	CLAUDIO	Mediacons Srl	tecnico informatico	8  (ore: 1100)

Tecniche iterative per matrici strutturate: applicazioni a PDE, immagini e problemi di approssimazione

---

2.2 Settori scientifico-disciplinari interessati dal Programma di Ricerca

MAT/08 - ANALISI NUMERICA INF/01 - INFORMATICA

---

2.3 Parole chiave 

MATRICI DI TOEPLITZ ; PRECONDIZIONAMENTO PER MATRICI STRUTTURATE ; MULTIGRID PER MATRICI STRUTTURATE ; MATRICI CON STRUTTURA ; IMMAGINI LBT ; SPECT

---

2.4 Base di partenza scientifica nazionale o internazionale

Testo italiano

La comprensione delle matrici strutturate di tipo Toeplitz ha ricevuto negli ultimi anni un forte impulso da parte di svariati gruppi di ricerca in algebra lineare numerica. Si sono affermate in particolare due principali direttrici di ricerca: la prima, più teorica, riguarda lo studio di proprietà spettrali di successioni di matrici strutturate; la seconda, più applicativa, è legata alla ricerca di solutori di Toeplitz efficienti.

Per ciò che concerne le proprietà spettrali, di sicura importanza sono i risultati distribuzionali di Szego, Widom, Avram, Parter (si veda [14]), culminati nel lavoro di Tyrtyshnikov [55] e riguardanti il "comportamento globale" degli spettri di successioni di Toeplitz. In letteratura sono presenti estensioni al caso di generatrici a valori matriciali ed a successioni provenienti dal precondizionamento [40,41,25], oltre ad applicazioni all'approssimazione e alla quadratura [45]. Altra importante estensione concerne il caso di strutture che sono "solo localmente" Toeplitz [52] o che possiedono altre "strutture locali" [44] e che contengono come casi particolari discretizzazioni di equazioni differenziali con condizioni al contorno [47] e matrici di grafo [44].
Un ulteriore settore di interesse, anche applicativo per il suo ovvio impatto sullo studio del condizionamento asintotico, è quello dello studio dei valori singolari/autovalori estremi (si veda [14,39,41,49] e relativi riferimenti).

Per ciò che concerne i metodi numerici, sono stati recentemente conseguiti risultati pressoché definitivi nel costruire algoritmi sempre più efficienti per la soluzione di sistemi lineari e di problemi ai minimi quadrati.
Le prime tecniche specializzate sono quelle che vanno sotto il nome di metodi "fast" e "superfast". Si tratta di metodi diretti che riducono il costo ad O(n²) e O(n log²(n)) operazioni aritmetiche dove n è la dimensione. Per una esaustiva analisi di tali metodi, spesso basati sulla nozione di "rango di dislocamento", si veda [30] e gli oltre 100 titoli citati in bibliografia, ed il libro [13].
Un ulteriore miglioramento, almeno nel caso bencondizionato, è rappresentato dall'uso del Gradiente Coniugato Precondizionato (PCG). Una tipica scelta fissa il precondizionatore nell'algebra di tutte le matrici diagonalizzate tramite una trasformata veloce prefissata: le circolanti, associate alla trasformata discreta di Fourier (che Strang [51] propose per primo nel 1986), sono la scelta più comune, per quanto anche le trasformate trigonometriche siano state recentemente prese in considerazione [11,29].
Il risultato è un clustering forte nel caso unilivello per ogni generatrice continua, mentre nel caso multilivello il clustering forte è molto raro e le proprietà di clustering si deteriorano man mano che il numero di livelli aumenta. La situazione è in realtà anche peggiore perché i lavori [50,46] provano che questo tipo di clustering è il migliore possibile, almeno quando si usino precondizionatori in algebre.
Per il caso malcondizionato l'analisi è più complessa ed infatti molti dei metodi "fast" e "superfast" soffrono di problemi di stabilità e molti dei precondizionatori proposti non sono più ottimali. A questo proposito R.Chan e Di Benedetto, Fiorentino e Serra Capizzano introducono una ulteriore tecnica di precondizionamento che si basa su matrici di Toeplitz a banda [16] e che conduce a metodi ottimali e superlineari [38] di costo O(n log(n)) per sistemi definiti positivi con condizionamento polinomiale, o solo ottimali per il caso non definito [37].
È importante osservare che tale tecnica di precondizionamento a banda è naturalmente estendibile al caso multilivello [36]. Quindi il problema è quello di trovare buoni solutori per sistemi di Toeplitz a banda e multilivello. La tecnica [12] non è più ottimale (anche se rimane "quasi lineare" in costo), mentre il metodo multigrid sembra essere ottimale [26]. Sulla base di tali premesse uno degli obiettivi principali nel progetto di future ricerche sarà quello di indagare metodi multigrid ottimali per il caso specifico di strutture a banda e multilivello (con condizionamento polinomiale).

Dal punto di vista applicativo, molte situazioni concrete richiedono la soluzione in tempi brevi di problemi matematici di grosse dimensioni, caratterizzati dalla presenza (talvolta nascosta) di strutture matriciali; tra le più importanti, vanno segnalati i problemi inversi legati all'elaborazione di immagini, le equazioni alle derivate parziali (PDE), l'approssimazione di funzioni.

Tutti i metodi numerici usati nel campo delle immagini devono tenere presente che è necessaria una qualche forma di regolarizzazione. Il precondizionamento in algebre matriciali è stato applicato con successo alla ricostruzione di immagini atmosferiche, tramite risoluzione con PCG di un problema ai minimi quadrati legato alla regolarizzazione di Tykhonov (si veda ad esempio [34]) oppure mediante la definizione di un precondizionatore dipendente da un parametro, avente di per sè effetto regolarizzante [28].
Una recentissima tecnica di imaging che richiede di risolvere problemi di ricostruzione particolarmente difficili è il Large Binocular Telescope (LBT) [1]. Il problema matematico alla base è la ricostruzione di immagini multiple di circa 10⁸ pixel, e necessita pertanto di metodi numerici efficienti.
Un altro problema interessante della ricostruzione di immagini, che richiede la risoluzione di sistemi di grosse dimensioni, è la cosiddetta tomografia SPECT [33]. Il volume dei dati è in questo caso dell'ordine di 10⁶, ma le strutture matriciali presenti sono più nascoste.

La struttura di Toeplitz a banda è l'ingrediente principale per una tecnica di precondizionamento superlineare [42,47] per discretizzazioni a Differenze Finite di equazioni differenziali ellittiche al contorno con coefficienti non costanti. La tecnica assicura un cluster forte ed equivalenza spettrale almeno nei casi in cui i coefficienti siano di classe C². Inoltre le sperimentazioni numeriche suggeriscono che la tecnica è ottimale anche qualora l'equazione sia degenere (non strettamente ellittica).
La discretizzazione alle differenze finite di problemi di evoluzione con formule multistep lineari ai valori al bordo determina matrici non simmetriche di Toeplitz a blocchi perturbate [3]. Precondizionatori tipo-circolanti per tali problemi sono stati introdotti in [4]. Tali precondizionatori sono efficaci [5], purché la norma della relativa inversa abbia al più crescita lineare con la dimensione delle componenti.

Infine, vari problemi di approssimazione polinomiale e razionale (come il problema di Nevanlinna-Pick [35]) si lasciano descrivere in termini di matrici strutturate, tra cui le classi di Cauchy, Pick, Vandermonde e localmente Toeplitz. Le relative proprietà spettrali forniscono una più profonda comprensione del comportamento numerico degli algoritmi usati per risolvere i problemi da cui sono originate.

L'unità operativa, comprendente sette matematici e un'informatica, è caratterizzata da una prolungata esperienza di ricerca nei campi dell'analisi spettrale di ampie classi di matrici strutturate [24,25,44,49], della risoluzione di sistemi lineari di Toeplitz [19,20,22,23,37,43] e problemi agli autovalori [10,21], della regolarizzazione di problemi inversi che intervengono in molteplici applicazioni [15,6]. Nell'unità sono anche presenti competenze specifiche e fondamentali sul trattamento numerico di PDE [47,48] e sull'applicazione delle matrici strutturate alle immagini mediche [9] ed astronomiche [8] e a problemi differenziali dipendenti dal tempo [4,5].

---

2.4.a Riferimenti bibliografici

[1] J.Angel, J.Hill, P.Strittmatter, P.Salinari, G.Weigelt, Interferometry with the Large Binocular Telescope. Proc. SPIE 3352(1998), 881-889
[2] O.Axelsson, V.Barker, Finite Element Solution of Boundary Value Problems, Theory and Computation. Academic Press, NY, 1984
[3] O.Axelsson, J.Verwer, Boundary value techniques for initial value problems in ordinary differential equations. Math. Comp. 45(1985), 153-171
[4] D.Bertaccini, A circulant preconditioner for the systems of LMF-based ODE codes. SIAM J. Sci. Comp. 22(2000), 767-786
[5] D.Bertaccini, Reliable preconditioned iterative linear solvers for some numerical integrators. Num. Lin. Alg. Appl. 8(2001), 111-125
[6] M.Bertero, P.Boccacci, Introduction to Inverse Problems in Imaging, IOP Publ., Bristol, 1998
[7] M.Bertero, P.Boccacci, Image restoration methods for the Large Binocular Telescope (LBT). Astronomy and Astrophysics 147(2000), 323-332
[8] M.Bertero, P.Boccacci, F.Di Benedetto, M.Robberto, Restoration of chopped and nodded images in infrared astronomy. Inverse Problems 15(1999), 345-372
[9] D.Bindi, P.Brianzi, F.Di Benedetto, A Fourier approach to the natural pixel discretization of brain single-photon emission computed tomography. Int. J. of Imaging Syst. and Technol. 12(2002), 1-8
[10] D.Bini, F.Di Benedetto, Solving the generalized eigenvalue problem for rational Toeplitz matrices. SIAM J. Matrix Anal. Appl. 11(1990), 537-552
[11] D.Bini, F.Di Benedetto, A new preconditioner for the parallel solution of positive definite Toeplitz linear systems. Proc. 2nd SPAA conf. Crete (Greece), 1990, 220-223
[12] D.Bini, B.Meini, Effective methods for solving banded Toeplitz systems. SIAM J. Matrix Anal. Appl. 20(1999), 700-719
[13] D.Bini, V.Pan, Polynomial and Matrix Computation: Vol.1, Fundamental Algorithms. Birkauser, Boston, MA, 1994
[14] A.Boettcher, B.Silbermann, Introduction to Large Truncated Toeplitz Matrices. Springer, NY, 1999
[15] P.Brianzi, A criterion for the choice of a sampling parameter in the problem of Laplace transform inversion. Inverse Problems 10(1994), 55-61
[16] R.Chan, M.Ng, Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38(1996), 427-482
[17] R.Chan, D. Potts, G. Steidl, Preconditioners for nondefinite Hermitian Toeplitz systems. SIAM J. Matrix Anal. Appl. 22(2000), 647-665
[18] M.Chu, A simple application of the homotopy method to symmetric eigenvalue problems. Linear Algebra Appl. 59(1984), 85-90
[19] F.Di Benedetto, Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices. SIAM J. Sci. Comp. 16(1995), 682-697
[20] F.Di Benedetto, Preconditioning of block Toeplitz matrices by sine transforms. SIAM J. Sci. Comp. 18(1997), 499-515
[21] F.Di Benedetto, Generalized updating problems and computation of the eigenvalues of rational Toeplitz matrices. Linear Algebra Appl. 267(1997), 187-219
[22] F.Di Benedetto, Solution of Toeplitz normal equations by sine transform based preconditioning. Linear Algebra Appl. 285(1998), 229-255
[23] F.Di Benedetto, S.Serra Capizzano, A unifying approach to abstract matrix algebra preconditioning. Numer. Math. 82(1999), 57-90
[24] D.Fasino, L.Gemignani, Structural and computational properties of possibly singular semiseparable matrices. Linear Algebra Appl. 340(2002), 183-198
[25] D.Fasino, P.Tilli, Spectral properties of block multilevel Hankel matrices. Linear Algebra Appl. 306(2000), 155-163
[26] G.Fiorentino, S.Serra Capizzano, Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions. SIAM J. Sci. Comp. 17(1996), 1068-1081
[27] I.Gohberg, I.Koltracht, Miwed, componentwise, and structured condition numbers. SIAM J. Matrix Anal. Appl. 14(1993) 688-704
[28] M.Hanke, J.Nagy, R.Plemmons, Preconditioned iterative regularization for ill-posed problems. Numerical Linear Algebra and Scientific Computing, de Gruyter, 1993, 141-163
[29] T.Kailath, V.Olshevsky, Displacement structure approach to discrete-trigonometric-transform based preconditioners of G.Strang type and T.Chan type. Calcolo 33(1996), 191-208
[30] T.Kailath, A.Sayed, Displacement structure: theory and applications. SIAM Rev. 37(1995), 297-386
[31] S.Kim, S.Parter, Preconditioning Chebyshev spectral collocation by Finite-Difference operators. SIAM J. Num. Anal. 34(1997), 939-958
[32] A.Kuijlaars, S.Serra Capizzano, Asymptotic zero distribution of orthogonal polynomials with discontinuously varying recurrence coefficients. J. Approx. Theory 113(2001), 142-155
[33] R.Jaszczak, K.Greer, C.Floyd Jr, C.Harris, R.Coleman, Improved SPECT quantitation using compensation for scattered photons. J. Nucl. Med. 25(1984), 893-900
[34] J.Nagy, V.Pauca, R.Plemmons, T.Torgersen, Degradation reduction in optics imagery using Toeplitz structure. Calcolo 33,(1996), 269-288
[35] D.Sarason, Nevanlinna-Pick interpolation with boundary data. Int. Eq. Op. Theory 30(1998), 231-250
[36] S.Serra Capizzano, Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems. BIT 34(1994), 579-594
[37] S.Serra Capizzano, Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions. SIAM J. Matrix Anal. Appl. 17(1996), 1007-1019
[38] S.Serra Capizzano, Optimal, quasi-optimal and superlinear preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems. Math. Comp. 66(1997), 651-665
[39] S.Serra Capizzano, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices. Linear Algebra Appl, 270(1998), 109-129
[40] S.Serra Capizzano, An ergodic theorem for classes of preconditioned matrices. Linear Algebra Appl. 282(1998), 161-183
[41] S.Serra Capizzano, Asymptotic results on the spectra of block Toeplitz preconditioned matrices. SIAM J. Matrix Anal. Appl. 20(1998), 31-44
[42] S.Serra Capizzano, The rate of convergence of Toeplitz based PCG methods for second order nonlinear boundary value problems. Numer. Math. 81(1999), 461-495
[43] S.Serra Capizzano, Superlinear PCG methods for symmetric Toeplitz systems. Math. Comp. 68(1999), 793-803
[44] S.Serra Capizzano, Locally X matrices, spectral distributions, preconditioning and applications. SIAM J. Matrix Anal. Appl. 21(2000), 1354-1388
[45] S.Serra Capizzano, Korovkin tests, approximation, and ergodic theory. Math. Comp. 69(2000), 1533-1558
[46] S.Serra Capizzano, Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear. Linear Algebra Appl. 343/344(2002), 303-319
[47] S.Serra Capizzano, C.Tablino Possio, Spectral and structural analysis of high precision Finite Difference matrices for elliptic operators. Linear Algebra Appl. 293(1999), 85-131
[48] S.Serra Capizzano, C.Tablino Possio, Finite Element matrix-sequences: the case of rectangular domains. Numer. Alg. 28(2001), 309-327
[49] S.Serra Capizzano, P.Tilli, Extreme singular values and eigenvalues of non Hermitian Toeplitz matrices. J. Comp. Appl. Math. 108(1999), 113-130
[50] S.Serra Capizzano, E.Tyrtyshnikov, Any circulant-like preconditioner for multilevel matrices is not superlinear. SIAM J. Matrix Anal. Appl. 21(1999), 431-439.
[51] G.Strang, A proposal for Toeplitz matrix calculations. Stud. Appl. Math. 74(1986), 171-176
[52] P.Tilli, Locally Toeplitz sequences: spectral properties and applications. Linear Algebra Appl. 278(1998), 91-120
[53] W.Trench, Numerical solution of the eigenvalue problem for Hermitian Toeplitz matrices. SIAM J. Matrix Anal. Appl. 10(1989), 135-146
[54] E.Tyrtyshnikov, Optimal and superoptimal circulant preconditioners. SIAM J. Matrix Anal. Appl. 13(1992), 459-473
[55] E.Tyrtyshnikov, N.Zamarashkin, Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships. Linear Algebra Appl. 270(1998), 15-27
[56] D.Watkins, L.Elsner, Self-similar flows. Linear Algebra Appl. 110(1988), 213-242

---

2.5 Descrizione del programma e dei compiti dell'Unità di Ricerca

Per quanto visto nella Base di Partenza, le principali competenze dell'unità investono le matrici strutturate (Toeplitz in particolare), i metodi iterativi, le PDE e i problemi inversi. Il progetto si propone di studiare problemi ancora aperti all'interno di questi filoni, e creare allo stesso tempo nuovo feedback tra gli stessi. In particolare si vuole analizzare i casi multilivello e non Hermitiano per il loro naturale occorrere nella discretizzazione di problemi che coinvolgano domini a più dimensioni (PDE, equazioni integrali con particolare attenzione al problema del restauro di immagini, etc.) e per la loro difficoltà intrinseca: si noti che i problemi aperti più rilevanti nel campo dei metodi iterativi riguardano proprio i casi non Hermitiano, Hermitiano non definito e multilivello.
All'interno di questa classe di problemi si vuole focalizzare l'attenzione su tre direttrici principali: Analisi di successioni di matrici [in parziale collaborazione con R.Bhatia, Indian Statistical Institute - New Delhi, P.Tilli, Scuola Normale Superiore di Pisa e E.Tyrtyshnikov, Russian Academy of Sciences - Mosca]; Analisi e Sintesi di algoritmi ad hoc per matrici strutturate [in parziale collaborazione con B.Beckermann, Université Lille 1, il gruppo di R.Chan, Chinese University of Hong Kong, A.Frangioni, Università di Pisa, A.Kuijlaars, KU Lovanio e T.Huckle, TU Monaco]; Applicazioni a problemi specifici della Matematica Applicata [in parziale collaborazione con il gruppo di R.Chan e l'U.O. numero 1]; è anche prevista la stesura di codici software prototipali, come descritto nel seguito.
 

A) Aspetti teorici
 

Il progetto collegherà i campi dell'analisi di convergenza per metodi di tipo Krylov, dell'algebra lineare asintotica e della teoria degli operatori, con particolare riguardo agli operatori di regolarizzazione per problemi inversi.
 

A1) Convergenza dei metodi iterativi
La discretizzazione di alcune PDE porta a sistemi lineari Hermitiani non definiti (come l'equazione di Helmholtz) o non Hermitiani (come i problemi evolutivi). Si prevedono per questi casi risultati asintotici e di localizzazione sullo spettro di strutture precondizionate e non. In particolare, saranno studiati i casi di matrici Toeplitz-like a blocchi precondizionate da matrici circolanti a blocchi, oppure di Toeplitz a banda. Si vogliono provare relazioni tra queste proprietà e la velocità di metodi tipo Krylov quali GMRES e i BiCG, insieme a stime di convergenza.
 

A2) Algebra lineare asintotica
Data una successione di matrici A_n e considerata la misura discreta ottenuta come media aritmetica di Delta di Dirac centrate sui valori singolari di A_n, si vuole individuarne (se esiste) la distribuzione limite.
a) Estensione della nozione di successione Localmente Toeplitz (si veda [52]), che è inerentemente unilivello, al caso multilivello considerando anche una sorta di chiusura topologica. L'interesse consta nel fatto che tale nozione estesa permette di studiare in modo unificato e completo la distribuzione limite di qualsivoglia successione di matrici discretizzanti Equazioni a Derivate Parziali su domini semplicemente Peano-Jordan misurabili, con qualsivoglia condizioni al contorno e con metodi di discretizzazione a Differenze Finite (FD) o Elementi Finiti (FE), oltre alle corrispondenti matrici precondizionate, con conseguente applicazione alla valutazione della velocità di convergenza di opportuni metodi PCG.
b) Estensione della classe delle funzioni Test nei risultati distribuzionali per successioni di Toeplitz. Ad esempio se la generatrice f è di classe L^p allora le uniche condizioni sulle funzioni Test saranno la continuità e un'opportuna crescita asintotica. Ciò permetterebbe di ottenere stime asintotiche precise sulla crescita delle norme Schatten p con conseguenti applicazioni allo studio di clustering per precondizionamento in algebra.
c) Studio del condizionamento classico di matrici Laplaciane di Grafo che intervengono come sottoproblemi nell'applicazione di metodi "Interior Point" per la risoluzione di problemi di ottimizzazione vincolata. Si studierà inoltre il condizionamento strutturato [27] per matrici con struttura di dislocamento (Cauchy, Vandermonde); se in tali casi la risoluzione numerica viene effettuata con certi algoritmi veloci in grado di sfruttare opportunamente tali strutture, il numero di condizionamento classico spesso fornisce stime di errore molto pessimistiche, in quanto in tali casi gli errori algoritmici sono modellabili tramite perturbazioni sui dati iniziali che ne preservano la struttura.
 

A3) Relazioni con la teoria degli operatori
Un primo studio riguarda le connessioni tra i problemi infinito dimensionali espressi nel linguaggio di Teoria degli Operatori (secondo l'approccio di Boettcher e Silbermann [14]) e problemi di Algebra Lineare Asintotica, in modo da facilitare la comunicazione delle competenze tra due settori in cui viene a volte adottato un differente linguaggio matematico. Un secondo argomento riguarda l'inquadramento dei metodi iterativi precondizionati nella teoria analitica classica degli operatori di regolarizzazione per problemi mal posti [6].
 

A4) Risultati astratti sul precondizionamento multilivello
È noto [50,46] che, a differenza di quanto accade nel caso unilivello, per strutture di Toeplitz multilivello è impossibile trovare successioni di precondizionatori in algebre matriciali che assicurino un cluster forte. Si vuole proseguire tale analisi includendo tutte le algebre di tipo trigonometrico e dando una caratterizzazione topologica all'insieme dei simboli f per cui la successione di Toeplitz associata non ammette precondizionatori superlineari in una data successione di algebre. Si prevede che valga un analogo risultato negativo se si richiedono proprietà spettrali anche più deboli che assicurino l'ottimalità del precondizionatore. Ciò avrebbe un notevole impatto filosofico, in quanto risulterebbe che nel caso multilivello (incluse le PDE) la sola via per costruire metodi ottimali consiste nell'integrare tecniche multigrid e precondizionamento a banda (vedi B1 e C2a) e nelle strategie basate su complementi di Schur a più livelli. È previsto un assegno di ricerca annuale su questo specifico punto del progetto.
 

B) Aspetti computazionali
 

Ci si occuperà di tecniche multigrid, risoluzione di sistemi lineari e problemi agli autovalori mediante precondizionamento, e metodi numerici per strutture meno comuni.
 

B1) Metodi multigrid
Analisi e sintesi di algoritmi tipo multigrid per la risoluzione di sistemi lineari strutturati multilivello con attenzione a matrici in Algebre e Toeplitz Multilivello. Si vuole affrontare lo studio delle proprietà geometriche e di struttura dei proiettori allo scopo di ottenere metodi Two-grid e Multigrid ottimali, cioè convergenti in un numero costante di iterazioni indipendente dalla dimensione e con costo lineare per strutture a banda multilivello. L'importanza di tale tematica è legata ai risultati negativi per il precondizionamento in algebre di matrici (si veda il punto precedente e la Base di Partenza). Nello specifico si vuole considerare la stesura di algoritmi di multigrid algebrico per le seguenti classi di problemi:
a) Strutture Toeplitz e Tau (proseguendo l'analisi in [26]);
b) Strutture circolanti;
c) Strutture in algebra di Coseni-III;
d) Strutture Toeplitz+diagonali;
e) Strutture proiettate.
Le prime due hanno importanza in problemi differenziali ellittici, con condizioni al contorno di Dirichlet e periodiche rispettivamente, mentre la terza è importante in problemi di ricostruzione di immagini. La quarta interviene nel trattamento numerico di PDE con metodi esponenzialmente convergenti (come il metodo "sinc"), la quinta nel caso in cui gli operatori differenziali sono definiti in plurirettangoli (PR) anziché in parallelepipedi (sia nel caso FD che nel caso FE). Infine, dal punto di vista teorico, si vorrebbe sviluppare un approccio unificato per l'individuazione di tecniche multigrid per "strutture autosomiglianti".
 

B2) Precondizionamento di sistemi lineari strutturati
Si vogliono analizzare le proprietà regolarizzanti del precondizionatore "superottimale" di Tyrtyshnikov [54] e dei precondizionatori "filtranti" da esso derivati. Svariate questioni risultano aperte: come va costruito un precondizionatore multilivello tenendo basso il costo computazionale, come dimostrare risultati spettrali sotto ipotesi più generali, l'uso in connessione con metodi non simmetrici e l'eventuale estensione dei precondizionatori regolarizzanti alla risoluzione di problemi col vincolo di non negatività.
Un altro punto del progetto riguarda i sistemi lineari shiftati del tipo (A+cI)x=b, dove A è simmetrica definita positiva e c è un parametro non negativo, che intervengono in varie applicazioni. Viene proposto un nuovo precondizionatore legato a una modifica delle inverse approssimate in forma fattorizzata. Vari esperimenti e un'analisi preliminare hanno dato risultati molto promettenti su ampie classi di matrici.
 

B3) Tecniche di continuazione per il calcolo di autovalori
Un ulteriore campo di indagine considerato nel progetto è la ricerca di metodi numerici effettivamente veloci per calcolare tutti gli autovalori di una matrice di Toeplitz, che è un problema ancora aperto. Sorprende che le tecniche di precondizionamento più efficienti permettano di risolvere un sistema lineare di Toeplitz in O(n log n) operazioni, mentre il miglior risolutore conosciuto del problema agli autovalori per matrici di Toeplitz generiche [53] richieda ben O(n²) operazioni per ciascun autovalore. In alcuni casi ristretti è stato possibile ridurre la complessità grazie alle ottime approssimazioni di matrici di Toeplitz, la cui diagonalizzazione è nota esplicitamente, fornite dal precondizionamento. Lo scopo di questo progetto non va oltre uno studio di fattibilità per due tecniche specifiche: i flussi isospettrali [56] e i metodi di omotopia [18].
 

B4) Altre strutture
Si vuole proseguire la costruzione di algoritmi veloci e stabili per la fattorizzazione QR di matrici Cauchy-like. Inoltre, si vuole focalizzare l'attenzione sulle proprietà spettrali e computazionali della classe delle matrici diagonali-più-semiseparabili, che svolgono un ruolo cruciale nell'approssimazione: in particolare, le stesse relazioni esistenti tra matrici tridiagonali e sequenze di polinomi ortogonali esistono tra queste matrici e certe sequenze di funzioni razionali ortogonali [24].
 

C) Applicazioni
 

Verranno considerati tre argomenti principali: equazioni integrali legate a problemi inversi, PDE, problemi di approssimazione funzionale e quadratura.
 

C1) Elaborazione di immagini
a) Da un punto di vista applicativo è molto importante individuare metodi numerici particolarmente efficienti per risolvere il problema LBT, a causa del notevole volume di dati. Il programma consta di tre punti. Anzitutto si intende proseguire lo studio dei metodi di deconvoluzione più classici applicati ad immagini multiple [7], allo scopo di fornirne un confronto esauriente. Si vuole inoltre tentare di sfruttare attentamente le strutture matriciali presenti in modo naturale nella formulazione del problema, allo scopo di migliorare le prestazioni. Esiste infine la possibilità che le immagini all'infrarosso vengano inserite nell'ambito del progetto LBT; in questa prospettiva, si intende proseguire le ricerche sulle tecniche "chopping e nodding" [8].
b) Si vuole proseguire lo sviluppo di algoritmi veloci di ricostruzione SPECT basati sul modello a pixel naturali [9], che sfrutta l'invarianza per rotazioni; va in particolare indagata la struttura presente al livello della variabile spaziale (forse con l'uso di tecniche multigrid); va poi raffinato il modello introducendo una correzione per l'attenuazione; è infine necessaria un'attenta validazione sperimentale.
 

C2) Sistemi lineari e PDE
a) Problemi ellittici e semi-ellittici
Analisi e sintesi di algoritmi veloci ad hoc per la risoluzione di sistemi lineari strutturati multilivello, con attenzione alle discretizzazioni con FD, FE, Collocazione [31] di PDE con coefficienti non costanti e su domini rettangolari e non. Analisi di precondizionatori per il gradiente coniugato e delle relative proprietà di clustering ed equivalenza spettrale. In particolare, in analogia con [42,47] ci si aspetta un clustering forte in presenza di regolarità C² dei coefficienti delle equazioni a derivate parziali considerate e quindi un sostanziale miglioramento rispetto agli algoritmi di gradiente coniugato basati su algebre [16], fattorizzazioni incomplete o polinomi di matrici [2]. La congettura finale è che tale approccio conduca alle prime tecniche ottimali di precondizionamento nel caso di problemi differenziali semi-ellittici, anche per domini PR generici.
b) Problemi di evoluzione
Studio di precondizionatori circolanti a blocchi per sistemi lineari non simmetrici legati ai metodi ai limiti per PDE dipendenti dal tempo. L'obiettivo specifico è l'analisi dello spettro, del condizionamento e di altre proprietà inerenti.
 

C3) Approssimazione e quadratura
Saranno studiati tre diversi argomenti. L'uso della "Matrix technology" consentirà di determinare la distribuzione limite per gli zeri di successioni di polinomi ortogonali con coefficienti di ricorrenza periodici dipendenti da parametro (seguendo le indicazioni in [32]). Si vuole analizzare la struttura delle conseguenti matrici di Jacobi e si ipotizza che queste successioni siano equi-distribuite rispetto a speciali successioni di Toeplitz o Localmente Toeplitz generalizzate.
Un altro filone è la quadratura di funzioni di classe L¹ e l'analisi numerica dell'immagine essenziale di funzioni semplicemente misurabili tramite le formule ergodiche discusse in [55,40,45]. Si vuole inoltre considerare la possibilità di individuare tecniche di accelerazione della convergenza da usare qualora la funzione in esame possieda un certo grado di regolarità.
Infine, la profonda comprensione delle strutture Cauchy, Pick e Vandermonde risulterà utile nell'analisi di algoritmi per risolvere problemi di interpolazione polinomiale e razionale, tra cui il problema di Nevanlinna-Pick.
 

D) Software
 

Lo sviluppo di software è richiesto dai punti B1 e C1 del progetto. Si vuole realizzare un software prototipale che implementi gli algoritmi multigrid descritti in precedenza allo scopo di testare le tecniche adottate su problemi applicativi di dimensioni realistiche. Lo sviluppo di software prototipale dedicato è inoltre necessario per effettuare una corretta validazione numerica dei metodi avanzati introdotti per i problemi LBT e SPECT; contratti di ricerca espressamente previsti darebbero un grande aiuto per questi punti cruciali del progetto e per l'analisi degli aspetti matematici ad esso legati.
 

L'unità riunisce studiosi di diverse sedi, e i risultati attesi sono ottenibili solo attraverso una stretta collaborazione. Pertanto, il finanziamento dovrà coprire in buona parte le spese di missione relative ad incontri scientifici individuali e partecipazioni a convegni. Inoltre, alcuni punti del progetto richiedono l'inserimento di giovani ricercatori sia per tematiche di ricerca che per sviluppo di software; un'altra quota dei fondi richiesti sarà quindi destinata al finanziamento di contratti di ricerca e collaborazioni occasionali.