Area Scientifico Disciplinare: Scienze Matematiche

Fabio Di Benedetto, born in 1963, received the "laurea" in Mathematics in 1987 at the University of Pisa with 110/110 marks "cum laude". After some fellowships from CNR (the National Research Council), in 1990 he became Researcher in Numerical Analysis at the Department of Mathematics of the University of Genova; from 2000 he is Associate Professor of Numerical Analysis at the same Department.
His teaching activity includes from 1994 classes of Numerical Calculus for undergraduate students in Computer science, Material sciences and Mathematics; he has been advisor of several graduate theses in Mathematics and of a phd thesis in Computational Mathematics.
His main research interests involve numerical linear algebra, with special emphasis in structured matrices (namely Toeplitz matrices) and their applications to image processing. He is author and coauthor of about 25 papers; his refereeing activity concerns Mathematical Reviews and international journals like SIAM Journal on Numerical Analysis, SIAM Journal on Matrix Analysis and Applications, SIAM Journal on Scientific Computing, Linear Algebra and its Aplications, BIT and Calcolo.
He cooperated to the organization of two INDAM international workshops made in Cortona on structured matrices, in 1996 (with the publication of related proceedings) and 2000.

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

1.7.2 Personale universitario di altre Università

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

1.7.3 Titolari di assegni di ricerca

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

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

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

1.7.5 Personale a contratto da destinare a questo specifico programma

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

1.7.6 Personale extrauniversitario dipendente da altri Enti

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

Iterative techniques for matrix structures and applications to PDE, imaging and approximation problems

---

2.2 Settori scientifico-disciplinari interessati dal Programma di Ricerca

MAT/08 - ANALISI NUMERICA INF/01 - INFORMATICA

---

2.3 Parole chiave

TOEPLITZ MATRICES ; PRECONDITIONING FOR STRUCTURED MATRICES ; MULTIGRID FOR STRUCTURED MATRICES ; STRUCTURED MATRICES ; LBT IMAGING ; SPECT

---

2.4 Base di partenza scientifica nazionale o internazionale

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 Toeplitz solvers.

Regarding the spectral properties, we recall the distributional results due to Szego, Widom, Avram, Parter (see [14]) and culminated in the work of Tyrtyshnikov [55] concerning the "global behaviour" of the spectra of Toeplitz sequences. Extensions to matrix valued generating functions and to sequences arising in the preconditioning theory [40,41,25] 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" [52] or that possess different "local structures" [44] and including, as special instances, discretizations of differential operators with boundary conditions [47] and weighted Laplacians of graphs [44].
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 [14,39,41,49] 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²) e 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 [30] (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 [51] proposed first in 1986), even though trigonometric transforms recently received particular attention [11,29].
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 [50,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 [16]) that leads to optimal and superlinear [38] 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 [37].
These ideas have been further exploited by Di Benedetto, Serra Capizzano, R.Chan, Potts and Steidl in a matrix algebra setting (see e.g. [19,43,17]). Now the problem is reduced to the band case for which we have optimal iterative solvers (the multigrid method [26] 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 [36] 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 [26] seems to be still optimal. 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).

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, partial differential equations (PDE) and functional approximation.

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 reconstruction of atmospheric images, either by the PCG solution of a least-squares problem related to Tykhonov regularization (see e.g. [34]) or by the definition of a parameter-dependent preconditioner, having itself a regularization effect [28].
A very recent 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.
Another challenging problem in image processing, which requires the solution of very large linear systems, is the tomographic problem denoted as SPECT (Single Photon Emission Computerized Tomography) [33]. Here the data size is of order 10⁶, but the structures arising in the matrices are more hidden.

Banded Toeplitz matrices are the main ingredient in a superlinear preconditioning strategy [42,47] for Finite Differences discretization 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. Moreover a wide numerical experimentation suggests that the strategy is optimal in the degenerate elliptic case as well.
Finite difference discretization of time-dependent partial differential equations by means of linear multistep formulas in boundary value form generates perturbations of nonsymmetric block Toeplitz matrices [3]. Circulant-like preconditioners were introduced in [4]. It was shown in [5] that these preconditioners can be quite effective, provided that the norm of the inverse of the preconditioner has at most linear growth with respect to the size of the component matrices.

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

