MODELLO

nº	Cognome	Nome	Dipartimento	Qualifica	Settore Disc.	Mesi Uomo
1° anno	2° anno
1.	DI BENEDETTO	Fabio	Dip. MATEMATICA	Prof. Associato	MAT/08	8	6
2.	BOCCACCI	Patrizia	Dip. INFORMATICA E SCIENZE DELL'INFORMAZIONE	Ricercatore Universitario	INF/01	3	3
3.	BRIANZI	Paola	Dip. MATEMATICA	Prof. Associato	MAT/08	4	4
	TOTALE					15	13

nº	Cognome	Nome	Università	Dipartimento	Qualifica	Settore Disc.	Mesi Uomo
1° anno	2° anno
1.	SERRA CAPIZZANO	Stefano	INSUBRIA	Dip. SCIENZE CHIMICHE, FISICHE E MATEMATICHE	PA	MAT/08	4	6
2.	TABLINO POSSIO	Cristina	MILANO-BICOCCA	Dip. MATEMATICA E APPLICAZIONI	RU	MAT/08	6	6
3.	FASINO	Dario	UDINE	Dip. MATEMATICA E INFORMATICA	PA	MAT/08	4	5
4.	BERTACCINI	Daniele	ROMA	Dip. MATEMATICA	RU	MAT/08	7	6
	TOTALE						21	23

nº	Cognome	Nome	Università	Dipartimento	Qualifica	Mesi Uomo
1° anno	2° anno
1.	Donatelli	Marco	Università degli Studi INSUBRIA Varese-Como	Dip. di Fisica e Matematica	dottorando	7	7
	TOTALE					7	7

nº	Cognome	Nome	Dipartimento	Data di inizio del contratto	Durata (in anni)	Mesi Uomo
1° anno	2° anno
1.	ESTATICO	Claudio	Dip. MATEMATICA	02/09/2003	1	9	7
TOTALE						9	7

nº	Qualifica	Costo previsto	Mesi Uomo	Note
1° anno	2° anno
1.	Assegnista	18.000	9	7	possibile cofinanziamento da parte dell'Area
	TOTALE	18.000	9	7

