Area Scientifico Disciplinare: Scienze Matematiche

Sebastiano Seatzu has been full professor of numerical analysis at the University of Cagliari (Italy) since 1980 and professor of operational research from 1981-1995. He served as chairman of the Department of Mathematics from 1986-1989 and as chairman of the Electrical Engineering Degree Council from 1980-1994. After his graduation in physics in 1965, he got interested in numerical analysis, in particular in approximation theory and the numerical solution of integral equations. His recent work includes numerical methods for solving integral equations of the first kind, numerical linear algebra and orthogonal functions. He has published 65 papers and is a managing editor of Calcolo, a quarterly on numerical analysis supported by the Italian National Research Council, and an associate editor of Advances in Computational Mathematics.

1. VAN DER MEE C.V.M., RODRIGUEZ G., SEATZU S. (2002). Semi-infinite multi-index perturbed block Toeplitz systems. LINEAR ALGEBRA AND ITS APPLICATIONS. In V. Mehrman, D. Bini, G. Heinig, and E. Tyrtyshnikov, editors, Proceedings of the workshop on Structured matrices: Analysis, Algorithms and Applications, Cortona September 25-29, 2000, to appear.
2. VAN DER MEE C.V.M., NASHED M.Z., SEATZU S. (2002). Sampling expansions and interpolation in unitarily translation invariant reproducing kernel Hilbert spaces. ADVANCES IN COMPUTATIONAL MATHEMATICS. to appear.
3. VAN DER MEE C.V.M., RODRIGUEZ G., SEATZU S. (2001). Spectral factorization of bi-infinite multi-index block Toeplitz matrices. LINEAR ALGEBRA AND ITS APPLICATIONS. vol. 343-344, pp. 355-380 Special Issue on Structured and Infinite Systems of Linear Equations.
4. GOODMAN T.N.T., MICCHELLI C.A., RODRIGUEZ G., SEATZU S. (2000). On the Cholesky factorization of the Gram matrix of multivariate functions. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. vol. 22(2), pp. 501-526.
5. VAN DER MEE C.V.M., RODRIGUEZ G., SEATZU S. (1998). Block Cholesky factorization of infinite matrices, and orthonormalization of vectors of functions.

In CHEN Z., LI Y., MICCHELLI C.A., XU Y. Advances in Computational Mathematics. (vol. 202, pp. 423-455). Lecture Notes in Pure and Applied Mathematics. NEW YORK AND BASEL: M. Dekker Inc. (UNITED STATES).

1.7.2 Personale universitario di altre Università

Nº	Cognome	Nome	Università	Dipart./Istituto	Qualifica	Settore scient.	Mesi uomo
							2002	2003
Personale docente:
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.	THEIS	DANIELA	MATEMATICA	2001	16  (ore: 2200)

1.7.5 Personale a contratto da destinare a questo specifico programma

Nº	Qualifica	Costo previsto	Mesi uomo

1.7.6 Personale extrauniversitario dipendente da altri Enti

Nº	Cognome	Nome	Ente	Qualifica	Mesi uomo

Infinite linear systems with structured matrix and applications

SPECTRAL FACTORIZATION ; INFINITE STRUCTURED MATRICES ; STRUCTURED INTEGRAL EQUATIONS ; INVERSE SCATTERING ; REGULARIZATION METHODS ; TOEPLITZ MATRIX