This group, including seven mathematicians and one computer scientist, is characterized by a long-standing research experience in the fields of the spectral analysis of wide classes of structured matrices [24,25,44,49], of the solution of Toeplitz linear systems [19,20,22,23,37,43] and eigenvalue problems [10,21], of the regularization of inverse problems arising in several applications [15,6]. Specific and fundamental expertises are also present in the group, concerning the numerical treatment of PDEs [47,48] and the application of matrix structures to medical [9] and infrared astronomical [8] images and time-dependent differential problems [4,5].

---

2.4.a Riferimenti bibliografici

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

---

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

According to the discussion in the Scientific Background, the main expertises of the group are found in topics concerning Toeplitz and other matrix structures, iterative techniques, PDEs and inverse problems. The research program aims to investigate further open problems along these lines and to create new feedback between these areas.
More precisely we want to study the multilevel and the non Hermitian case owing to its strong interest in the discretization of infinite dimensional problems on multidimensional domains (differential problems, integral equations with special attention to image restoration etc.) and because of its intrinsic difficulty: we point out that most of the relevant open problems regarding iterative methods for Toeplitz matrices concern the non Hermitian, the Hermitian nondefinite and the multilevel cases.
Within this class of problems we would like to focus our attention on three main directions: Spectral and Structural Analysis of matrix sequences [in partial collaboration with R. Bhatia, Indian Statistical Institute, New Delhi, P. Tilli, Scuola Normale Superiore, Pisa and E. Tyrtyshnikov, Russian Academy of Sciences, Moscow]; Analysis and Design of ad hoc algorithms for structured matrices [in partial collaboration with B. Beckermann, Université Lille 1, the Group of R. Chan, Chinese University of Hong Kong, A. Frangioni, University of Pisa, A. Kuijlaars, KU Leuven and T. Huckle, TU Munchen]; Application to specific problems in Applied Mathematics [in partial collaboration with the Group of R. Chan and the group #1 in this project]; prototype software products are also planned, as described below.
 

A) Theoretical aspects
 

The topics considered here link the fields of convergence analysis of Krylov iterations, asymptotic linear algebra and operator theory, with particular emphasis on regularization operators for inverse problems.
 

A1) Convergence analysis of iterative methods
The discretization of some PDEs leads to Hermitian nondefinite linear systems (e.g. Helmholtz equation) or to non Hermitian linear systems (e.g. time dependent problems). For these cases we plan to give localization and asymptotic results on the eigenvalues of the preconditioned and non preconditioned structures. In particular, we will consider the case of block Toeplitz-like problems preconditioned by block circulant-like matrices and the case where the preconditioners are banded and Toeplitz. We plan to illustrate how these properties can be related to the fast convergence rate of Krylov solvers such as GMRES and BiCG-like and state some convergence bound theorems.
 

A2) Asymptotic linear algebra
Given a sequence of matrices A_n and by considering the discrete measure obtained as arithmetic mean of Dirac's Deltas centered in the singular values of A_n, we would like to identify the limit distribution (if it exists!).
a) We think that it is possible to generalize the notion of Locally Toeplitz sequence (see [52]) which is inherently unilevel to the multilevel case by considering a kind of "topological closure" too. The interest relies in the fact that this new notion allows to study, in a unified manner, the limit distribution of sequences discretizing PDEs on Peano-Jordan measurable domains, with any boundary condition and by using Finite Differences or Finite Elements, and related preconditioned matrices with application to the analysis of the convergence speed of associated PCG methods.
b) We would like to enlarge the class of Test Functions in the distributional results for Toeplitz matrices. For instance if the symbol f belongs to the L^p space then the unique conditions on the Test Functions should be the continuity and a certain growth condition. This would allow to write down precise asymptotical estimates on the Schatten p norms of Toeplitz matrices with related applications to the clustering in the matrix algebra preconditioning.
c) We want to study the classical conditioning of Laplacians of Graph that occur as subproblems in the application of Interior Point Methods for the numerical solution of some constrained optimization problems. Moreover, we will analyze the structured conditioning [27] for matrices having a specific displacement rank structure (Cauchy, Vandermonde): in such situations, if the algorithm is able to properly exploit the structure, then the usual condition number gives a too pessimistic foresight of the error since the algorithmical error can be modeled through perturbations of the initial data that are structure preserving.
 