L'unità operativa comprende gli stessi partecipanti di un progetto cofinanziato MIUR del 2002 (http://bezout.dm.unipi.it). I componenti (otto matematici e un'informatica) vantano una prolungata esperienza di ricerca nei campi dell'analisi spettrale e computazionale di ampie classi di matrici strutturate [21,22,23,24,29,30,39,44,52] e della regolarizzazione di problemi inversi che intervengono in molteplici applicazioni [7,16]. Più di recente, è stato creato nuovo feedback tra l'algebra lineare strutturata e campi d'applicazione come le equazioni alle derivate parziali (PDE), le immagini e l'approssimazione di funzioni [4,6,8,9,49,50].
La descrizione della base di partenza scientifica seguirà, in larga parte, quella del precedente progetto, con gli opportuni aggiornamenti ed integrazioni.

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 iniziati da Szego (si veda [15]), culminati nel lavoro di Tyrtyshnikov [56] 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 [42,43] oltre ad applicazioni all'approssimazione e alla quadratura [45]. Altra importante estensione concerne il caso di strutture che sono "solo localmente" Toeplitz [55] o che possiedono altre "strutture locali" e che contengono come casi particolari discretizzazioni di equazioni differenziali con condizioni al contorno [50,51].
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 [15,41,43,52] 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 [35] 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 [54] propose per primo nel 1986), sono la scelta più comune, per quanto anche le trasformate trigonometriche siano state recentemente prese in considerazione [10,34].
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 [53,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 [18] e che conduce a metodi ottimali e superlineari [40] di costo O(n log(n)) per sistemi definiti positivi con condizionamento polinomiale, o solo ottimali per il caso non definito [39].
Le stesse idee sono state sfruttate in seguito nelle algebre matriciali da vari autori (vedi ad es. [21,44,19]). Il problema è così ricondotto al caso a banda, per il quale esistono risolutori ottimali iterativi (il multigrid [31], studiato in seguito da R.Chan e Huckle) e diretti [12] di costo lineare.
È importante osservare che tale tecnica di precondizionamento a banda è naturalmente estendibile al caso multilivello [38]. 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 è di nuovo ottimale [2]. Sulla base di tali premesse uno degli obiettivi principali nelle future ricerche sarà quello di indagare metodi multigrid ottimali per il caso specifico di strutture a banda e multilivello (con condizionamento polinomiale).

Segnaliamo altri due tipi di strutture, sviluppati nella letteratura più recente.
Il primo riguarda i sistemi lineari shiftati del tipo (A+cI)x=b, che intervengono in varie applicazioni (elaborazione d'immagini, PDE evolutive, calcolo iterativo di autovalori, etc.), ove al posto dell'identità I figura talvolta uno shift diagonale generico. Nel progetto precedente è stato proposto un nuovo precondizionatore nel caso di A SPD, legato a una modifica delle inverse approssimate in forma fattorizzata [3].
Il secondo riguarda le matrici diagonali+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 [29]. Negli ultimi due anni diversi gruppi hanno studiato problemi computazionali legati a tale classe, come il metodo QR per il calcolo degli autovalori, con ricadute interessanti sul calcolo di zeri di polinomi [11,30].

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 PDE, l'approssimazione di funzioni.

Una recente tecnica di imaging che richiede di risolvere problemi di ricostruzione particolarmente difficili è ad esempio 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. Altre tecniche di imaging ad esso legate sono il "chopping e nodding" [8] per l'infrarosso e l'ottica adattiva [20].
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 mediante la definizione di una famiglia parametrica di precondizionatori specifici, aventi di per sè effetto regolarizzante; tale famiglia può essere ottenuta filtrando opportunamente i precondizionatori ottimale [32] o superottimale [26].
Le ricostruzioni ottenute con un metodo di base possono poi essere migliorate grazie a due strumenti avanzati: le condizioni al contorno (vedi [8,33,37] per scelte classiche e [48] per la nuova idea delle anti-riflettenti) e le wavelet [17].
L'uso di strutture matriciali si è ormai affermato nei problemi inversi lineari, ma è ancora raro nel campo non lineare. Va segnalato al proposito un recente risultato [27] relativo ad un problema di Remote Sensing. Il modello matematico da risolvere è un'equazione integro-differenziale non lineare fortemente malposta, e si può trattare con una tecnica iterativa "Quasi-Newton" a due livelli, con regolarizzazione del problema linearizzato tramite metodo di Landweber; ciò conduce a matrici strutturate ed all'uso di tecniche di algebra numerica veloce.

La struttura di Toeplitz a banda è l'ingrediente principale per una tecnica di precondizionamento superlineare [49,50,51] per discretizzazioni a Differenze Finite, Elementi Finiti o Collocazione 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² e quindi migliora sostanzialmente altre tecniche di precondizionamento (fattorizzazioni incomplete, inverse approssimate, algebre matriciali).
La discretizzazione alle differenze finite di problemi di evoluzione con formule multistep lineari ai valori al bordo determina invece matrici non simmetriche di grandi dimensioni con struttura a blocchi. Sono stati introdotti diversi precondizionatori: di tipo circolante [4,6] o basati su splitting Hermitian-skew Hermitian [5]; sotto opportune ipotesi, per entrambi la convergenza risulta indipendente dal parametro di finezza.

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

The group consists of the same people participating to a project which has been funded for the period 2002-2003 (see the web page http://bezout.dm.unipi.it). The components (eight mathematicians and one computer scientist) have a long-standing research experience in the fields of the spectral and computational analysis of wide classes of structured matrices [21,22,23,24,29,30,39,44,52] and of the regularization of inverse problems arising in several applications [7,16]. More recently, new expertises have been acquired about the feedback between structured linear algebra and applied areas including partial differential equations (PDEs), image processing and functional approximation [4,6,8,9,49,50].
The description of the scientific background will follow, in a large part, that of the previous project, obviously with the appropriate updates and additions, achieved during the project itself.

In the last years the insight about structured Toeplitz-like matrices has received a strong impulse by several research groups in numerical linear algebra.
Two main research lines have taken place in the literature. The first is more theoretical and is concerned with the spectral properties of structured sequences. The second has a more applicative appealing and is related to the design of efficient structured solvers.

Regarding the spectral properties, we recall the distributional results pioneered by Szego (see [15]) and culminated in the work of Tyrtyshnikov [56] concerning the "global behaviour" of the spectra of Toeplitz sequences. Extensions to matrix valued generating functions and to sequences arising in the preconditioning theory [42,43] as well as some applications to approximation and quadrature [45], can be found in literature. A second important extension concerns the case of structures which are of Toeplitz type "only locally" [55] or that possess different "local structures" and include, as special instance, discretizations of differential operators with boundary conditions [50,51].
A further research line of theoretical and applicative interest is the analysis of the extremal spectral behaviour for its impact in the study of the asymptotical conditioning (see [15,41,43,52] and references therein).

Concerning the numerical methods, crucial results have been recently achieved in the construction of more and more efficient algorithms for solving linear systems and least squares problems.
The first specialized techniques are the "fast" and "superfast" methods. They belong to the class of direct methods and reduce the arithmetic cost to O(n²) and O(n log²n) operations where n is the size of the systems. For an exhaustive survey on these methods often based on the notion of "displacement rank" see [35] (and the several references in the bibliography) and the book [13].
For the well conditioned case, a further improvement is represented by the use of the Preconditioned Conjugate Gradient method (PCG). A typical choice takes the preconditioner in the algebra including all the matrices that are diagonalized by a prescribed fast transform: the most widely used is the circulant class associated with the discrete Fourier transform (as Strang [54] proposed first in 1986), even though trigonometric transforms recently received particular attention [10,34].
The conclusion is that the strong clustering holds for continuous symbols and in the unilevel case while in the multilevel case the strong clustering rarely occurs and the clustering features deteriorate as the number of levels increases. The general situation is even worse since the papers [53,46] inform us that this kind of clustering is the best possible when we use matrix algebra preconditioners.
Concerning the ill-conditioned case, the analysis is more complicated and indeed many of the fast and superfast solvers show numerical instability and many of the proposed preconditioners are no longer optimal since the required number of iterations can grow with the dimension n. In this respect R.Chan and Di Benedetto, Fiorentino and Serra Capizzano introduce a new preconditioning strategy based on banded Toeplitz matrices (see [18]) that leads to optimal and superlinear [40] iterative solvers of cost O(n log(n)) for positive definite linear systems having polynomial ill conditioning, or just optimal methods for the indefinite case [39].
These ideas have been further exploited by Di Benedetto, Serra Capizzano, R.Chan, Potts and Steidl in a matrix algebra setting (see e.g. [21,44,19]). Now the problem is reduced to the band case for which we have optimal iterative solvers (the multigrid method [31] subsequently studied by R.Chan and Huckle) and direct solvers [12] of linear cost.
It is worthwhile stressing that this preconditioning strategy can be extended in a natural way [38] to the multilevel setting. Therefore the crucial problem is reduced to finding good solvers in the banded multilevel Toeplitz case. The method in [12] is no longer optimal (even if it shows a "quasi linear" arithmetic cost), while the multigrid technique is still optimal [2]. In conclusion one of the important issues to be taken into account in future works is the analysis and the design of optimal multigrid strategies for multilevel banded structures (with polynomial ill conditioning).

Two further kinds of structures, developed in the most recent literature, are worth to mention.
The first one involves shifted linear systems as (A+cI)x=b, arising in several frameworks (image processing, time-dependent PDEs, iterative eigensolvers, etc.), where the identity matrix I is sometimes replaced by a more general diagonal shift. In the previous project a new preconditioning technique has been proposed for the case where A is SPD and e is a nonnegative parameter, based on a modification of factorized approximate inverses [3].
The second one is concerned with diagonal plus semi-separable matrices, which play a crucial role in the approximation context: more precisely, the well-known link between tridiagonal matrices and orthogonal polynomials has a counterpart between this new matrix class and orthogonal rational functions [29]. Several people have considered in the last two years some computational problems related to this class, such as QR iteration for computing the eigenvalues, with promising applications to polynomial rootfinding [11,30].

From the application point of view, many concrete situations demand the fast solution of mathematical problems of very large size, characterized by the (sometimes hidden) presence of matrix structures; among the most important, we point out inverse problems arising in image processing, PDEs and functional approximation.

A very recent example of imaging device that requires the solution of challenging reconstruction problems is the Large Binocular Telescope (LBT) [1]. The underlying mathematical problem involves the reconstruction of multiple images of about 10⁸ pixels, and therefore it needs efficient numerical methods. Other related imaging problems involve "chopping and nodding" [8] techniques for the recovering of infrared images, and adaptive optics [20].
All the numerical methods used in image reconstruction must take into account that some regularization approach is needed. Successful applications of matrix algebra preconditioning have involved the definition of a parameter-dependent family of specific preconditioners, constructed by means of a proper filtering of optimal [32] or superoptimal [26] approximations, having themselves a regularization effect.
The reconstruction obtained by a basic method can be further improved with the help of two advanced tools: boundary conditions (see [8,33,37] for classical proposals and [48] for the new anti-reflective idea) and wavelets [17].
The use of structured matrix tools is becoming standard for linear inverse problems, but is still uncommon in the nonlinear case. It is worth to mention a recent successful experience [27] along this direction, concerning a Remote Sensing problem. The mathematical model is a nonlinear ill-posed integral-differential equation, which can be treated by an outer-inner two-steps Inexact Newton iterative method. Any Newton linearized step has been regularized by means of the Landweber iterative method, leading to the use of structured matrix computational techniques.

Banded Toeplitz matrices are the main ingredient in a superlinear preconditioning strategy [49,50,51] for Finite Differences (FD), Finite Elements or Collocation discretizations of elliptic boundary value problems with nonconstant coefficients. This technique insures a strong clustering and a spectral equivalence at least when the coefficients are two times continuously differentiable, hence it gives a substantial improvement with respect to other preconditioning techniques (incomplete factorizations, approximate inverses, matrix algebras).
Finite difference discretization of time-dependent PDEs generates large nonsymmetric matrices having a block structure. Several preconditioners have been introduced, either of circulant type [4,6] or based on a Hermitian-skew Hermitian splitting [5]; both achieve a rate independent of the discretization parameter under suitable assumptions.

Finally, several problems related to polynomial and rational approximation can be described in terms of structured matrices, including Cauchy, Pick, Vandermonde, locally Toeplitz and semiseparable. The spectral properties of these matrices allow us to better understand the behaviour of numerical solvers for the underlying approximation problem.

[1] J.Angel, J.Hill, P.Strittmatter, P.Salinari, G.Weigelt, Interferometry with the Large Binocular Telescope. Proc. SPIE 3352(1998), 881-889
[2] A.Aricò, M.Donatelli, S.Serra Capizzano, Multigrid optimal convergence for certain (multilevel) structured linear systems. SIAM J. Matr. Anal. Appl., in press
[3] M.Benzi, D.Bertaccini, Approximate inverse preconditioning for shifted linear systems. BIT 43(2003), 231-244
[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, G.Golub, S.Serra Capizzano, C.Tablino Possio, Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems. Tech. Rep., Stanford Univ., 2002
[6] D.Bertaccini, M.Ng, Band-Toeplitz Preconditioned GMRES Iterations for time-dependent PDEs. BIT 43(2003), 901-914
[7] M.Bertero, P.Boccacci, Introduction to Inverse Problems in Imaging, IOP Publ., Bristol, 1998
[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, A new preconditioner for the parallel solution of positive definite Toeplitz linear systems. Proc. 2nd SPAA conf. Crete (Greece), 1990, 220-223
[11] D.Bini, L.Gemignani, V.Pan, Inverse power and Durand-Kerner iterations for univariate polynomial root-finding. Comput. Math. Appl., in press
[12] D.Bini, B.Meini, Effective methods for solving banded Toeplitz systems. SIAM J. Matr. 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.Björck, P.Heggernes, P.Matstoms, Methods for large scale total least squares problems. SIAM J. Matr. Anal. Appl. 22(2000), 413-429.
[15] A.Boettcher, B.Silbermann, Introduction to Large Truncated Toeplitz Matrices. Springer, NY, 1999
[16] P.Brianzi, A criterion for the choice of a sampling parameter in the problem of Laplace transform inversion. Inverse Problems 10(1994), 55-61
[17] R.Chan, T.Chan, L.Shen, Z.Shen, Wavelet deblurring algorithms for spatially varying blur from high-resolution image reconstruction. Linear Algebra Appl. 366(2003), 139-155
[18] R.Chan, M.Ng, Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38(1996), 427-482
[19] R.Chan, D. Potts, G. Steidl, Preconditioners for nondefinite Hermitian Toeplitz systems. SIAM J. Matr. Anal. Appl. 22(2000), 647-665
[20] M.Chu, V.Pauca, R.Plemmons, X.Sun, A Mathematical Framework for the Linear Reconstructor Problem in Adaptive Optics. Linear Algebra Appl. 316(2000), 113-135
[21] F.Di Benedetto, Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices. SIAM J. Sci. Comp. 16(1995), 682-697
[22] F.Di Benedetto, Preconditioning of block Toeplitz matrices by sine transforms. SIAM J. Sci. Comp. 18(1997), 499-515
[23] F.Di Benedetto, Solution of Toeplitz normal equations by sine transform based preconditioning. Linear Algebra Appl. 285(1998), 229-255
[24] F.Di Benedetto, S.Serra Capizzano, A unifying approach to abstract matrix algebra preconditioning. Numer. Math. 82(1999), 57-90
[25] H.Engl, M.Hanke, A.Neubauer, Regularization of Inverse Problems, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996
[26] C.Estatico, A class of filtering superoptimal preconditioners for highly ill conditioned linear systems. BIT 42(2002), 753-778
[27] C.Estatico, A.Tamasan, A Newton linearization approach for solving the atmospheric retrieval problem. Tech. Rep., UCLA, 2003
[28] D.Fasino, Rational Krylov matrices and QR steps on Hermitian diagonal-plus-semiseparable matrices. Num. Lin. Alg. Appl., to appear
[29] D.Fasino, L.Gemignani, Structural and computational properties of possibly singular semiseparable matrices. Linear Algebra Appl. 340(2002), 183-198
[30] D.Fasino, N.Mastronardi, M.Van Barel, Fast and stable algorithms for reducing diagonal plus semiseparable matrices to tridiagonal and bidiagonal form. Contemporary Mathematics 323(2003), 105-118
[31] 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
[32] M.Hanke, J.Nagy, R.Plemmons, Preconditioned iterative regularization for ill-posed problems. Numerical Linear Algebra and Scientific Computing, de Gruyter, 1993, 141-163
[33] A.Jain, Fundamentals of Digital Image Processing. Prentice-Hall, Englewood Cliffs, NJ, 1989
[34] 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
[35] T.Kailath, A.Sayed, Displacement structure: theory and applications. SIAM Rev. 37(1995), 297-386
[36] S.Kamvar, H.Haveliwala, C.Manning, G.Golub, Exploiting the block structure of the Web for computing PageRank. Tech. Rep., Stanford Univ., 2003
[37] M.Ng, R.Chan, W.C.Tang, A fast algorithm for deblurring models with Neumann boundary conditions. SIAM J. Sci. Comput. 21(1999), 851-866
[38] S.Serra Capizzano, Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems. BIT 34(1994), 579-594
[39] S.Serra Capizzano, Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions. SIAM J. Matr. Anal. Appl. 17(1996), 1007-1019
[40] S.Serra Capizzano, Optimal, quasi-optimal and superlinear preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems. Math. Comp. 66(1997), 651-665
[41] S.Serra Capizzano, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices. Linear Algebra Appl, 270(1998), 109-129
[42] S.Serra Capizzano, An ergodic theorem for classes of preconditioned matrices. Linear Algebra Appl. 282(1998), 161-183
[43] S.Serra Capizzano, Asymptotic results on the spectra of block Toeplitz preconditioned matrices. SIAM J. Matr. Anal. Appl. 20(1998), 31-44
[44] S.Serra Capizzano, Superlinear PCG methods for symmetric Toeplitz systems. Math. Comp. 68(1999), 793-803
[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, Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs Matrix-sequences. Numer. Math. 92(2002), 433-465
[48] S.Serra Capizzano, A note on anti-reflective boundary conditions and fast deblurring models. SIAM J. Sci. Comput. 25(2003), 1307-1325
[49] S.Serra Capizzano, C.Tablino Possio, Finite Element matrix-sequences: the case of rectangular domains. Numer. Alg. 28(2001), 309-327
[50] S.Serra Capizzano, C.Tablino Possio, Analysis of preconditioning strategies for collocation linear systems. Linear Algebra Appl. 369(2003), 41-75
[51] S.Serra Capizzano, C.Tablino Possio, Superlinear preconditioners for Finite Differences linear systems. SIAM J. Matr. Anal. Appl. 25(2003), 152-164
[52] S.Serra Capizzano, P.Tilli, Extreme singular values and eigenvalues of non Hermitian Toeplitz matrices. J. Comp. Appl. Math. 108(1999), 113-130
[53] S.Serra Capizzano, E.Tyrtyshnikov, Any circulant-like preconditioner for multilevel matrices is not superlinear. SIAM J. Matr. Anal. Appl. 21(1999), 431-439
[54] G.Strang, A proposal for Toeplitz matrix calculations. Stud. Appl. Math. 74(1986), 171-176
[55] P.Tilli, Locally Toeplitz sequences: spectral properties and applications. Linear Algebra Appl. 278(1998), 91-120
[56] E.Tyrtyshnikov, N.Zamarashkin, Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships. Linear Algebra Appl. 270(1998), 15-27

Il programma si sviluppa su due direzioni che erano i temi principali del progetto 2002-2003:
A) Proprietà teoriche e computazionali di matrici strutturate;
B) Strutture matriciali in problemi applicativi.
I problemi aperti in algebra lineare strutturata considerati in A) sono naturale continuazione di ricerche condotte nel progetto precedente, con un'attenzione particolare rivolta a strutture meno studiate (matrici shiftate, semiseparabili, nuove algebre di seni, "ingrassamenti spettrali" di algebre di tipo circolante/trigonometrico): le prime tre sono state oggetto di studio nella letteratura più recente e nelle applicazioni, mentre l'ultima è una nuova proposta a metà strada fra il precondizionamento di tipo circolante e le inverse approssimate sparse.
Le principali applicazioni in B) risultano ancora l'approssimazione, i problemi inversi e le PDE. Oltre alla continuazione di ricerche precedenti, qui verranno anche studiati nuovi problemi e/o tecniche innovative, spesso basate su strumenti avanzati sviluppati di recente nell'ambito delle strutture.
Rispetto al progetto 2002-03, la differenza sta nel diverso peso dato ai temi A) e B): verranno privilegiate le applicazioni reali. Di seguito sono descritti in dettaglio i punti specifici del programma.

