MINISTERO DELL'ISTRUZIONE, DELL'UNIVERSITÀ E DELLA RICERCA
DIPARTIMENTO PER L'UNIVERSITÀ, L'ALTA FORMAZIONE ARTISTICA, MUSICALE E COREUTICA E PER LA RICERCA SCIENTIFICA E TECNOLOGICA
PROGRAMMI DI RICERCA SCIENTIFICA DI RILEVANTE INTERESSE NAZIONALE
RICHIESTA DI COFINANZIAMENTO (DM n. 30 del 12 febbraio 2004)

PROGETTO DI UNA UNITÀ DI RICERCA - MODELLO B
Anno 2004 - prot. 2004015437_003
PARTE I

1.1 Tipologia del programma di ricerca
Interuniversitario 


Aree scientifico disciplinari
Area 01: Scienze matematiche e informatiche (100%) 
 
 


1.2 Durata del Programma di Ricerca

 

24 Mesi  


1.3 Coordinatore Scientifico del Programma di Ricerca

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" 


1.4 Responsabile Scientifico dell'Unità di Ricerca

SEATZU  SEBASTIANO 
Professore Ordinario  10/04/1941  STZSST41D10F667J 
MAT/08 - Analisi numerica 
Università degli Studi di CAGLIARI 
Facoltà di INGEGNERIA  
Dipartimento di MATEMATICA  
070/6755619
(Prefisso e telefono)
 
070/6755601
(Numero fax)
 
seatzu@unica.it
(Email)
 


1.5 Curriculum scientifico del Responsabile Scientifico dell'Unità di Ricerca
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, for 12 years, as chairman of the Electrical Engineering Degree Council from 1980-1994. He participated in the organization of various national and international conferences (such as the XIV International Workshop on Operator Theory and Applications, held in Cagliari in the period of June 24-27, 2003). After his graduation in physics in 1965, he got interested in numerical analysis, in particular in approximation theory, the numerical solution of integral equations of the first kind, and numerical linear algebra. He has published 65 papers. He has also occupied himself with applied mathematics in various fields of physics and chemistry. His recent work includes approximation theory, sampling theory, spectral factorization of infinite Toeplitz matrices, and the numerical solution of block structured and multi-index linear systems. He is a coeditor of Calcolo, a quarterly on numerical analysis supported by the Italian National Research Council, and an associate editor of Advances in Computational Mathematics.


1.6 Pubblicazioni scientifiche più significative del Responsabile Scientifico dell'Unità di Ricerca

 

1. VAN DER MEE C.V.M.; RODRIGUEZ G.; SEATZU S. (2003). Semi-infinite multi-index perturbed block Toeplitz systems LINEAR ALGEBRA AND ITS APPLICATIONS. (vol. 366(C) pp. 459-482)  
2. BREZINSKI C.; REDIVOZAGLIA M.; RODRIGUEZ G.; SEATZU S. (2003). Multiparameter regularization techniques for ill-conditioned linear systems NUMERISCHE MATHEMATIK. (vol. 94 pp. 203-228)  
3. VAN DER MEE C.V.M.; NASHED M.Z.; SEATZU S. (2003). Sampling expansions in unitarily translation invariant reproducing kernel Hilbert spaces. ADVANCES IN COMPUTATIONAL MATHEMATICS. (vol. 19(4) pp. 355-372)  
4. VAN DER MEE C.V.M.; RODRIGUEZ G.; SEATZU S. (2002). 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..  
5. 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)  


1.7 Risorse umane impegnabili nel Programma dell'Unità di Ricerca




1.7.1 Personale universitario dell'Università sede dell'Unità di Ricerca

Personale docente

Cognome  Nome  Dipartimento   Qualifica  Settore Disc.  Mesi Uomo 
1° anno  2° anno 
1. SEATZU  Sebastiano  Dip. MATEMATICA  Prof. Ordinario  MAT/08  6  6 
2. VAN DER MEE  Cornelis Victor Maria  Dip. MATEMATICA  Prof. Ordinario  MAT/07  6  6 
3. RODRIGUEZ  Giuseppe  Dip. MATEMATICA  Prof. Associato  MAT/08  6  6 
  TOTALE              18  18 