A3) Connections with operator theory
The first direction concerns the analysis of relationships between infinite dimensional problems expressed in the language of Operator Theory (following the Boettcher-Silbermann approach [14]) and finite dimensional problems in Asymptotical Linear Algebra in order to help the scientific communication among people working in these two fields where a different mathematical language is used. The second direction concerns the study of preconditioned iterative methods in the framework of the classical analytical theory of regularizing operators for ill-posed problems [6].
 

A4) Analysis of abstract results on the multilevel preconditioning.
It is known that, unlike the unilevel case, for multilevel Toeplitz structures it is impossible to find superlinear preconditioning sequences of circulant type [50] and of abstract type [46]. We want to specialize the analysis by considering all the algebras of trigonometric type and by giving a topological characterization of the set of the generating functions f for which the associated Toeplitz sequences do not possess a superlinear preconditioning in a given sequence of algebras. We believe that an analogous negative result is true if we require weaker spectral properties which could ensure the optimality of the preconditioner. The philosophical impact of the latter point is noteworthy since it would indicate that in a multilevel setting (including PDEs discretizations) the only hope of finding optimal methods is to use a blending of multigrid techniques and banded preconditioners (see points B1 and C2a) and multilevel Schur complement based strategies; a temporary research position is planned for this specific point of the program.
 

B) Computational issues
 

We will cover the topics of multigrid techniques, preconditioning strategies for solving linear systems and eigenvalue problems, and numerical methods for less common structures.
 

B1) Multigrid methods
Analysis and Design of multigrid algorithms for the numerical solution of structured linear systems with attention to banded multilevel matrices of Toeplitz and trigonometric type. We want to understand the geometrical and structural properties of the projecting operators in order to obtain optimal two-grid and multigrid procedures whose cost is linear in the banded multilevel case. The importance of this topic relies on the negative results for the preconditioning in a matrix algebra (see the previous item and the explanation given in the Scientific Background). More precisely we would like to study algebraic multigrid algorithms in the following cases:
a) Toeplitz and Tau structures (following the analysis in [26]);
b) Circulants;
c) Cosine-III matrix algebra;
d) Toeplitz-plus-diagonal structures;
e) Projected structures.
The first two classes are of interest in the numerical treatment of elliptic differential problems with Dirichlet and periodic boundary conditions respectively, and the third class is important in image restoration. Moreover the fourth class is of importance in the numerical treatment of elliptic PDEs by exponentially convergent methods (e.g. the "sinc" method) and the fifth class naturally occurs when the differential operators are defined on plurirectangles in place of multidimensional rectangles (with reference to both FEM and FD discretizing techniques). Finally, from a theoretical point of view, we would like to build up a unifying approach for the design of multigrid algorithms for "self-similar" matrix structures.
 

B2) Preconditioning of structured linear systems
We want to focus our attention on the regularizing features of the "superoptimal" preconditioning strategy proposed by Tyrtyshnikov (see [54]) and of "filtered" preconditioners that can be obtained as modification of the superoptimal operators. Several questions are open: how to construct a multilevel preconditioner at a low computational cost, the proof of spectral results under general assumptions, their use in connection to nonsymmetric iterations and the possible extension to inverse problems where the non-negative constraint is required. A further point of the program involves the proposal of a new preconditioner for shifted linear systems as (A+eI)x=b, where A is SPD and e is a nonnegative parameter, arising in several frameworks. Our preconditioner is based on a modification of factorized approximate inverses. Several experiments and a preliminary analysis have given quite encouraging results for many classes of matrices.
 

B3) Continuation methods for eigenvalue problems
Another field of research considered in this program is the problem of finding really fast numerical methods for the computation of all the eigenvalues of a Toeplitz matrix, which is still open. It is surprising that the most efficient preconditioning techniques allow us to solve a Toeplitz linear system in O(n log n) operations, while the best known eigensolver for general Toeplitz matrices [53] requires O(n²) operations for each eigenvalue. The complexity could be reduced by the availability of very good approximations of Toeplitz matrices provided by preconditioning, whose explicit diagonalization is known. We plan to make a feasibility study for two specific techniques: isospectral flows [56] and homotopy continuation [18].
 