A1) Aspetti teorici
a) Algebra lineare asintotica
Applicazione dei risultati finora ottenuti alla convergenza dei metodi iterativi. In particolare, considerando un approccio statistico all'analisi dell'errore nel caso di matrici che mostrano una distribuzione asintotica degli autovalori, siamo interessati nello studiare il ruolo della funzione di distribuzione: siamo convinti che il suo andamento determina l'evolversi dell'errore come il raggio spettrale lo è (asintoticamente) nel caso deterministico.
Il quadro concernente proprietà spettrali asintotiche di matrici strutturate di tipo Toeplitz e Localmente Toeplitz (include discretizzazioni di PDE a coefficienti variabili e su domini irregolari) è abbastanza chiaro: rimane da indagare il comportamento estremale fine (condizionamento asintotico) nel caso multidimensionale seguendo l'approccio di Bottcher e Grudsky. In un ambito più generale (anche non strutturato) e per via del forte interesse nello studio della convergenza di metodi tipo Krylov, studieremo come dedurre il clustering degli autovalori (debole o forte) da un clustering dei valori singolari per il quali sono già a disposizione molti strumenti.
b) Relazioni tra strutture
La relazione esistente tra matrici diagonali+semiseparabili e matrici razionali di Krylov, scoperta in [28], è una controparte "razionale" della ben nota relazione tra matrici tridiagonali e matrici di Krylov classiche. Vogliamo proseguire lo studio di tale relazione, sia per analizzare le proprietà di convergenza delle note varianti razionali dell'iterazione di Krylov, sia per le possibili implicazioni allo studio teorico e computazionale di insiemi di funzioni razionali ortogonali.
A2) Metodologie numeriche
a) Matrici parametriche
Una successione di sistemi lineari è detta parametrica se può essere rappresentata come {Aj xj = bj} dove Aj=A+vj Ej e vj è un parametro scalare; questa descrizione estende il caso più comune di matrici shiftate. Si intende analizzare fattorizzazioni incomplete aggiornate per sistemi lineari parametrici con
i) A nonsimmetrica definita positiva e Ej=I (caso shiftato)
ii) A simmetrica (definita e indefinita) e Ej a banda,
casi che sono strategici nelle rispettive applicazioni. Ad esempio, tecniche del tipo shift-invert, potenze inverse e Jacobi-Davidson sono usate per il calcolo di alcuni (di solito pochi) autovalori e autovettori di problemi hermitiani di grandi dimensioni e sparsi. Si sottolinea che il nucleo di questi algoritmi richiede la soluzione efficiente di numerosi sistemi lineari di grandi dimensioni (e generalmente indefiniti) in forma shiftata. Si prevede di seguire due percorsi per la soluzione dei problemi di cui sopra:
(i) precondizionatori basati su fattorizzazioni aggiornate incomplete indefinite ad-hoc usate con un opportuno metodo di proiezione di Krylov;
(ii) soluzione dei sistemi shiftati mediante metodi di proiezione e precondizionatori multilivello con algoritmi di riordinamento per trasformare il problema di partenza in uno più diagonale dominante.
Un'altra applicazione riguarda la soluzione del problema ai minimi quadrati totali basato sul quoziente di Rayleigh. In questo approccio, la soluzione del problema si riduce alla soluzione di successioni di sistemi simmetrici shiftati e definiti positivi. In [14] Björck e altri hanno proposto di risolvere questi sistemi lineari mediante gradiente coniugato precondizionato con la fattorizzazione (completa) di Choleski della matrice delle equazioni normali. Ci si propone di sintetizzare e analizzare metodi iterativi che generino una successione di sistemi lineari meglio condizionati, usando tecniche basate sulle fattorizzazioni incomplete e inverse approssimate aggiornate.
b) Strutture semiseparabili
Matrici con struttura semiseparabile generalizzata hanno recentemente ottenuto molto interesse come strumenti computazionali per la risoluzione numerica di problemi agli autovalori. La ricerca in questo campo può aprire nuove prospettive per la sintesi di algoritmi efficienti per problemi agli autovalori per matrici speciali, quali matrici di tipo companion generalizzate o matrici di Hessenberg quasi-unitarie.
Inoltre, vogliamo analizzare la possibilità di specificare il termine diagonale nella riduzione di una matrice simmetrica in forma diagonale+semiseparabile, allo scopo di renderne più efficiente il calcolo degli autovalori.
c) Strutture multilivello
Siamo interessati all'analisi e sintesi di algoritmi veloci ad hoc per la risoluzione di sistemi lineari strutturati multilivello (analisi di precondizionatori per il gradiente coniugato, delle relative proprietà di clustering ed equivalenza spettrale, e studio di metodi multigrid con enfasi alla scelta della coppia proiettore/smoother). Più in dettaglio ci interesseremo ai seguenti temi:
- Precondizionamento di strutture multilivello Toeplitz cercando di generalizzare al caso in più variabili i risultati di ottimalità presenti in [40].
- Proposta di un "ingrassamento" di algebre considerando matrici della forma U T U* dove T è una matrice con un certo profilo di sparsità e per la quale la risoluzione di un sistema lineare associato abbia complessità limitata dal costo di moltiplicare U o U* per un vettore (tipicamente O(n log n) operazioni aritmetiche). Vogliamo indagare se questa nuova proposta, che arricchisce sensibilmente le algebre classiche in cui T è solo diagonale, sia sufficiente ad individuare precondizionatori ottimali nel caso multilivello e con malcondizionamento polinomiale (cosa impossibile per T diagonale).
- Estensione della dimostrazione di ottimalità del multigrid in [2] al caso multilivello ed applicazioni a problemi di ricostruzioni di immagini (si veda B2-a) ed alle PDE (con particolare attenzione ai sistemi strutturati e densi provenienti dai metodi Sinc-Galerkin applicati a PDE ellittiche).
B1) Prosecuzione di ricerche precedenti
a) Approssimazione razionale
Vogliamo proseguire alcune ricerche intraprese su problemi di interpolazione o approssimazione con funzioni razionali, con particolare riguardo all'analisi del condizionamento strutturato e al posizionamento ottimale dei poli.
b) Problemi inversi di imaging
Applicazione di algoritmi per la stima automatica del numero di iterazioni, che rappresenta un parametro di regolarizzazione nei metodi iterativi per problemi mal posti, ed è quindi un argomento cruciale nell'ambito della risoluzione di problemi inversi. Estensione dei precondizionatori regolarizzanti al caso della ricostruzione di immagini non negative e all'interno di problematiche legate al sistema di ottica adattiva di cui è fornito l'interferometro LBT.
Analisi e sintesi di nuovi algoritmi efficienti per sistemi lineari generati da algoritmi di regolarizzazione alla Tikhonov. Restringeremmo la nostra attenzione a termini regolarizzanti rappresentanti l'operatore identità o la derivata prima o seconda. Le relative equazioni normali sono in forma parametrica, e potrebbe essere necessario risolvere l'equazione sopra per numerosi valori del parametro di Tikhonov. Gli algoritmi proposti sono basati su nuovi metodi iterativi che usano fattorizzazioni incomplete aggiornate generalizzando i risultati in [3] (che si possono applicare direttamente se il termine di penalizzazione è la semplice norma della soluzione).
Infine, una vasta mole di calcolo è necessaria per ottimizzare noti algoritmi di ricostruzione (quale OS-EM per immagini multiple). Ad esempio, il problema LBT richiede di trattare immagini ad alto range dinamico (giovani stelle binarie, pianeti extrasolari). In tali casi si indagherà in due direzioni: la scelta di un funzionale adatto a catturare particolari caratteristiche e un sofisticato denoising a posteriori che preservi forti gradienti e strutture deboli.
c) PDE
Analisi delle caratteristiche di convergenza del GMRES precondizionato per la soluzione dei sistemi lineari che discretizzano l'equazione di convezione-diffusione con coefficiente di diffusione variabile. Il precondizionatore è basato sulla parte diffusiva dell'operatore corrispondente e si considererà principalmente una discretizzazione del tipo differenze finite in un dominio rettangolare d-dimensionale. Prevediamo di dimostrare l'esistenza di un cluster proprio di autovalori per la matrice precondizionata e quindi la convergenza superlineare delle iterazioni dell'algoritmo precondizionato. Una analisi preliminare ha dimostrato che la struttura del cluster non è influenzata dalla finezza della griglia ma il numero degli outlier nello spettro della matrice precondizionata cresce linearmente col parametro di viscosità. Le stesse tecniche saranno applicate a un modello del metabolismo umano basato su equazioni di convezione-diffusione-reazione dipendenti dal tempo, messe a punto al MIMS center di Cleveland.
B2) Tecniche innovative
a) Multigrid regolarizzante
Nel recuperare il "vero" oggetto da quello sfocato ed affetto da rumore si dovrà tener conto di tecniche regolarizzanti allo scopo di aggirare il problema della cattiva positura del problema. A tale scopo esistono diverse procedure di regolarizzazione quali Tikhonov, Riley, metodi iterativi come CG, CGNE, Landweber etc (si veda [25]). Si vuole indagare la possibilità di utilizzare una tecnica multigrid (basata sulla tecnica algebrica in [2,47]) che, per la sua naturale struttura a più livelli, dovrebbe ben adattarsi al problema in esame. I nostri obiettivi sono i seguenti:
- ottenere la stessa precisione nella ricostruzione dei migliori metodi regolarizzanti (come Landweber o CGNE) ma con un enorme risparmio computazionale;
- adattare la tecnica ad ogni tipo di condizioni al contorno (si veda il punto seguente) grazie alla estrema versatilità del metodo algebrico in [2] rispetto a varie strutture considerate.
b) Condizioni al contorno
Concentreremo i nostri sforzi sulle condizioni al contorno (CC) anti-riflettenti con due obiettivi:
- un'analisi accurata dell'algebra di matrici (non canonica, cioè costituita da elementi eterogenei) che origina dalle condizioni al contorno anti-riflettenti;
- lo studio del ruolo del rumore e, più precisamente, di come usare un metodo regolarizzante (la cui necessità nasce dalla presenza del rumore e dalla cattiva positura del problema) in connessione con le CC anti-riflettenti: ci piacerebbe suggerire modifiche delle classiche tecniche regolarizzanti (basate su equazioni normali o su metodi alla Tikhonov) in modo da sfruttare computazionalmente la struttura di algebra che emerge dalle CC considerate.
Resta comunque inteso l'obiettivo di avere una precisione maggiore rispetto a tecniche regolarizzanti applicate con le altre condizioni al contorno.
c) Denoising e determinazione di contorni tramite wavelet
Le immagini astronomiche sono particolarmente rumorose, richiedendo in molti casi tecniche di denoising. Ci si propone di studiare tre casi pratici: immagini "chopped e nodded" (nel vicino infrarosso), misurazioni di PSF usate in metodi classici di restauro, ricostruzioni sovra-iterate. Per tali indagini saranno usati metodi di riduzione basati su wavelet, in modo da ottimizzare il parametro di soglia per ogni problema.
È inoltre ben noto che l'approccio wavelet nella ricostruzione di immagini può risultare molto efficace in particolare nell'individuare i contorni di un'immagine. Vorremmo indagare nelle due seguenti direzioni:
- individuare relazioni tra i classici metodi wavelet per il deblurring di immagini (sfocate ed affette da rumore) e metodi multigrid (si veda B2-a) per il deblurring di immagini (sfocate ed affette da rumore);
- incorporare le più precise CC anti-riflettenti (si veda B2-b) nell'ambito wavelet allo scopo di migliorare la precisione complessiva dell'immagine ricostruita.
B3) Nuove applicazioni
a) Problemi inversi non lineari
L'approccio iterativo "Quasi-Newton" a due livelli precedentemente applicato ad un problema di Remote Sensing, come descritto nella Base di Partenza, ha rivelato la fattibilità dell'uso di matrici strutturate nel nuovo contesto applicativo dei problemi inversi non lineari. Sviluppi futuri prevedono l'applicazione della stessa tecnica ad un problema di determinazione di permittività dielettrica da Non-Linear Inverse Scattering.
b) Motori di ricerca web
In questa applicazione la struttura che definisce il problema è indicata dalle parole chiave "sparsità" e "struttura a blocchi": si aggiunge per ragioni modellistiche una matrice densa di rango 1 moltiplicata per 1-c, con 0<c<1 [36]. Se c è ben separato da 1, il calcolo del vettore positivo PageRank(c) (vettore stazionario sinistro) è effettuabile in modo sufficientemente veloce tramite il classico metodo delle potenze poiché il secondo autovalore ha modulo al più c.
Comunque, se c è vicino a 1, allora il calcolo diviene troppo lento anche per le enormi dimensioni della matrice di WEB. Il nostro obiettivo è di esprimere PageRank(c) come una espansione razionale di PageRank(1) in modo da applicare alla fine una tecnica di estrapolazione vettoriale.
c) Problemi di identificazione
Problemi inversi non standard agli autovalori per matrici tridiagonali, o con altre strutture ad essa correlate (tra le quali anche strutture di tipo diagonale+semiseparabile), sono stati recentemente individuati in alcuni problemi di identificazione di parametri provenienti dall'ingegneria civile.
In tali applicazioni tipicamente si cerca di identificare piccoli danni molto localizzati su travi, barre multistrato o altre strutture di tipo composito, o di ricostruirne proprietà costitutive, a partire da misure di risposta in frequenza o delle frequenze di risonanza.
Scopo della ricerca proposta è quello di fornire risultati teorici (criteri di identificabilità, analisi perturbative) e pratici (costruzione di algoritmi numerici) per l'identificazione di matrici con strutture assegnate a partire da misure di tipo spettrale.

