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

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

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
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