B4) Other structures
We want to continue the development of fast and stable algorithms for the QR factorization of Cauchy-like matrices. Moreover, we will focus our attention on spectral and computational properties of 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 [24].
 

C) Specific applications
 

Three main fields will be investigated: integral equations arising in inverse problems, partial differential equations, approximation and quadrature of functions.
 

C1) Inverse problems in imaging
a) Reconstruction of LBT images
It is very important, from an application point of view, to devise very efficient numerical methods for solving the LBT problem, due to the very huge number of data.
Our program consists of three steps. First, we want to continue the application of the most classical deconvolution methods to the problem of multiple images [7], in order to provide a full comparison of them. Next, we want to study a careful exploitation of matrix structures naturally arising in the formulation of the problem, in order to obtain an improvement in the performances. Finally, there is the perspective of using infrared imaging in the context of the LBT project; in view of this, we want to pursue the research on "chopping and nodding" [8] techniques.
b) Reconstruction of SPECT images
We plan to investigate in more depth fast algorithms based on the natural pixel model [9], which reflects the rotational invariance of the system. The structure involving the spatial variables has not been yet exploited (perhaps multigrid will be helpful in this context); the model must be refined in order to take into account attenuation effects; a careful experimental validation of the methods is needed.
 

C2) Linear systems related to PDEs
a) Elliptic and semi-elliptic problems
We will be concerned with the analysis and Design of ad hoc algorithms for the numerical solution of structured multilevel linear systems with special attention to the discretizations by Finite Differences, Finite Elements and strong Collocation [31] methods of Elliptic PDEs with nonconstant coefficients and over rectangular and non rectangular domains. We plan to analyze preconditioners for the PCG method and the related clustering features and spectral equivalence. More specifically, in analogy with [42,47], we expect a strong clustering when the coefficients are two times continuously differentiable and therefore a substantial improvement with respect to the PCG algorithms based on matrix algebras [16], incomplete factorizations or matrix polynomials [2]. Finally we think that this approach will lead to the first optimal preconditioning techniques in the case of semi-elliptic differential problems also in the case of general plurirectangle domains.
b) Time-dependent problems
We want to study circulant-like block preconditioners for nonsymmetric linear equations arising in time-step integrators in boundary value form. In particular, our goal is the analysis of the spectrum of the eigenvalues, of the conditioning and other related properties.
 

C3) Approximation and quadrature
Three different topics will be investigated. The use of "Matrix technology" will enable to determine the limit distribution for the zeros of sequences of orthogonal polynomials with recurrence periodic coefficients depending on a parameter (following the suggestions contained in [32]). We would like to analyze the structure of the related Jacobi matrices which should be equi-distributed with respect to special Toeplitz or generalized Locally Toeplitz sequences. Moreover we want to perform the quadrature of functions of L¹ class and the numerical analysis of the essential range of measurable functions by using the ergodic formulas discussed in [55,40,45]; we will also consider the possibility of finding techniques for accelerating the convergence in the case where the involved symbol is more regular. Finally, the deep knowledge on structured matrices of Cauchy, Pick and Vandermonde type will be applied to the analysis of algorithms for the solution of the Nevanlinna-Pick problem and other polynomial and rational interpolation problems.
 

D) Software
Software development is required for points B1 and C1 of the research program. We are interested in realizing a prototype of Software implementing the multigrid algorithms discussed above, in order to test the proposed methods on applicative problems of realistic dimensions. The development of dedicated prototype software is also necessary in order to perform a correct numerical validation of the advanced methods introduced for LBT and SPECT imaging; temporary research positions specifically planned could be very helpful for this crucial part of the project and for the a posteriori analysis of related mathematical issues.
 

The group includes researchers of several different universities, and a strong cooperation is needed to obtain the expected results. Therefore the funding will cover several travel expenses due to individual meetings and participation to conferences. Moreover, some topics of the program require additional young people both for research and software development; in view of this, part of the funding asked will be used for payment of temporary research positions and occasional jobs.