Tutte le ricerche previste richiedono una validazione numerica e lo sviluppo di software prototipale specifico. L'unità necessita dunque di giovani ricercatori, ai quali sarà dedicata una cospicua parte del finanziamento: assegni, borse o contratti temporanei sono previsti durante il biennio del progetto.
L'unità comprende membri di sedi diverse, e una stretta collaborazione è necessaria anche con aiuti esterni: M.Benzi, Atlanta-USA (punto A2-a), D.Calvetti e G.Seidel, Ohio-USA (punto B1-c), G.Golub, Stanford-USA (punti A1-a, A2-a, B1-c), A.Morassi, Udine (punto B3-c), D.Noutsos e P.Vassalos, Ioannina-Grecia (punti A1-a, A2-c), M.Pastorino, DIBE Genova (punto B3-a), M.Tasche, Rostock-Germania (punto B2-c) e membri di altre unità del progetto (punto A2-b). Pertanto i fondi copriranno diverse spese di missione per meeting e conferenze.

The new program is organized along two directions that were the main themes considered in the project 2002-2003:
A) Theoretical and computational properties of structured matrices;
B) Structured matrix tools in applied problems.
The topics considered in A) are open problems in structured numerical linear algebra which represent natural continuations of investigations performed in the previous project. Special emphasis will be devoted to less investigated structures (such as shifted, semi-separable matrices, new matrix algebras related to the sine transform of type I, "spectral fattening" of circulant-like/trigonometric algebras): the first three structures have received particular attention in the most recent literature and in applications, while the last is a really new proposal trying to combine the idea of circulant-like and sparse approximate inverse preconditioners.
The main applications considered in B) are again functional approximation, inverse problems, PDEs. Here, in addition to the continuation of previous researches, the group will investigate new applied problems and/or some completely new approaches, often based on advanced tools that are recently developed in the context of structured matrices.
The essential difference with respect to the 2002-2003 project concerns the weights of themes A) and B): more emphasis will be given to (real world) applications. A detailed description of the specific points of the program is reported below.