On each of the topics indicated there exists an extensive literature represented by numerous publications in specialized journals, book series and proceedings of international conferences. Many papers concern functional analysis, linear operator theory and numerical analysis. There are also numerous problems of applied interest, in particular those in acoustical, optical and electromagnetic inverse scattering whose solution depends in an essential way on the factorization of integral operators with structured nuclei or their discrete analogs.
The results on functional analysis and operator theory that are of major interest to this project, can be found in the book series Operator Theory and Applications and in particular in [16], [17], [5], [9] and [15]. The most interesting applied results, including the most effective methods to solve many inverse scattering problems, can be found in [8], [11] and [27]. As regards the spectral factorization of infinite one-index Toeplitz matrices, the publications of primary interest are [15], [5] and [6], while the results of specific interest to integral equations are essentially contained in [15], [19], [16] and [17].
The contributions of the local unit on the spectral factorization of Toeplitz matrices are contained in [20], [30], [31], [33] and [34].
In the one-index case in particular, members of the local unit have not only made an exhaustive analysis of the spectral factorizations of banded matrices found in the literature, but members of the research unit have also proposed two numerical methods for the spectral factorization of bi-infinite block Toeplitz matrices in weighted Banach algebras. The first method is based on the theory of matrix polynomials and the second, when applied to banded matrices, represents a generalization of the ``band extension" method proposed in 1989 by Gohberg, Kaashoek and Woerdeman in [17] and [39].
The two methods have also been used for a comparison of the numerical efficiency of the solution of applied problems, at the identification of the limiting profile in the asymptotic process of orthonormalization, by the Gram-Schmidt method, of a sequence of function vectors [21], and at the solution of the Poisson equation in an infinite strip [32].
In the multi-index case there is almost no literature because of the relative non existence of an algebraic theory on multi-index matrix operators, in spite of the objective interest in the topic in many applied fields. In the latter situation, but exclusively in the scalar case, two spectral factorization methods in weighted Banach algebras have been developed with respect to a fixed linear order [22], theoretically based on spectral factorization results in weighted Wiener algebras [12].
The results obtained allow one to characterize the type of decay of either the elements of the inverse of the matrix or of the factors, in terms of the characteristics of the matrix itself. One of the two methods, which is easily implemented using the FFT, has been used to identify the limiting profile in the asymptotic process of orthonormalization, by means of the Gram-Schmidt method, of sequences of uniform translates of a fixed function of several variables. Because the translates depend on the fixed linear order, numerical examples have been supplied based on linear box splines to illustrate the dependence of the limiting profile on the fixed linear order. The numerical efficiency of the two methods proposed has also been compared to the solution of a semi-infinite system whose matrix appears in the literature as an example of a positive definite banded multi-index Toeplitz matrix which has unbanded Cholesky factors. This is specific to the multi-index case in the sense that, in the one index case, the Cholesky factors of a banded positive definite matrix are always banded.
In the multi-index block case, only partial results on the factorization have been obtained. In particular, we have not yet succeeded in characterizing the decay type of the elements of the Cholesky factors of a positive definite multi-index block Toeplitz matrix in terms of the decay type of the elements of the matrix under consideration. On the other hand, a ``band extension" method has been proposed in the two-index case which is based on the Christoffel-Darboux formula for two-variable polynomials [14].
As regards the solution of infinite linear systems, the major result of primary interest to the project obtained by the local unit concerns the solution of semi-infinite Toeplitz systems and their perturbations. In [32] and [35], numerical methods have been proposed for their solution in weighted Banach algebras. The method to solve the perturbed systems is new and its numerical efficiency has been confirmed by either the solution of the Poisson equation on a strip or by the solution of systems whose matrices are Gram matrices associated to the positive integer translates of a fixed vector of functions.
The research on linear integral equations we foresee is based in part on results on their discrete analogs [36]. For the numerical solution of integral equations with structured kernels (such as convolution equations), it is most useful to implement a discretization that leads to a structured linear system based on results recently obtained on sampling in reproducing kernel Hilbert spaces [3] and [29]. Because many applications, such as inverse scattering or image processing problems, are reduced to an integral equation of the first kind, we need structured regularization methods to deal with the corresponding linear system with ill-conditioned structured matrix. Regularization theory [24] and some results obtained by the local unit [7] and [38], by applying fast algorithms for matrices with displacement structure [25], [10], [18] and [26] represent a good starting point for the study of this problem.
To produce prototypical software on the solution of the semi-infinite systems, the numerical codes developed locally to solve scalar and block, one-index and scalar multi-index, Toeplitz systems and their perturbations will be used. To do so, the collaboration with the other units will be essential to choose optimal algorithms to solve finite linear systems of large dimension, as required by the use of the projection method.