Altro personale


Nessuno

1.7.2 Personale universitario di altre Università

Personale docente

Cognome  Nome  Università  Dipartimento  Qualifica  Settore Disc.  Mesi Uomo 
1° anno  2° anno 
1. REDIVO ZAGLIA  Michela  PADOVA  Dip. MATEMATICA PURA ED APPLICATA  PA  MAT/08  6  6 
  TOTALE                


Altro personale


Nessuno

1.7.3 Titolari di assegni di ricerca


Nessuno

1.7.4 Titolari di borse


Nessuno

1.7.5 Personale a contratto da destinare a questo specifico programma


Nessuno

1.7.6 Personale extrauniversitario indipendente o dipendente da altri Enti

Cognome  Nome  Nome dell'ente  Qualifica  Mesi Uomo 
1° anno  2° anno 
1. Theis  Daniela  Indipendente  Dottore di ricerca  3  3 
  TOTALE          





PARTE II

2.1 Titolo specifico del programma svolto dall'Unità di Ricerca
Multiindex structured matrices with applications


2.2 Settori scientifico-disciplinari interessati dal Programma di Ricerca

 

MAT/08 - Analisi numerica 
MAT/07 - Fisica matematica 
MAT/05 - Analisi matematica 


2.3 Parole chiave

REGULARIZATION METHODS ; EXTRAPOLATION METHODS ; STRUCTURED MATRICES ; SPECTRAL FACTORIZATION ; INTEGRAL EQUATIONS WITH STRUCTURED KERNEL ; INVERSE SCATTERING


2.4 Base di partenza scientifica nazionale o internazionale
On any of the subjects indicated below there exists extensive literature represented by numerous publications in international journals, specialized book series and proceedings of international conferences. The major part of the relevant papers regards, apart from numerical analysis, also functional analysis and linear operator theory. Moreover, there exist problems in various applied fields whose solution depends on the research on the subjects indicated in the project. A large amount of research on inverse scattering in, in particular, acoustics, optics and electromagnetism strictly depends on the solution of integral equations with structured kernel and their discrete analogs. The results on the functional analysis and operator theory most relevant to the project are to be found in the book series Operator Theory and Applications and in particular in [12,17,18,19,37]. The most interesting applied results, including the most efficient methods for solving many inverse scattering problems, are to be found in [9,14,27]. Significant contributions of the local research unit can be found in [1] and [29]. Various applied problems stemming from astronomy such as, in particular, the study of light transfer in planetary atmospheres lead to the treatment of various types of matrices with nonconventional structure. Some of these have been studied in [25]. Very interesting results on linear operator theory, numerical methods for solving linear systems with structured matrices, integral equations with structured kernel and their applications have been presented at the Fourteenth IWOTA conference (International Workshop on Operator Theory and its Applications) held in Cagliari in the period of June 24-27, 2003, whose proceedings will be published in the Birkhauser OT series under the editorship of Kaashoek, van der Mee and Seatzu. On the solution techniques for ill-conditioned linear systems there exists documented scientific activity by the local research unit [5,6,38]. As to research on the generalization of projection methods to the solution of multi-index systems, the monographs [2,3,17] are of the utmost interest. In this respect the most significant contributions of the local unit are contained in the papers [22,30,33,34]. Many results of specific interest to integral equations are contained in [17,18,19].
In the multi-index case there is not a lot of literature because of the comparative nonexistence of an algebraic theory of multi-index matrix operators, in spite of the objective interest in the subject in many applied fields. In the latter situation, but exclusively in the scalar case, two spectral factorization methods in weighted Banach algebras with respect to a fixed total order have been developed [15,22]. The results obtained allow one to characterize the type of decay of both the elements of the inverse of the matrix and of the factors, in terms of the characteristics of the matrix. One of the two methods, which is easily implemented by using the FFT, has been used to identify the limiting profile in the asymptotic process of orthonormalization of sequences of uniform translates of a fixed multivariate function by means of the Gram-Schmidt method [22]. In the multi-index block Toeplitz case there only exist partial results on spectral factorization [33,34]. In particular, nobody has so far succeeded in characterizing the type of decay of the elements of the Cholesky factors of a positive definite multi-index block Toeplitz matrix in terms of that of the elements of the matrix under consideration. An interesting extension of the band extension method that seems promising for solving multi-index systems has recently been obtained in [16].
The research planned on the study of integral equations is based in part on results involving their discrete analogs [36]. Because many applied problems typical of remote sensing, inverse scattering and image processing can be reduced to the solution of integral equations of convolution type in several variables, it appears essential to discretize to obtain a pure or perturbed Toeplitz system and to solve the corresponding linear system with regularization methods that exploit the structure.
The regularization theory applied to structured matrices [23] as well as the computational methods based on fast algorithms that exploit the displacement structure [13,20,24,26] form a solid basis for studying this problem. These comprise preconditioned iterative methods, among which those formulated in Krylov spaces, and in particular the GMRES, Lanczos and conjugate gradient methods for which there exists a lot of consolidated literature, evoke particular interest. Locally there exists substantial expertise in both iterative methods [4,6,7,8] and structured matrices [30-34]. For this reason we expect to be able to develop iterative algorithms specialized to the case of structured matrices. On the basis of partial results that are as yet unpublished, the local unit expects to be able to develop an algorithm for generating preconditioners of structured multi-index matrices.
For the numerical validation of the existing methods in the field, it is crucial to have at one's disposal an extensive class of test matrices. The principal reference for generating such test matrices is the article [35] in which an operational method for generating families of multi-index test matrices is indicated.
For this reason it will be essential to collaborate with the other units to choose the optimal algorithms for solving perturbed structured linear systems of large order, as required when using the projection method. In the other two research units there exists a very substantial theoretical and numerical expertise that is by now established and internationally recognized. As to the development of software, we can base ourselves on many algorithms and programs for treating structured matrices and solving ill-conditioned linear systems which have already been developed and used by the local unit. In this field there exists specialistic know-how guaranteeing the realizability of software of public domain, as indicated in part 5) of the research project.