A1) Theoretical issues
a) Asymptotical linear algebra
The powerful results obtained so far will be applied to the convergence analysis of iterative methods. In particular, if matrices show some distribution property for the eigenvalues and a statistical approach to the error analysis is considered, we want to investigate the role of the distribution function: we believe that its behavior is responsible to this statistical behavior as the spectral radius is in the deterministic setting.
The picture concerning the asymptotical spectral analysis (distribution, localization, extremal behavior) of structured matrices of Toeplitz and Locally Toeplitz type (including PDEs with variable coefficients and on involved geometries) is quite complete now: it remains to understand the extremal behavior (spectral conditioning) in the multidimensional setting following the approach of Bottcher and Grudsky.
In a more non-structured framework, due to interest in convergence theory of Krylov methods, we will study how to deduce spectral clustering of the eigenvalues (proper or general) from a spectral clustering of the singular values for which much more tools are avalaible.
b) Relations between structures
The interplay between diagonal-plus-semiseparable matrices and rational Krylov matrices, firstly outlined in [28], is a rational counterpart of the well-known connection between tridiagonal matrices and classical Krylov matrices. We intend to further this study in order to analyze properties of rational variants of the Krylov iteration, and to deepen the theoretical and computational properties of orthogonal rational functions.
A2) Numerical methods
a) Parametric matrices
A sequence of linear systems is called parametric if it can be represented as {Aj xj = bj} where Aj=A+vj Ej and vj is a scalar parameter; this description generalizes the simpler case of shifted matrices. We plan to focus our attention to incomplete updated factorizations for parametric sequences of linear systems such that
i) A nonsymmetric positive definite and Ej=I (shifted case), and
ii) A symmetric (definite and indefinite) and Ej is banded,
cases which are crucial in the related applications.
For instance, shift-and-invert (SI), inverse power (IP) and Jacobi-Davidson (JD) are popular techniques for the computation of some (typically few) eigenvalues and eigenvectors for large and sparse Hermitian problems. We stress that the core of these algorithms require the efficient solution of several large (and usually indefinite) algebraic systems in shifted form. We plan to follow two main paths to solve the underlying problems:
(i) ad-hoc indefinite incomplete updated factorization preconditioners used with a suitable Krylov projection method;
(ii) solution of shifted systems by projection techniques and multilevel incomplete factorization preconditioned algorithms, with reorderings to transform the original problem in a more diagonally dominant one.
Another application involves the solution of large and sparse total least squares (TLS) problems based on Rayleigh quotient iteration. In this approach, the solution of the underlying problem reduces to the solution of a sequence of shifted symmetric positive definite linear systems. In [14] Björck et al. proposed solving these linear systems by the conjugate gradient method preconditioned by the (complete) Choleski factorization of the normal system matrix. We plan to design and analyze iterative algorithms which generate sequences of linear systems whose condition numbers are better, by using techniques based on incomplete updated and updated approximate inverse factorizations.
b) Semiseparable structures
Matrices with generalized semiseparable structures are gaining a great interest as computational tool to solve eigenvalue problems. The recent research in this field has opened new perspectives for what concerns the design of efficient numerical algorithms for special eigenvalue problems, e.g., associated with generalized companion or quasi-unitary Hessenberg matrices.
Moreover, we want to understand the computational relevance of prescribing the diagonal term in the similarity transformation of a symmetric matrix into diagonal-plus-semiseparable form, in order to speed up the computation of its eigenvalues.
c) Multilevel structures
We are interested in the analysis and in the synthesis of fast algorithms for the solution of multilevel structured linear systems (analysis of preconditioners for the conjugate gradient method, of the associated properties of clustering and spectral equivalence, and analysis of multigrid methods with a special emphasis in the choice of the projector/smoother pair). More in detail, we will be interested in the following aspects:
- Preconditioning of multilevel Toeplitz structures, trying to generalize to the multivariate case the optimality results given in [40].
- Investigation of a ''fattening'' of algebras, by taking matrices of the form U T U* where T is a matrix with a given sparsity pattern and for which the solution of an associated linear system has a complexity bounded by the cost of multiplying U or U* by a vector (typically O(n log n) operations). We would like to understand if this new proposal, which sensibly enriches the ordinary algebras where T is just diagonal, is sufficient for finding preconditioners which are superlinear and/or optimal in the multilevel polynomially ill-conditioned case (which is impossible if T is diagonal).
- Extension of the multigrid optimality proof in [2] to the multilevel case and applications to image restoration problems (see B2-a) and to the PDEs (especially in connection with the dense structured systems arising from the Sinc-Galerkin methods applied to elliptic PDEs).
B1) Continuation of previous research topics
a) Approximation by rational functions
We want to pursue our previous research on interpolation and approximation problems with rational functions, particularly with respect to the analysis of structured conditioning issues and optimal pole placements.
b) Inverse problems in imaging
If we use iterative solvers for linear inverse problems, the iteration number represents a regularization parameter; therefore a first goal is the automatic estimate of such parameter. Another direction involves the extension of regularizing families of preconditioners (e.g. filtering optimal and superoptimal, as described in the Scientific Background) to the reconstruction of non-negative images, and their application to problems related to the adaptive optics device equipping the LBT system.
We also plan the analysis and design of new efficient algorithms for linear systems generated by Tikhonov-like regularization. We would restrict our attention to regularization operators representing the identity, the first or the second derivative. The related normal equations are of parametric form, and should be solved for several values of the Tikhonov parameter. The proposed algorithms are new iterative methods using updated incomplete factorizations generalizing those introduced in [3] (which can be applied directly if the least squares are penalized by means of the solution norm).
Finally, a large amount of work is necessary to optimize the image reconstruction algorithms (i.e. OS-EM method for multiple images). For instance, the LBT restoration problem will require the treatment of images with very high-dynamic range (young binary stars or extrasolar planets). In such a case, the problem will be investigated along two different lines. The first one concerns the study of an appropriate functional in order to take into account the particular features of the object. The second one is a sophisticated post-reconstruction denoising in order to preserve both huge gradients and weak structures.
c) PDEs
The convergence properties of the preconditioned GMRES solution will be investigated for linear systems discretizing the convection-diffusion equation with variable diffusion coefficient. The preconditioner is based on the diffusive part of the operator and we plan to consider a finite difference discretization on a d-dimensional rectangular domain. We plan to show the existence of a proper cluster for the eigenvalues of the preconditioned matrix and then the superlinear behavior of iterations. A preliminary analysis has shown that the structure of the cluster is not influenced by the discretization but the number of outliers linearly increases with respect to the viscosity parameter.
The same techniques will be applied to time-dependent convection-diffusion equations arising in a human metabolism model, which has been introduced at the MIMS center of Cleveland.
B2) New techniques
a) Regularization by multigrid
It is well known that for retrieving the real image from the observed one corrupted by blurring and by noise, it is necessary to resort to some regularizing methods. There exist many procedures in this direction as Tikhonov, Riley, iterative methods as CG, CGNE, Landweber etc (see [25]). However often the most precise ones are also terribly slow. We would like to investigate the possibility of using a multigrid technique (based on the algebraic approach in [2,47]) for the regularization problem as well. Our goals are the following:
- obtain the same reconstruction quality as the best regularizing methods but with a great saving in computation time;
- adapt the method to every boundary condition (see the subsequent point b)) because the algebraic method described in [2] is very versatile with respect to the different structures.
b) Boundary condition effects
We concentrate our efforts in the direction of anti-reflective BCs by considering two goals:
- a more precise analysis of the (non-canonical i.e. mixed structures) algebra of matrices appearing with the anti-reflective BCs;
- the study of the role of the noise and more precisely how to use a regularizing method (which is necessary due to the noise and to the ill-posedness of the problem) in connection with the anti-reflective BCs: we would like to modify the classical normal equations and Tikhonov techniques in such a way that the structure of algebra of the resulting system is exploited in the best possible way. It is understood that the main aim is to obtain a better precision with respect to regularizing methods applied with the other BCs.
c) Denoising and edge detection by wavelets
Astronomical images are corrupted by a large amount of noise. Denoising methods are required in many cases, and in particular we will investigate three cases: chopped and nodded images (near-infrared images), measured PSFs used in classical restoration methods, over-iterated reconstruction. The study will be performed using wavelet-based shrinkage methods in order to optimize for any problem the suitable threshold method.
Moreover, it is well known that the wavelet approach can be especially successful in detecting the edges of an image. We would like to study the following research themes:
- finding a relation between the classical wavelet methods for deblurring of images (noisy and blurred) and the multigrid methods (see B2-a) for deblurring of images (noisy and blurred);
- incorporate the more precise anti-reflective BCs (see B2-b)) into a wavelets framework in order to improve the precision of the resulting reconstruction.
B3) New applications
a) Nonlinear inverse problems
The two-level "Quasi-Newton" approach previously implemented for Remote Sensing problems, as described in the Scientific Background, has revealed the possibility of using structured matrix tools in the new applicative context of nonlinear inverse problems. In this project we plan to apply the same technique to a non-linear inverse scattering problem arising in electrical engineering, where the dielectric permittivity has to be determined.
b) Web search engines
Here the structure that dominates the problem is indicated by the key words "sparsity" and "block structure": a further rank-one matrix multiplied by 1-c, 0<c<1, is added for modelistic reasons (see [36]). When c is far from one, the computation of the positive PageRank(c) vector (left stationary vector) can be performed quite fastly by the standard power method since the second large eigenvalue has at most modulus c. However, if c is close to 1 then the technique is too slow also due to the huge size of the WEB matrix. We would like to express the positive vector PageRank(c) as a rational expansion of PageRank(1) in such a way that its computation can be obtained eventually through vector extrapolation methods.
c) Identification problems
Non-classical inverse eigenvalue problems for tridiagonal matrices and other closely related matrix structures (also including diagonal-plus-semiseparable matrices) are recently arising as models in identification problems in civil engineering, where localized damages or constitutive coefficients in (multilayer) rods and frames are to be detected from measures of frequency responses or resonances. We are aimed at solving both theoretical and computational issues arising in this framework, e.g., identifiability results, perturbative analysis, and synthesis of numerical methods to identify a properly structured matrix from spectral data.