[1] T. Aktosun, M. Klaus, and C. van der Mee. Wave scattering in one dimension with absorption. J. Math. Phys., 39, 1957-1992 (1998).
[2] T. Aktosun, M. Klaus, and C. van der Mee. Direct and inverse scattering for selfadjoint Hamiltonian systems on the line. Integral Equations and Operator Theory 38, 129-178 (2000).
[3] A. Aldroubi and K. Groechenig. Nonuniform sampling and reconstruction in shift-invariant spaces. SIAM Review 43(4), 585-620 (2001).
[4] D. Bini, G.M. Del Corso, G. Manzini, and L. Margara. Inversion of circulant matrices over Zm . Math. Comp. 70, 1169-1182 (2001).
[5] A. Boettcher and B. Silbermann. Analysis of Toeplitz operators. Springer, New York, 1990.
[6] A. Boettcher and B. Silbermann. Introduction to large truncated Toeplitz matrices. Springer, New York, 1999.
[7] C. Brezinski, M. Redivo-Zaglia, G. Rodriguez, and S. Seatzu. Multiparameter regularization techniques for ill-conditioned linear systems, 2001, to appear.
[8] K. Chadan and P. C. Sabatier. Inverse Problems in Quantum Scattering Theory, 2nd ed., Springer, New York, 1989.
[9] K. Clancey and I. Gohberg. Factorization of Matrix Functions and Singular Integral Operators, volume 3 of Operator Theory: Advances and Applications. Birkhauser, Basel-Boston, 1981.
[10] T. Constantinescu, A.H. Sayed, and T. Kailath. Displacement structure and H-infinity problems. System theory: Modeling, analysis and control. Kluwer, Boston, 2000.
[11] W. Eckhaus and A. van Harten. The inverse scattering transformation and the theory of solitons. An introduction. North-Holland Mathematics Studies, 50. North-Holland, Amsterdam, 1981.
[12] T. Ehrhardt and C. van der Mee. Canonical factorization of continuous functions on the d-torus. Proc. Amer. Math. Soc., to appear.
[13] J. Engwerda, A.C.M. Ran, and A.L. Rijkeboer. Necessary and sufficient conditions for the systems of a positive definite solution of the matrix equation X+A^*X^{-1}A=Q. Linear Algebra Appl. 186, 255-275 (1993).
[14] J.S. Geronimo and H. Woerdeman. Positive extensions and Riesz-Fejer factorization for two-variable trigonometric polynomials, to appear.
[15] I.C. Gohberg and I.A. Feldman. Convolution Equations and Projection Methods for their Solution, volume 41 of Translations of Mathematical Monographs. Amer. Math. Soc., Providence, 1974.
[16] I. Gohberg, S. Goldberg, and M.A. Kaashoek. Classes of Linear Operators, Vol. I, volume 49 of Operator Theory: Advances and Applications. Birkhauser, Basel-Boston, 1990.
[17] I. Gohberg, S. Goldberg, and M.A. Kaashoek. Classes of Linear Operators, Vol. II, volume 63 of Operator Theory: Advances and Applications. Birkhauser, Basel-Boston, 1993.
[18] I. Gohberg, T. Kailath and V. Olshevsky. Fast gaussian elimination with partial pivoting for matrices with displacement structure. Math. Comp., 64(212), 1557-1576 (1995).
[19] I.C. Gohberg and M.G. Krein. Systems of integral equations on a half-line with kernels depending on the difference of arguments. Uspekhi Matem. Nauk, 13(2), 3-72 (1958) (Russian); English translation: Amer. Math. Soc. Transl., Series 2, 14:217-287 (1960).
[20] T.N.T. Goodman, C.A. Micchelli, G. Rodriguez, and S. Seatzu. Spectral factorization of Laurent polynomials. Adv. in Comp. Math., 7:429-454, 1997.
[21] T.N.T. Goodman, C.A. Micchelli, G. Rodriguez, and S. Seatzu. On the limiting profile arising from orthonormalizing shifts of exponentially decaying functions. IMA J. Num. Anal., 18(3):331-354, 1998.
[22] T.N.T. Goodman, C.A. Micchelli, G. Rodriguez, and S. Seatzu. On the Cholesky factorisation of the Gram matrix of multivariate functions. SIAM J. Matrix Anal. Appl., 22(2):501-526, 2000.
[23] Chun-Hua Guo and P.Lancaster. Analysis and modifications of Newton's method for algebraic Riccati equations. Math. Comp. 67, no.223, 1089-1105 (1998).
[24] P.C. Hansen. Rank-deficient and discrete ill-posed problems. Numerical aspects of linear inversion. SIAM, Philadelphia, 1997.
[25] G. Heinig and K. Rost. Algebraic methods for Toeplitz-like matrices and operators. Vol. 13 of Operator Theory: Advances and Applications, Birkhauser, Basel-Boston, 1984.
[26] T. Kailath and A.H. Sayed. Displacement structure: Theory and applications. SIAM Review 37(3): 297-386 (1995).
[27] V. A. Marchenko. Sturm-Liouville operators and applications, Birkhauser, Basel, 1986.
[28] J.W. McLean and H.J. Woerdeman. Spectral factorizations and sum of squares representations via semidefinite programming. SIAM J. Matrix Anal. Appl. 23(3): 646-655 (2001).
[29] C. van der Mee, M.Z. Nashed, and S. Seatzu. Sampling expansions and interpolation in unitarily translation invariant reproducing kernel Hilbert spaces. Adv. Comp. Math., to appear.
[30] C.V.M. van der Mee, G. Rodriguez, and S. Seatzu. LDU factorization results for bi-infinite and semi-infinite scalar and block Toeplitz matrices. Calcolo, 33:307-335, 1996.
[31] C.V.M. van der Mee, G. Rodriguez, and S. Seatzu. Block Cholesky factorization of infinite matrices, and orthonormalization of vectors of functions. In Z. Chen, Y. Li, C.A. Micchelli, and Y. Xu, editors, Advances in Computational Mathematics, volume 202 of Lecture Notes in Pure and Applied Mathematics, pages 423-455, New York and Basel, 1998. M. Dekker Inc.
[32] C.V.M. van der Mee, G. Rodriguez, and S. Seatzu. Solution methods for semi-infinite linear systems of block Toeplitz type and their perturbations. in D. Bini, E. Tyrtyshnikov, and P. Yalamov, editors, Structured Matrices: Recent Developments in Theory and Computations, pages 93-109, New York, 2000. Nova Science Publisher Inc.
[33] C.V.M. van der Mee, G. Rodriguez, and S. Seatzu. Spectral factorization of bi-infinite block Toeplitz matrices with applications. In L. Brugnano and D. Trigiante, editors, Recent Trends in Numerical Analysis, Nova Science Publ., New York, 2000, pp. 203-225.
[34] C.V.M. van der Mee, G. Rodriguez, and S. Seatzu. Spectral factorization of bi-infinite multi-index block Toeplitz matrices. Linear Algebra and its Applications 343-344: 355-380 (2001).
[35] C.V.M. van der Mee, G. Rodriguez, and S. Seatzu. Semi-infinite multi-index perturbed block Toeplitz systems. Linear Algebra and its Applications, 2002, to appear.
[36] S. Proessdorf and B. Silbermann. Numerical analysis for integral and related operator equations. Vol. 52 of Operator Theory: Advances and Applications, Birkhauser, Basel-Boston, 1991.
[37] L. Rodman. Operator Polynomials, Vol. 38 of Operator Theory: Advances and Applications, Birkhauser, Basel-Boston, 1989.
[38] G. Rodriguez, S. Seatzu, and D. Theis. A new technique for ill-conditioned linear systems, submitted, 2001.
[39] H.J. Woerdeman. Matrix and Operator Extensions. CWI Tract 68, Centre for Mathematics and Computer Science, Amsterdam, 1989.