2.4.a Riferimenti bibliografici

[1] 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).
[2] A. Boettcher and B. Silbermann. Analysis of Toeplitz operators. Springer, New York, 1990.
[3] A. Boettcher and B. Silbermann. Introduction to large truncated Toeplitz matrices. Springer, New York, 1999.
[4] C. Brezinski, M. Redivo Zaglia. Block projection methods for linear systems, Numerical Algorithms, 29 (2002) 33?43.
[5] C. Brezinski, M. Redivo-Zaglia, G. Rodriguez, and S. Seatzu. Multiparameter regularization techniques for ill-conditioned linear systems, Numer. Math. 94, 203-228 (2003).
[6] C. Brezinski, M. Redivo Zaglia, H. Sadok. New look-ahead Lanczos-type algorithms for solving linear systems, Numer. Math., 83 (1999) 53-85.
[7] C. Brezinski, M. Redivo Zaglia, H. Sadok. The matrix and polynomial approaches to Lanczos-type algorithms, J. Comput. Appl. Math., 123 (2000) 241-260.
[8] C. Brezinski, M. Redivo Zaglia, H. Sadok. A review of formal orthogonality in Lanczos-based methods, J. Comput. Appl. Math., 140 (2002) 81-98.
[9] K. Chadan and P. C. Sabatier. Inverse Problems in Quantum Scattering Theory, 2nd ed., Springer, New York, 1989.
[10] R. Chan and G. Strang. Toeplitz equations by conjugate gradients with circulant preconditioner. SIAM J. Sci. Stat. Comput. 10(1):104-119, 1989.
[11] T.F. Chan. An optimal preconditioner for Toeplitz systems. SIAM J. Sci. Stat. Comput., 9(4):766-771, 1988.
[12] 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.
[13] T. Constantinescu, A.H. Sayed, and T. Kailath. Displacement structure and H-infinity problems. System theory: Modeling, analysis and control. Kluwer, Boston, 2000.
[14] 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.
[15] T. Ehrhardt and C. van der Mee. Canonical factorization of continuous functions on the d-torus. Proc. Amer. Math. Soc.,131, 801-813 (2002).
[16] J.S. Geronimo and H. Woerdeman. Positive extensions and Fejer-Riesz factorization in Autoregressive Filters in two variable, Ann. Math. to appear.
[17] 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.
[18] 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.
[19] 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.
[20] 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).
[21] 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.
[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] P.C. Hansen. Rank-deficient and discrete ill-posed problems. Numerical aspects of linear inversion. SIAM, Philadelphia, 1997.
[24] 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.
[25] J.W. Hovenier, C. van der Mee, H. Domke. Transfer of polarized light in planetary atmospheres. Basic concepts and practical methods. Kluwer, Dordrecht, 2004 (to appear).
[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] C.V.M. van der Mee, M.Z. Nashed, and S. Seatzu, Sampling expansions and interpolation in unitarily translation invariant reproducing kernel Hilbert spaces, Adv. Comp. Math.,19(4), 455-472, 2003.
[29] C.V.M. van der Mee, V. Pivovarchik. Inverse scattering for Schrödinger equation with energy dependent potential. J. Math. Phys. 42 (2001) 1-24.
[30] 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.
[31] 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.
[32] 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.
[33] 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).
[34] C.V.M. van der Mee, G. Rodriguez, and S. Seatzu. Semi-infinite multi-index perturbed block Toeplitz systems. Linear Algebra and its Applications, 366 (2003) 459-482.
[35] C.V.M. van der Mee, S. Seatzu. A method for generating infinite positive definite self-adjoint test matrices and Riesz bases. Preprint (2004).
[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. Numerical Algorithms, 33 (2003) 433-422.
[39] E.E. Tyrtyshnikov. Optimal and superoptimal circulant preconditioners, SIAM J. Matrix Anal. Appl., 13 (1992) 459-473.


2.5 Descrizione del programma e dei compiti dell'Unità di Ricerca
As agreed upon with the other units, the Cagliari unit will conduct research on the following arguments:
1) development of innovative methods to solve linear systems with ill-conditioned matrices and linear systems with multi-index matrices;
2) development of preconditioners to solve linear systems with multi-index matrices;
3) generation of families of multi-index test matrices, identifying the asymptotic behaviour of their condition numbers;
4) numerical solution of integral equations with multivariate structured kernels and their application to acoustics and remote sensing;
5) development of prototypical software specialized to structured matrices.