All the research themes considered here require numerical validations and the development of dedicated prototype software. Hence the group needs to incorporate additional young people, for which a substantial part of funding will be used: temporary research positions, fellowships and occasional jobs are planned to start during the two years of the project.
The group includes researchers of several different universities and a strong cooperation is needed to obtain the expected results, also with the help of external collaborators: M.Benzi, Atlanta-USA (topics A2-a), D.Calvetti and G.Saidel, Ohio-USA (topic B1-c), G.Golub, Stanford-USA (topics A1-a, A2-a, B1-c), A.Morassi, Udine-Italy (topic B3-c), D.Noutsos and P.Vassalos, Ioannina-Greece (topics A1-a, A2-c), M.Pastorino, DIBE Genova-Italy (topic B3-a), M.Tasche, Rostock-Germany (topic B2-c) and people of other groups in this project (point A2-b).
Therefore the funding will cover also several travel expenses due to individual meetings and participation to conferences.

BINI	DARIO ANDREA	bini@dm.unipi.it
MAT/08 - Analisi numerica
Università di PISA
Facoltà di SCIENZE MATEMATICHE FISICHE e NATURALI
Dipartimento di MATEMATICA "Leonida Tonelli"

DI BENEDETTO	FABIO
Professore Associato	17/05/1963	DBNFBA63E17E463A
MAT/08 - Analisi numerica
Università degli Studi di GENOVA
Facoltà di SCIENZE MATEMATICHE FISICHE e NATURALI
Dipartimento di MATEMATICA
010-3536883 (Prefisso e telefono)	010-3536752 (Numero fax)	dibenede@dima.unige.it (Email)