According to what has been agreed upon with the other units, the present unit will conduct its research on the following arguments:
1) analysis of structured infinite multi-index matrices, where "multi-index" pertains to matrices whose (scalar or square matrix) elements are characterized by a pair of vector indices;
2) solution of infinite linear systems with structured matrices and their perturbations;
3) numerical solution of finite linear systems with structured matrix, with particular emphasis on those with an ill-conditioned matrix;
4) application of the results to the numerical solution of integral equations with structured kernels and their perturbations, of particular interest in acoustics, electromagnetics and applied geophysics;
5) development of prototypical software.
1) As regards the first argument, the research will primarily regard the spectral factorization of multi-index block Toeplitz matrices in weighted Wiener algebras. Although this study concerns theoretical aspects of the factorization and the method to analyze them is to use weighted Banach algebras, it is of fundamental importance for the development of efficient numerical methods for spectral factorization and consequently for the solution of semi-infinite linear system with multi-index Toeplitz matrices.
Indeed, because each element of the solution of semi-infinite systems with Toeplitz matrices can be expressed as a series whose coefficients are found from the spectral factorization of the matrix, for its numerical computation it is absolutely necessary to know the asymptotic behavior of its elements. This sort of result exists in the scalar case, as well as for multi-index Toeplitz matrices with scalar elements [12] and [32].
The extension of the methods developed in the scalar case to the block matrix case is impossible, since in these methods the commutativity of products of the elements is used systematically. It is also impossible to extend results on the factorization of one-index block Toeplitz matrices to the multi-index case, since the former is based on the theory of matrix polynomials or on the compactness of Hankel matrices and, in the multi-index case, there does not exist any counterpart of the theory of matrix polynomials [37] and semi-infinite Hankel matrices are never compact.
2) As regards the solution of semi-infinite linear systems with one-index block Toeplitz matrices, we propose to carry out a comparative study of the existing methods as a function of the decay properties of the elements of the system matrix and of the complexity of the method. First of all, this will concern the method based on the theory of operator polynomials proposed in [31], the band extension method in the form proposed in [32], the semidefinite programming method [28], and methods based on solving quadratic matrix equations [13] and [23].
Contrary to what happens in the one-index case, in the case of infinite block Toeplitz systems with multi-index matrices, the research is still in its initial stages, on one hand because of the difficulties connected with the spectral factorization of matrices in weighted Wiener algebras, on the other hand because of the size of the matrix systems one must solve when using so-called projection methods. In this respect the specialized techniques studied by unit 1 will be most useful. We also intend to continue the study of semi-infinite linear systems whose matrices are perturbations of Toeplitz matrices.
The local unit has recently proposed a new method for solving such systems in the one-index block case [32] and is presently completing its extension to the scalar multi-index case. As shown in [32], under hypotheses that are generally satisfied in applications, the computational strategy proposed allows one to solve the perturbed system with a precision that is comparable to that obtainable when solving the unperturbed Toeplitz system. This method has been numerically implemented at the solution of the Poisson equation on an unbounded strip and at the solution of semi-infinite systems arising from the asymptotic process orthonormalization of the uniform translates of a fixed vector of functions on intervals of increasing length [32].
In the multi-index block case, there exist various difficulties: In the first place those connected with the spectral factorization in weighted Wiener algebras, and in the second place that of efficient numerical methods. One theoretical difficulty of particular importance which has no counterpart in the one-index case, is the following: the spectral factorization of a multi-index block matrix in a weighted Wiener algebra does not always have factors in a Banach algebra with the same weight. The local unit has contributed to proving this still unpublished result. In the one-index block case this situation does not occur, because the factors appearing in the spectral factorization and their inverses have the same decay properties. This fact greatly complicates the development of efficient numerical methods for spectral factorization and hence the solution of semi-infinite systems with semi-infinite multi-index block Toeplitz matrices and their perturbations considerably. Recently a ``band extension" method has been developed in the two-index case [14], but so far this method has not led to an efficient numerical algorithm and a comparison of the results thus obtained with the results contained in [32]. The local unit proposes to conduct an accurate study of this method and to make an extensive and exhaustive comparison between the numerical efficiency and the computational complexity of this method and that of the method proposed in [32].
3) The theory and numerical solution of finite linear system with structured matrix will be primarily studied by the other units.
Since finite systems, in particular those that are ill-conditioned, serve for solving linear integral equations of the first kind stemming from inverse scattering (see 4) below), the local unit proposes to also study finite systems with structured matrix, especially those that are ill-conditioned. In general, it is not easy to extend methods developed for one-index systems to multi-index systems, except in the case in which the structured matrix is a circulant [4]. This leads to the suggestion of imbedding a finite Toeplitz system in a circulant system of slightly increased order. The local unit proposes to extend this circulant imbedding method to multi-index Toeplitz systems. To take into account that many such systems of applied interest are ill-conditioned, we propose to develop a regularization method aimed at multi-index Toeplitz systems.
4) Since linear systems with structured matrices can be viewed as the discrete analogs of integral equations with structured nuclei, there exists between the two topics a natural and deep connection that is potentially very fruitful but has so far not been adequately exploited. Fundamentally this depends on the fact that operator theory has so far been developed by functional analysts and structured matrix theory by numerical analysts. One of the principal objectives of this project is to establish a fruitful collaboration between practitioners of the two disciplines, keeping in mind the development of innovative methods for the numerical solution of linear systems and integral equations with structured kernels. From the theoretical point of view, we need to develop discretizations of such integral operators that lead to structured matrices with analogous structural properties and to prove the convergence of the solution of the structured system to the solution of the integral equation. In particular, it seems promising to study their solution in certain Hilbert spaces which allow one to apply sampling theory [3] and [29].
The local unit plans to develop both the necessary theoretical background and efficient computational techniques for the numerical solution of integral equations with structured kernel in the plane and in the half-plane as well as their perturbations. The development of the theory has as a primary goal the extension of the methods developed for finite and semi-infinite systems to integral equations. In particular, we need to further develop regularization methods for ill-conditioned systems and to adapt them to ill-conditioned structured matrix systems. An important field of applications where there exist significant contributions of the local unit [1] and [2], is represented by inverse scattering in acoustics and quantum mechanics.
Moreover, the local unit plans to develop a computational technique for the solution of severely ill-condizioned structured linear systems, which is based on the application of displacement structure properties to Tikhonov regularization. In those cases when the regularization matrix is itself structured, this technique should allow to compute the regularized solution of linear systems with various kind of displacement structure, in particular Toeplitz, Hankel and Cauchy structure, which are of particular nterest in the numerical solution of integral equations with structured kernel.
An interesting engineering application of the methods discussed under 2) concerns the solution of the Helmholtz equation on a thin unbounded strip, which is equivalent to the study of the propagation of either sound waves or electromagnetic waves in a waveguide. There exist two situations of particular applied interest: the first regarding waveguides formed by omogeneous material and the second concerning waveguides containing inhomogeneities restricted to a bounded domain.
The application of finite difference techniques requires the solution of a tridiagonal block Toeplitz system in the first case and of a suitably perturbed system in the second case. The idea is to use the method to solve the perturbed system proposed in [32]. It is not easy to use, because for an effective engineering application of the results one must have available a precise relation between the discretization stepsize and the wavelength, and this makes it necessary to develop particular domain decomposition techniques.
The solution of the same type of problem in the half-plane or in the half-space leads to the solution of multi-index block Toeplitz systems and their perturbations. Being effectively able to solve this problem depends in an essential way on the factorization of multi-index block Toepliz matrices.
An application of strictly numerical interest we deem doable, concerns the generation of preconditioners of sizable (either scalar or block) matrices which are perturbations of positive definite Toeplitz matrices. The basic idea is to associate to each of them the corresponding bi-infinite Toeplitz matrix, to compute the Cholesky factorization of its inverse, reduce the factors to the size required, and use the resulting matrices as preconditioning factors.
Finally, the local unit proposes to apply the theoretical and numerical results on integral equations to the solution of typical problems in applied geophysics and in acoustical and quantum mechanical inverse scattering. More precisely, in applied geophysics we propose to use these results to solve integral equations connected with the identification of underground inhomogeneities by acoustical and seismical methods and, in acoustical and quantum mechanical inverse scattering, to solve integral equations with kernels depending on the sum of its arguments, which are most relevant in this field [8], [11], and [27]. To have an idea of the contributions of the local unit to this field, we refer in particular to [1] and [2].
5) Finally we propose to extend and perfect, in its various operational stages, the software developed so far to solve semi-infinite Toeplitz systems and their perturbations. To do so, it will be particularly essential to have efficient algorithms to solve systems with finite but large scalar and block Toeplitz matrices and their perturbations.