1) As to the first research argument, the Cagliari unit proposes to develop computational methods for ill-conditioned structured linear systems by applying fast algorithms based on displacement structure to Tikhonov regularization methods. In the very frequent cases in which the regularization matrix itself is structured, these methods should allow us to deal with linear systems characterized by various types of displacement structure, such as for instance Toeplitz, Hankel and Cauchy structures, which are of particular interest in the numerical solution of integral equations with structured kernels. We also propose to study the solution of ill-conditioned linear systems by means of preconditioned iterative methods applied in Krylov spaces, such as for instance GMRES, the conjugate gradient method and the Lanczos method. More precisely, we are thinking of using the preconditioning methods mentioned in 2) as preconditioners in various iterative methods and in particular in the GMRES method.
A second part of the research will regard the extension of projection methods in weighted Wiener algebras to the solution of linear systems with structured multi-index matrices. This method, which is well-known when solving linear Toeplitz systems in the Wiener algebra, is easily extended to weighted Wiener algebras, provided one deals with mono-index block Toeplitz systems or with positive definite multi-index block Toeplitz systems with scalar blocks [17],[2]. To the contrary, the extension to the multi-index case is not easy for non positive definite Toeplitz systems or for positive definite block Toeplitz systems. Such an extension would be very useful because it would allow us to characterize the asymptotic behaviour of the error as a function of the decay of the elements of the matrix away from the diagonal and of the decay of the elements of the vector on the right-hand side.
The local unit also proposes to study the solution of linear systems whose matrices have a nonconventional structure stemming from problems in astronomy such as the transfer of polarized light in planetary media where there exists considerable local expertise [25].