1.	DI BENEDETTO F.; SERRA CAPIZZANO S. (2002). A note on the superoptimal matrix algebra operators LINEAR AND MULTILINEAR ALGEBRA. (vol. 50 pp. 343-372)
2.	DI BENEDETTO F. (2000). Matrix structures for image applications: some examples and open problems NOTES ON NUMERICAL FLUID MECHANICS. (vol. 73 pp. 243-249)
3.	DI BENEDETTO F.; SERRA CAPIZZANO S. (1999). A unifying approach to abstract matrix algebra preconditioning NUMERISCHE MATHEMATIK. (vol. 82 pp. 57-90)
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.	DI BENEDETTO F. (1995). Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices SIAM JOURNAL ON SCIENTIFIC COMPUTING. (vol. 16 pp. 682-697)

		Numero	Mesi uomo 1° anno	Mesi uomo 2° anno	Totale mesi uomo
Personale universitario dell'Università sede dell'Unità di Ricerca		3	15	13	28
Personale universitario di altre Università		5	28	30	58
Titolari di assegni di ricerca		1	9	7	16
Titolari di borse	Dottorato	0
	Post-dottorato	0
	Scuola di Specializzazione	0
Personale a contratto	Assegnisti	1	9	7	16
	Borsisti	0
	Dottorandi	0
	Altre tipologie	0
Personale extrauniversitario		0
TOTALE		10	61	57	118

		Numero	Mesi uomo 1° anno	Mesi uomo 2° anno	Totale mesi uomo
University Personnel		3	15	13	28
Other University Personnel		5	28	30	58
Work contract (research grants, free lance contracts)		1	9	7	16
PHD Fellows & PHD Students	PHD Students	0
	Post-Doctoral Fellows	0
	Specialization School	0
Personnel to be hired	Work contract (research grants, free lance contracts)	1	9	7	16
	PHD Fellows & PHD Students	0
	PHD Students	0
	Other tipologies	0
No cost Non University Personnel		0
TOTALE		10	61	57	118