2) As is well-known [10,11,39], there exist various methods of optimal computational complexity to solve mono-index linear systems. On the other hand, there exist only partial results on the generation of preconditioners of low computational complexity in the case of multi-index matrices [39]. Research in progress by the Cagliari unit appears able to generate in a uniform way preconditioners for mono- and multi-index matrices. The research is presently evolving towards the optimization of the computational complexity independently of the number of indices. Here we propose to experimentally determine the efficiency of the solution method for an extensive class of linear systems by means of preconditioned iterative methods. The development of a vast class of test matrices, as to be discussed in 3), should allow us to validate the method in an appropriate way. We also plan research on the recursive generation of preconditioners that are to be applied iteratively to e.g. the GMRES method. More explicitly, the basic idea is the following: once the preconditioner has been constructed for the matrix at step k, the preconditioner at the next step is obtained from its predecessor by simply evaluating two additional elements.

3) In [28] a general method has been developed that can be applied in a simple way to generate bi-infinite positive definite matrices. In [35] this method has been improved considerably and generalized to the multi-index case, but only to bi-infinite matrices. Here we propose to adapt the method to generate semi-infinite matrices, aiming at identifying the asymptotic behaviour of the condition numbers of an extensive class of multi-index matrices as a function of their order. Such a result should allow us to have at our disposal a sufficiently large class of matrices for which the asymptotic behaviour of their condition numbers is known. The purpose is to be able to compare the efficiency of the newly proposed methods to those in present use. The Cagliari unit is particularly interested in the evaluation of the efficiency of the preconditioners proposed in connection with the conjugate gradient method and the GMRES method.

4) Because linear systems with structured multi-index matrices represent the discrete analogue of integral equations in several variables with structured kernel, there exists a natural and deep connection between the two research topics that is potentially very profitable but has presently not been valued in an adequate way. This depends fundamentally on the fact that operator theory has so far been developed by functional analysts and structured matrix theory by numerical analysts. Because either type of expertise is present in the local unit, we could in fact develop innovative methods for the numerical solution of multivariate integral equations with structured kernel. From the theoretical point of view the computational method for infinite multi-index systems proposed in [34] should be very useful. An important applied field where there exist significant contributions of the local unit [1],[29], is represented by inverse scattering in acoustics and quantum mechanics. In collaboration with scientists at the Universities of Cagliari and Napels that are experts on remote sensing, the local unit proposes to apply the theoretical and numerical results on integral equations and linear multi-index systems to solve typical problems in this field.

5) In spite of a great interest, both from the scientific and the applied side, in the arguments connected with structured matrices and their treatment, there does not seem to exist a specialized software library which implements the most recent algorithms that have specifically been developed for this class of matrices. Because there exist various algorithms and programs of applied interest developed by the local unit as well as a real expertise in writing and evaluating specialized software (*), we propose to develop a toolbox specialized to structured matrices in MatLab, which is one of the most widely disseminated software instruments for scientific computation and visualization. The characteristics to which we will give particular attention are the following: user friendliness, integration with the Matlab environment and its intrinsic numerical routines, and optimization of computing time and memory requirements. As a first goal we intend to pay attention to certain types of structured matrices and basic algorithms for solving linear systems, both by using preconditioned iterative methods and by using direct methods based on displacement structure. The final goal is to construct software that is flexible and can easily be extended to new computational algorithms, also in the multi-index case.
(*) G. Rodriguez has developed the codes for the numerical algorithms proposed in [35-38] and M. Redivo Zaglia is software editor of the journal Numerical Algorithms.


2.8 Mesi uomo complessivi dedicati al programma


Numero Mesi uomo
1° anno
Mesi uomo
2° anno
Totale mesi uomo
University Personnel  3  18  18  36 
Other University Personnel  1  6  6  12 
Work contract (research grants, free lance contracts)  0       
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)  0       
PHD Fellows & PHD Students  0       
PHD Students  0       
Other tipologies  0       
No cost Non University Personnel  1  3  3  6 
TOTALE     27  27  54 


.