MODELLO

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)

PROGRAMMA DI RICERCA - MODELLO A
Anno 2004 - prot. 2004015437

Parte: I

1.1 Programma di Ricerca di tipo: interuniversitario

Area Scientifico Disciplinare: Scienze Matematiche e informatiche

1.2 Titolo del Programma di Ricerca

Structured matrix analysis: numerical methods and applications

1.3 Abstract del Programma di Ricerca

Large part of problems in scientific computing is reduced to solving numerical linear algebra problems. The large scale and the complexity of the mathematical models turn into large amount of data and high complexity of the computations. General solution methods are not practically applicable for their large cost, and it is demanding to design and analyze specific algorithms strongly based on the peculiarity of the model.
These peculiarities, once restated in terms of the linear algebra language, can be read as structure and sparsity patterns of the matrices involved in the model.
Many patterns are recurrent in diverse scientific contexts and applications. For instance, band matrices are encountered in contexts like the numerical treatment of boundary value problems, in difference equations, in spline interpolation; shift invariant properties encountered in signal and image processing, statistic analysis, Markov chains, lead to Toeplitz matrices.
Multi-dimensional problems lead to multilevel structures and block matrices.
Often the properties of the original model turn into structures which are not so evident, like displacement structure, local structures and semi-separable or quasi-separable matrices, which look like "general" matrices.
The analysis of structures and the design of specific algorithms for solving problems in numerical linear algebra has received a great attention and has lead to important advances in the last years. On one hand, important theoretical advances have been reached in the study of theoretical properties of frequently encountered structured matrices, on the other hand the design of specific algorithms has allowed the effective solution of important problems in different applicative fields. For instance, algorithms for solving matrix equations and queueing models, based on Toeplitz computations, have lead to strong reductions of the cpu time in solving network problems in engineering.

THE PROJECT:
This project is the continuation of a previous MIUR project 2002-2003, its goal is to enlarge the range of structured tools and applications under investigation by expanding and integrating the results obtained in 2002-2003 (see http://bezout.dm.unipi.it). The aim of the project consists of

A- Analysis of algebraic, analytic and computational properties of classes of structured matrices encountered in theoretical and in applied problems, including linear and nonlinear structures. In particular, displacement structures (Toeplitz, Hankel, Cauchy, Bezout, etc), semi-separable matrices, multi-level (multi-index) matrices, locally structured matrices, parametric systems.
B- Design of fast and numerically reliable (stable and robust) algorithms for solving computational problems involving structured matrices, like total least squares, linear systems, eigenvalue computations. Adaptation of known techniques like multigrid, PCG, GMRES, QR iteration, to specific structures. Use of structured tools for locally structured or even unstructured (minimization) problems.
C- Application of the results to the solution of computational problems from scientific computing, including: image processing, nonlinear inverse problems, queueing models, matrix equations, integral and differential equations, inverse scattering problems, approximating polynomial zeros, computer aided geometric design, human metabolism models, information retrieval, neural networks.
D- Implementation of the algorithms in a prototype code, numerical comparisons and validation.

STATE OF THE ART:
There are several international research groups which are very active in the field. The Italian group is actively working in the area since many years. There is a strong theoretical and algorithmic basis made up by many tools and powerful techniques developed in the years by many researchers. There are different research lines where the interest is growing up at the international level. Some new lines stemmed from the previous MIUR project.

1.4 Durata del Programma di Ricerca: 24 Mesi

1.5 Settori scientifico-disciplinari interessati dal Programma di Ricerca

· MAT/08 - Analisi Numerica

· MAT/07 - Fisica Matematica

· INF/01 – Informatica

· MAT/02 – Algebra

· MAT/05 - Analisi Matematica

1.6 Parole chiave

STRUCTURED MATRICES ; TOEPLITZ MATRICES ; PRECONDITIONING FOR STRUCTURED MATRICES ; WIENER-HOPF FACTORIZATION ; SEMISEPARABLE MATRICES ; IMAGE RESTORATION ; POLYNOMIAL COMPUTATIONS ; NUMERICAL METHODS FOR MARKOV CHAINS ; MATRIX EQUATIONS

1.7 Coordinatore Scientifico del Programma di Ricerca

DARIO ANDREA BINI, Professore ordinario,

Dipartimento di Matematica "Leonida Tonelli", Università di PISA,

Facoltà di Sienze Matematiche Fisiche e Naturali bini@dm.unipi.it

1.8 Curriculum scientifico

Dario Bini is full professor of numerical analysis since 1986. He is author of more than 70 papers, published in international journals and in proceedings of international conferences, and of several books in numerical analysis and computational mathematics. He is member of the editorial board of the international journal "Calcolo", associate editor of SIAM J. Matrix Anal. Appl., and has a wide and long expertise in the research fields of structured matrix computations, design and analysis of numerical algorithms and polynomial computations. He has organized international conferences on these research topics. He has been advisor of several PhD thesis. His main research interests include, Toeplitz matrix computations, displacement operators, polynomial computations, numerical solution of Markov chains, solution of matrix equations.

1.9 Pubblicazioni scientifiche più significative del Coordinatore del Programma di Ricerca

1. BINI D.A.; BOETTCHER A (2003). Polynomial factorization through Toeplitz matrix computations LINEAR ALGEBRA AND ITS APPLICATIONS. (vol. 366 pp. 25-37)

2. BINI D.A.; L. GEMIGNANI; B. MEINI (2003). Solving certain matrix equations by means of Toeplitz computations: algorithms and applications CONTEMPORARY MATHEMATICS. (vol. 323 pp. 151-167)

3. BINI D.A.; G. LATOUCHE; B. MEINI (2002). Solving matrix polynomial equations arising in queueing problems LINEAR ALGEBRA AND ITS APPLICATIONS. (vol. 340 pp. 225-244)

4. BINI D.A.; L. GEMIGNANI; B. MEINI (2001). Computations with infinite Toeplitz matrices and polynomials LINEAR ALGEBRA AND ITS APPLICATIONS. (vol. 343-344 pp. 21-61)

5. BINI D.A.; MEINI B. (1999). Effective methods for solving banded Toeplitz systems SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. (vol. 20 pp. 700-719)

1.10 Elenco delle Unità di Ricerca

Nº	Responsabile scientifico	Qualifica	Settore disc.	Università	Dipart./Istituto	Mesi uomo
1.	BINI DARIO ANDREA	Prof. ordinario	MAT/08	PISA	MATEMATICA "Leonida Tonelli"	16
2.	DI BENEDETTO FABIO	Prof. associato	MAT/08	GENOVA	MATEMATICA	14
3.	SEATZU SEBASTIANO	Prof. ordinario	MAT/08	CAGLIARI	MATEMATICA	12

1.11 Mesi uomo complessivi dedicati al programma

		Numero	Mesi uomo 1° anno	Mesi uomo 2° anno	Totale mesi uomo
Personale universitario dell'Università sede dell'Unità di Ricerca		14	83	73	156
Personale universitario di altre Università		10	69	67	136
Titolari di assegni di ricerca		1	9	7	16
Titolari di borse	Dottorato	1	8	8	16
	Post-dottorato	0
	Scuola di Specializzazione	0
Personale a contratto	Assegnisti	1	9	7	16
	Borsisti	0
	Dottorandi	0
	Altre tipologie	1	4	6	10
Personale extrauniversitario		2	8	8	16
TOTALE		30	190	176	366

Parte: II

2.1 Obiettivo del Programma di Ricerca

The project is based on the following guidelines and underlying ideas:

· Structured matrices play a fundamental role in a great part of mathematical models in theory and applications.

· The analysis of structured matrices, besides its theoretical interest, is a fundamental step for the design of specific solution algorithms, where general algorithms fail for their large cost.

· The structured matrix technology, developed along the years, can be used to effectively solve large scale problems of great importance in the applications, which could be hardly solved with general algorithms.

· The structured matrix technology may provide tools for solving apparently unstructured problems.

· The design and the analysis of algorithms taylored on the specific structures is not enough in itself. Great attention must be payed to robustness and numerical stability of algorithms.

Therefore, at the basis of this project there is the analysis of theoretical and computational properties of matrix structures in order to improve the know-how in structured matrix technology. The aim is designing highly efficient and reliable algorithms for solving computational problems from different areas in theoretical and in scientific computing.

For the sake of clarity, the program is ideally subdivided in the following (possibly overlapping) parts:

-A- To perform the analysis of theoretical and computational properties of structured matrices.
-B- To devise structured matrix tools for designing efficient solution algorithms for the most important computational problems.
-C- To apply the new algorithms to problems coming from applications.
-D- To implement, in terms of prototype software, the algorithms designed in this research and to perform experimental validation and comparison.

The topics which will be considered are problems in Structured Numerical Linear Algebra (SNLA) which are the natural continuation of the issues of major interest investigated in the previous MIUR project 2002-2003 titled "Structured matrix analysis: numerical methods and applications", or problems, which although not in the program 2002-2003, have shown to be particularly interesting in themselves and for their applications. In fact, in the new project more interest is addressed to applications. Applicative topics are a source of very interesting theoretical problems and of structured matrix classes, and, at the same time they constitute an important benchmark where to test the effectiveness of the algorithms designed with SNLA tools.

The class of matrices which we consider in this research are Toeplitz and displacement structured matrices (including Hankel, Cauchy, Pick, Vandermonde, Sylvester, Bezout, Frobenius, generalized companion matrices), locally Toeplitz, banded, semi-separable and quasi-separable matrices, multi-index (multi-level) matrices, sequences of shifted matrices and their parametric generalizations, trigonometric algebras.

The computational problems include solving linear systems, computing eigenvalues/eigenvectors, solving matrix equations, solving total least squares problems, minimization problems, computing matrix factorizations and Wiener-Hopf factorization, polynomial computations.

Computational issues encountered in this study which will be investigated are the analysis of preconditioners, algebraic multigrid techniques, matrix factorizations, analysis of Krylov sequences, QR iteration, regularization problems, projection methods, numerical conditioning and numerical stability issues, integration of symbolic and numeric tools, interplay between polynomial and structured matrix computations.

The main application areas involve problems in image processing as LBT imaging and image restoration, queueing problems modeled by Markov chains of the G/M/1, M/G/1 and QBD type, acoustics and inverse scattering problems, computer aided geometric design, differential models of human metabolism, search engines in the web, neural networks and optimal learning, integral equations.

More precisely, the classes of structured matrices and the related problems which are studied in parts A,B,C,D are outlined below. For a more detailed description we refer to section 2.4 and to the "Modello B" of each research unit.

A1- Toeplitz and locally Toeplitz matrices
A2- Semi-separable and quasi-separable matrices
A3- Parametric matrices
A4- New matrix algebras related to trigonometric transforms
A5- Generalized companion and resultant matrices
A6- Block Toeplitz matrices
A7- Multi-level (multi-index) matrices
A8- Infinite Toeplitz matrices
A9- Nonconventional structures

The computational problems in part B will be:

B1- Linear systems and total least squares problems
B2- Eigenvalue problems
B3- Functional approximation
B4- Inverse problems and regularization
B5- PDEs
B6- Multigrid
B7- Preconditioning
B8- Polynomial computations
B9- Matrix equations
B10- Wiener-Hopf factorization
B11- Minimization problems
B12- Integral equations with structured kernels
B13 GMRES and Krylov methods
B14 Projection methods in weighted Wiener algebras

The Applications in part C will be:

C1- Web search engines
C2- Human metabolism models
C3- Image restoration
C4- Inverse scattering, nonlinear inverse problems, acoustics and remote sensing
C5- Identification problems
C6- Markov chains and queuing models
C7- Computer Aided Geometric Design
C8- Neural networks
C9- Astronomy problems

Concerning part D

D1- Test matrices
D2- MatLab Toolbox
D3- Prototype software

Finally, one aim of the project is the organization of the fifth edition of the International Workshop

Matrix Analytic Method in Stochastic Models MAM5, Pisa, June 2005 (http://www.dm.unipi.it/~mam5).

The conference, which covers topics in applied probability, engineering and numerical analysis, is an international forum where the state of the art in the field of numerical methods in applied probability will be traced and discussed.

2.2 Base di partenza scientifica nazionale o internazionale

Many important problems in pure and applied mathematics involve classes of structured matrices which are frequently encountered in different contexts. Matrix structures are the algebraic translation of the specific properties of the problem. General properties as the shift invariance, the compact support, the separability of variables, which are shared by many problems in different areas turn into matrix structures that are almost pervasive like Toeplitz matrices, band matrices, semi-separable and quasi-separable matrices. They are encountered in many different problems in numerical analysis, statistics, probability, computer algebra, signal and image processing, acoustics, astronomy, just to quote a few. Other related structures like Hankel, Vandermonde, Cauchy, Pick, Bezout Sylvester matrices are not less relevant.

The analysis of matrix structure is extremely important in order to devise tools for designing fast and reliable solution algorithms for many important problems which, for their large size, hardly could be solved by means of general algorithms.

The interest on structured matrices, already alive in the 60's [GS] and in the 70's [Tr], [GoS] with the direct methods for Toeplitz systems and implicitly with the fast Poisson solvers [BGN], has increased much its importance in the years due to the work of several very active international research groups. A wide literature has been consolidated on different related mathematical problems and many international conferences specially devoted to structured matrix analysis and its applications have been organized.

The theoretical and algorithmic basis on which this project relies is very wide and rich of results and of tools.

Historically, the main advances in the field of structured matrix analysis are reported in several books, some of which are milestones in this field. Here for space reason we may cite only a few of them: the books of Iohvidov [I] and of Heinig and Rost [HR] on Toeplitz and Hankel structures, the book of Bultheel and Van Barel [BvB] on the relations between structures and orthogonal polynomials, the book of Bini and Pan [BP] on the relations between structures and polynomial computations, the books of Grenander and Szego [GS] and of Boettcher and Silbermann [BS] on asymptotic spectral properties of Toeplitz matrices, the books of Gohberg, Goldberg and Kaashoek [GGK] and of Gohberg Lancaster and Rodman [GLR] and the book series Operator Theory and Applications by Birkhauser, on more theoretical issues, The book [DV] of Dewilde and van der Veen related to semi-separable matrices, the books edited by Kailath and Sayed [KS], by Bini, Tyrtyshnikov and Yalamov [BTY], and by V. Olshevsky [O] which contain recent advances in the field, and the review paper by Chan and Ng [CN] on Toeplitz preconditioning.

The theory of displacement operators by Kailath et al [KS] and the large literature originated around it constitute an important and solid basis. We recall the distributional results pioneered by Szego (see [BS]) and culminated in the work of Tyrtyshnikov [TZ] concerning the "global behaviour" of the spectra of Toeplitz sequences. Extensions to matrix valued generating functions and to sequences arising in the preconditioning theory as well as some applications to approximation and quadrature, can be found in literature. A second important extension concerns the case of locally Toeplitz matrices, i.e., structures which are of Toeplitz type "only locally" or that possess different "local structures" [Ti] and including, as special instance, discretizations of differential operators with boundary conditions.
Asymptotic spectral properties play an important role in the design of preconditioners for conjugate gradient. The circulant class associated with the discrete Fourier transform which Strang [St] proposed first in 1986, has been complemented with other trigonometric matrix algebras. A systematic treatment of this topic has been performed by many researchers like T.Chan, R.Chan, S.Serra, F. DiBenedetto, G.Fiorentino, E.Tyrtyshnikov, T.Huckle, Potts, Steidl, Nagy, Plemmons, in the one-level and multi-level case. Other trigonometric algebras and related classes have been studied by Kailath, Olshevsky, and by the Italian group.

The GMRES, Lanczos and conjugate gradient methods are important tools in this project. To this regard there exists a lot of consolidated literature in many paper and classic books.

For multi-index Toeplitz matrices 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. Contributions in this direction are given by the group of van der Mee, Rodriguez, Seatzu, Ehrardt. Exclusively in the scalar case, two spectral factorization methods in weighted Banach algebras with respect to a fixed total order have been developed. In the multi-index block Toeplitz case there only exist partial results on spectral factorization.
An interesting extension of the band extension method that seems promising for solving multi-index systems has recently been obtained in [GW].

Matrix structures play an important role in many polynomial computations where several problems related to polynomial and rational approximation can be described in terms of structured matrices, including Cauchy, Pick, Vandermonde, locally Toeplitz and semiseparable. We cite the book [BP] and the wide existing literature with the contributions of Bini, Boettcher, Gemignani, Meini, Fiorentino. Concerning the computation of Wiener-Hopf factorization, Laurent polynomials and bi-infinite Toeplitz matrix inversion, we refer to [BGM1, GMRS, MRS]. The interplay between numerical and symbolic computations is important in this context. To this regard the European project FRISCO (FRamework for the Integration of Symbolic and numeric Computing) constitutes a solid basis for our research, a nice integration of numeric and symbolic tools is made in [CGTW].

Semi-separable and quasi-separable matrices have a particular role in our project. There is a wide and solid literature on this subject, besides the classical results on semiseparable structures of Gohberg, Eidelman, Dewilde, Chandrasekaran, Ming Gu, recently some interesting results have been obtained by the group of Van Barel and by the Italian group. In particular in [VBM1] interesting similarity transformations into semiseparable form are shown, in [BGT] the properties of semiseparable matrices are used for the design of effective tridiagonal eigenvalue solvers.

Another structure arising in several frameworks (image processing, time-dependent PDEs, iterative eigensolvers, etc.), concerns shifted linear systems as (A+eI)x=b. Sometimes I is replaced by a more general diagonal shift [BeBe].

Finally, application of structured matrix analysis to unstructured minimization problems and total least squares has recently shown to be very effective see [DFLZ,LMV1] where some applications to automatic learning and speech compression are shown.

Concerning other applications:
Numerical methods for Markov chains is a field where recently the structured matrix technology has produced great advances. We refer to the books [Ne], [LR] for the description of the problems and to the papers by Bini, Meini and Latouche, for a sample of algorithms designed on Toeplitz tools. In particular the cyclic reduction algorithm designed in [BGN] has recently revealed a powerful tool also in the field of M/G/1 and G/M/1 Markov chains [BM3]. Another important problem strictly related to queueing models, encountered in many other applications where structured matrices play an important role, concerns the solution of nonlinear matrix equations for which there exists a wide literature [HK,BGM2].

A very recent imaging device that requires the solution of challenging reconstruction problems is the Large Binocular Telescope (LBT) [AHSS]. All the numerical methods used in image reconstruction must take into account that some regularization approach is needed. The reconstruction obtained by a basic method can be further improved with the help of two advanced tools: boundary conditions (see [J], [NCT] for classical proposals and [S3] for the new anti-reflective idea) and wavelets [CCSS].

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 [HMD]. A large amount of research on inverse scattering, 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 by Birkhauser.

Many new contributions have been recently given in the MIUR project 2002-2003 (see the web page http://bezout.dm.unipi.it) of which this proposal is a continuation, and of which we report below the list of the main papers with the most important achievements. These are in the fields of spectral and computational analysis of wide classes of structured matrices including Toeplitz, locally Toeplitz and semiseparable matrices, of the regularization of inverse problems arising in several applications, of applied areas including partial differential equations, image processing and functional approximation, in the field of polynomial computations and CAGD, of Markov chains and queuing problems, in matrix equations, in minimization problems, least squares and applications to neural networks and speech compression, on multi-index matrices and on spectral factorization, on ill conditioned systems.

Many of these results have been presented at numerous conferences organized in this area, among which the Fourteenth IWOTA Conference, on Operator Theory and Applications, Cagliari, June 2003, whose proceedings will be published in the Birkhauser OT series, edited by Kaashoek, van der Mee and S. Seatzu.

The members of this research project have a long tradition in structured matrix analysis with a strong basic expertise and a different specialization in diverse fields. The expertise of the members of the Units includes theoretical and computational issues, design and analysis of algorithms and software, and applications in different fields like image processing, differential and integral equations, queueing models and Markov chains, polynomial computations and computer algebra.

[ADS] A.Aricò, M.Donatelli, S.Serra, Multigrid optimal convergence for certain (multilevel) structured linear systems. SIMAX, in press.
[BBCR] M.Bertero, P.Boccacci, A.Custo, M.Robberto, A Fourier-based method for the restoration of chopped and nodded images, Astron. Astroph. 406,2003
[BCV] D.Bini,G.Codevico,M.Van Barel, Solving Toeplitz Least Squares Problems by Means of Newton's Iteration, Num.Algo.,33,2003
[BDFZ] A.Bortoletti C.Di Fiore S.Fanelli P.Zellini, A new class of quasi-newtonian methods for optimal learning in MLP-networks, IEEE Trans.Neur.Netw. 14,2003
[BDG] D.Bini F.Daddi L.Gemignani. On the shifted QR iteration applied to Frobenius matrices, Dip.Mat. Univ.Pisa 2003
[BeBe] M.Benzi,D.Bertaccini, Approximate inverse preconditioning for shifted linear systems. BIT 43,2003
[BG1] D.Bini L.Gemignani. Bernstein-Bezoutian matrices. Theor.Comp.Sci 2004.
[BG2] D.Bini L.Gemignani. Solving quadratic matrix equations and factoring polynomials: new fixed point iterations based on Schur complements of Toeplitz matrices. Numer.Lin.Alg.Appl. 2004.
[BGP] D.Bini L.Gemignani V.Pan. Inverse Power and Durand-Kerner Iterations for Univariate Polynomial Root-Finding, Comp.Math.Appl.
[BFGM] D.Bini, G.Fiorentino L.Gemignani B.Meini. Effective fast algorithms for polynomial spectral factorization. Num.Algo. 34,2003
[BGM2] D.Bini L.Gemignani B.Meini, Solving certain matrix equations by means of Toeplitz computations: algorithms and applications. Cont.Math.323, 2003
[BGW] D.Bini L.Gemignani J.Winkler, Structured matrix methods for CAGD, Dip.Mat. Univ. Pisa 2003
[BLM] D.A.Bini G.Latouche B.Meini, Solving nonlinear matrix equations arising in tree-like stochastic processes,Lin.Alg.Appl. 366, 2003
[BM] D.Bini, B.Meini. Non-skip-free M/G/1 type Markov chains and Laurent matrix power series, Fourth Int.Conf. Num. Sol. of Markov Chains, vol. 1, 2003
[BN] D.Bertaccini M.Ng, Band-Toeplitz Preconditioned GMRES Iterations for time-dependent PDEs. BIT 43,2003
[D] C.DiFiore, Structured matrices in unconstrained minimization methods, Cont. Math. 323,2003
[DiB] F.DiBenedetto, The m-th difference operator applied to L2 functions on a finite interval Lin.Alg.Appl. 366,2003
[DLZ] C.DiFiore F.Lepore P.Zellini, Hartley-type algebras in displacement and optimization strategies, Lin.Alg.Appl.366,2003
[ET] C.Estatico A.Tamasan, A Newton linearization approach for solving the atmospheric retrieval problem. Tech. Rep., UCLA, 2003
[FG1] D.Fasino L.Gemignani. Fast and stable solution of banded-plus-semiseparable linear systems. CALCOLO 39,2002
[FG3] D.Fasino L.Gemignani Direct and inverse eigenvalue problems for diagonal-plus-semiseparable matrices, Num.Algo.34,2003
[FMB] D.Fasino N.Mastronardi M.Van Barel, Fast and stable algorithms for reducing diagonal plus semiseparable matrices to tridiagonal and bidiagonal form. Cont.Math. 323,2003
[FMV] D.Fasino N.Mastronardi M.VanBarel Fast and Stable Algorithms for Reducing Diagonal plus Semiseparable Matrices to Tridiagonal and Bidiagonal Form, Cont.Math. 323,2003
[FS] D.Fasino, S.Serra, From Toeplitz matrix sequences to zero distribution of orthogonal polynomials, Cont.Math. 323,2003
[GL] L.Gemignani G.Lotti. Efficient and stable solution of M-matrix linear systems of (block) Hessenberg form. SIMAX 24,2003
[HMD] 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
[Ia] B.Iannazzo, A note on computing the matrix square root. CALCOLO, 2004.
[LMV1] P.Lemmerling,N.Mastronardi,S.VanHuffel, Efficient implementation of a structured total least squares based speech compression method, Lin.Alg.Appl. 366,2003
[M4] B.Meini, The matrix square root from a new functional perspective: theoretical results and computational issues , SIMAX to appear
[MNS] C.van der Mee M.Z.Nashed S.Seatzu, Sampling expansions and interpolation in unitarily translation invariant reproducing kernel Hilbert spaces, Adv.Comp.Math.,19,2003.
[MRS1] C.van der Mee G.Rodriguez S.Seatzu. Semi-infinite multi-index perturbed block Toeplitz systems. Lin.Alg.App. 366,2003
[MS] C.van der Mee S.Seatzu. A method for generating infinite positive definite self-adjoint test matrices and Riesz bases. Preprint 2004
[NSV] D.Noutsos, S.Serra, P.Vassalos, Spectral equivalence and matrix algebra preconditioners for multilevel Toeplitz systems: a negative result, Cont.Math., 323,2003
[S3] S.Serra, A note on anti-reflective boundary conditions and fast deblurring models. SIAM J.Sci.Comp. 25,2003
[S4] S.Serra, Generalized Locally Toeplitz sequences: spectral analysis and applications to discretized Partial Differential equations, Lin.Alg.Appl. 366,2003
[ST1] S.Serra, C.Tablino Possio, Analysis of preconditioning strategies for collocation linear systems. Lin.Alg.App.369,2003
[ST2] S.Serra, C.Tablino Possio, Superlinear preconditioners for Finite Differences linear systems. SIMAX 25,2003
[STy1] S.Serra E.Tyrtyshnikov, How to prove that a preconditioner can not be superlinear, Math.Comp.72 2003

2.2.a Riferimenti bibliografici

[AHSS]J.Angel,J.Hill,P.Strittmatter,P.Salinari,G.Weigelt, Interferometry with the Large Binocular Telescope. Proc. SPIE 3352(1998).
[BB]M.Bertero, P.Boccacci, Introduction to Inverse Problems in Imaging, IOP Publ., Bristol, 1998
[BD]E.Bozzo,C.Di Fiore, On the use of certain matrix algebras associated with discrete trigonometric transforms. SIMAX 16,1995
[BDi]D.Bini,F.DiBenedetto, A new preconditioner for the parallel solution of positive definite Toeplitz linear systems. Proc. 2nd SPAA conf. Crete, 1990
[BF]D.Bini P.Favati, On a matrix algebra related to the discrete Hartley transform. SIMAX 14,1993
[BGHN]A.Bultheel et Al, Orthogonal Rational Functions, Cambridge Univ. Press, 1999
[BGM1]D.Bini L.Gemignani B.Meini, Computations with infinite Toeplitz matrices and polynomials, Lin.Alg.Appl. 343,2002
[BGN]Buzbee,Golub,Nielson, On Direct Methods for Solving Poisson's Equations SIAM NumAn 1970
[BGST]D.Bertaccini,G.Golub,S.Serra, C.Tablino Possio, Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems. T.R.Stanford Univ., 2002
[BHM]A.Björck, P.Heggernes, P.Matstoms, Methods for large scale total least squares problems. SIMAX 22(2000).
[BiBo]D.Bini A.Boettcher, Polynomial factorization through Toeplitz matrix computations, Lin.Alg.Appl. 366, 2003
[BM1]D.Bini B.Meini, Effective methods for solving banded Toeplitz systems. SIMAX 20,1999
[BM3]D.Bini B.Meini, Improved cyclic reduction for solving queueing problems. Num.Algo. 15,1997
[BM4]D.Bini B.Meini, On the solution of a nonlinear matrix equation arising in queueing problems. SIMAX 17,1996
[BP]D.Bini V.Pan. Polynomial and matrix computations. Birkhäuser Boston, 1994
[BRRS]C.Brezinski M.Redivo-Zaglia G.Rodriguez S.Seatzu. Multiparameter regularization techniques for ill-conditioned linear systems, Num.Math.94,2003
[BS]A.Boettcher B.Silbermann, Introduction to Large Truncated Toeplitz Matrices, Springer, New York 1999.
[BTY]D.Bini,E.Tyrtyshnikov,P.Yalamov, Structured Matrices: Recent Developments in Theory and Computation, Nova Science Inc. N.Y.2001
[BvB]A.Bultheel,M.VanBarel, Linear algebra, rational approximation and orthogonal polynomials. North-Holland, Amsterdam, 1997
[C]T.Chan. An optimal preconditioner for Toeplitz systems. SIAM Sci.Stat.Comp.9,1988
[CCSS]R.Chan,T.Chan,L.Shen,Z.Shen, Wavelet deblurring algorithms for spatially varying blur from high-resolution image reconstruction. Lin.Alg.Appl.366,2003
[CGTW]R.Corless,P.Gianni,B.Trager,S.Watt, The Singular Value Decomposition for Polynomial Systems, Proc. ISSAC95
[CN]R.Chan M.Ng, Conjugate gradient methods for Toeplitz systems. SIAM Rev.38,1996
[CPPS]M.Chu,V.Pauca,R.Plemmons, X.Sun, A Mathematical Framework for the Linear Reconstructor Problem in Adaptive Optics. Lin.Alg.Appl. 316,2000
[CS]K.Chadan P.C.Sabatier. Inverse Problems in Quantum Scattering Theory, 2nd ed. Springer, N.Y.1989.
[Da] K.Datta, Numerical Linear Algebra and Applications. 1995, Brooks/Cole Publ.
[DFLZ] C.DiFiore S.Fanelli F.Lepore P.Zellini Matrix algebras in quasi-Newton methods for unconstrained minimization, Num.Math.94,2003
[Di] F.DiBenedetto, Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices. SIAM J.Sci.Comp.16,1995
[22] F.Di Benedetto, Preconditioning of block Toeplitz matrices by sine transforms. SIAM J. Sci. Comp. 18,1997
[DS] F.DiBenedetto, S.Serra Capizzano, A unifying approach to abstract matrix algebra preconditioning. Num.Math. 82,1999
[DV] P.Dewilde A.J. van der Veen, Time-varying Systems and Computations. Kluwer, 1998
[FS] G.Fiorentino, S.Serra Capizzano, Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions. SIAM J.Sci.Comp.17,1996
[FG2] D.Fasino L.Gemignani A Lanczos-type algorithm for the QR factorization of Cauchy-like matrices, Cont.Math. 323,2003
[G7] L.Gemignani. A superfast solver for Sylvester's resultant matrices generated by a stable and an anti-stable polynomial. Lin.Alg.Appl. 366,2003
[GoS]I.Gohberg,A.Semencul, The inversion of finite Toeplitz matricesand their continual analogues. Mat.Issled 7,1972.
[GLR] I.Gohberg,P.Lancaster,L.Rodman, Matrix polynomials. Academic Press, Inc. New York, 1982
[GGK] I.Gohberg,S.Goldberg,M.Kaashoek. Classes of linear operators. Vol. I,II Birkhäuser, Basel, 1990
[GKO] I.Gohberg T.Kailath V.Olshevsky. Fast Gaussian elimination with partial pivoting for matrices with displacement structure. Math.Comp.,64(1995).
[GMRS] T.Goodman,C.Micchelli,G.Rodriguez, S.Seatzu. Spectral factorization of Laurent polynomials. Adv. in Comp.Math., 7, 1997.
[GMRS1] T.Goodman,C.Micchelli,G.Rodriguez,S.Seatzu. On the Cholesky factorisation of the Gram matrix of multivariate functions. SIMAX, 22,2000.
[GS] U.Grenander,G.Szegö, Toeplitz forms and their applications. University of California Press, Berkeley-Los Angeles 1958
[GW] JS.Geronimo, H.Woerdeman. Positive extensions and Fejer-Riesz factorization in Autoregressive Filters in two variable, Ann. Math. to appear.
[H] PC.Hansen. Rank-deficient and discrete ill-posed problems. Numerical aspects of linear inversion. SIAM, Philadelphia, 1997.
[HK] N.Higham,H.Kim, Numerical analysis of a quadratic matrix equation, IMA J.Num.Anal. 2000
[HNP] M.Hanke, J.Nagy, R.Plemmons, Preconditioned iterative regularization for ill-posed problems. Numerical Linear Algebra and Scientific Computing, de Gruyter, 1993
[HR] G.Heinig,K.Rost, Algebraic methods for Toeplitz-like matrices and operators. Birkhäuser, Basel, 1984
[I] I.Iohvidov, Hankel and Toeplitz matrices and forms. Algebraic theory. Birkhäuser, Boston, Mass., 1982
[J] A.Jain, Fundamentals of Digital Image Processing. Prentice-Hall, NJ, 1989
[KS] T.Kailath,A.Sayed Eds., Fast Reliable Methods for Matrices with Structure, SIAM Philadelphia 1999
[KS1] T.Kailath,A.Sayed, Displacement structure: Theory and Applications, SIAM Rev. 37, 1995
[KHMG] S.Kamvar, H.Haveliwala, C.Manning, G.Golub, Exploiting the block structure of the Web for computing PageRank. Tech. Rep., Stanford Univ., 2003
[LR] G.Latouche,V.Ramaswami, Introduction to matrix analytic methods in stochastic modeling. SIAM, Philadelphia, 1999
[M] V.A.Marchenko. Sturm-Liouville operators and applications, Birkhauser, Basel, 1986.
[M1] B.Meini An improved FFT-based version of Ramaswami's formula. Comm. Statist. Stoch. Models, 13,1997
[MRS] C.van der Mee, G.Rodriguez, S.Seatzu. Spectral factorization of bi-infinite multi-index block Toeplitz matrices. Lin.Alg.Appl.2001.
[Ne] M.Neuts, Structured stochastic matrices of M/G/1 type and their applications. Marcel Dekker, Inc., New York, 1989
[NCT]M.Ng,R.Chan,W.Tang, A fast algorithm for deblurring models with Neumann boundary conditions. SIAM Sci.Comp.21 1999
[O] V.Olshevsky Ed., Structured Matrices in Mathematics, Computer Science, and Engineering II, Cont.Math. 281,2001
[RST] G.Rodriguez, S.Seatzu, D.Theis. A new technique for ill-conditioned linear systems. Num.Algo. 33,2003
[S1] S.Serra, Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear. Lin.Alg.Appl. 343/344,2002
[S2] S.Serra, Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs Matrix-sequences. Num.Math. 92,2002
[STy] S.Serra, E.Tyrtyshnikov, Any circulant-like preconditioner for multilevel matrices is not superlinear. SIMAX 21,1999
[St] G.Strang, A proposal for Toeplitz matrix calculations. Stud. Appl. Math. 74,1986
[T] E.Tyrtyshnikov. Optimal and superoptimal circulant preconditioners, SIMAX, 13,1992
[Ti] P.Tilli, Locally Toeplitz sequences: spectral properties and applications. Lin.Alg.Appl. 278,1998
[Tr] W.Trench. An algorithm for the inversion of finite Toeplitz matrices. J. Soc.Indust.Appl.Math. 12 1964
[TZ] E.Tyrtyshnikov,N.Zamarashkin, Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships. Lin.Alg.Appl. 270,1998
[VBM1] R.Vandebril,M.Van Barel,N.Mastronardi, An orthogonal similarity reduction of a matrix to semiseparable form, TW355, K.U. Leuven 2003

2.3 Numero di fasi del Programma di Ricerca: 1

2.4 Descrizione del Programma di Ricerca

Fase 1

Durata: 24 mesi Costo previsto: 187.000 Euro

Descrizione:

Several collaborations already exist among the different Research Units, throughout denoted as U1,U2,U3. In order to better articulate the research activity in a more organic way and to create synergies, we will form a coordination committee formed by the 3 responsibles of the Research Units. This committee will meet periodically to trace the state of the art of the research, to exchange information about the achievements and to program further meetings among the units.

At the beginning of the project we plan to make an initial meeting of the researchers of all the units in order to coordinate the activity. A workshop is planned after about one year to trace the state of the art of the project. A final workshop is planned at the end where the results obtained in the project are presented. The latter workshop is opened to external researchers, belonging to national and international research groups.

A strategic line of the project is to promote the relations between the more applicative aspects (see parts C and D of section 2.1) and the theoretical issues (part A), by supporting and improving the interactions between the researchers who have more experience in the applications with the ones who have a long expertise in structured numerical linear algebra. This will create synergies and benefits for the whole project. In fact, we expect that, on one hand this strategy will favor the use and the application of theoretical and computational tools to the solution of specific problems with the consequent development of effective software and with the substantial reduction of the computational costs. On the other hand, this strategy will allow the researchers to more deeply investigate specific applicative problems and, consequently, to favor the development of new theoretical and computational tools of general use for structured matrix analysis. This strategy will be implemented by periodically organizing short workshops on very specific subjects of interest which, if needed, will be opened to researchers of international groups who can be invited by the single Research Units. Therefore we plan frequent contacts of researchers of the different units and frequent contacts with researchers of other international research groups to be obtained through short visits. An international conference on the specific subject of numerical methods for Markov chains will be organized within the project in June 2005.

Each Research Unit will provide autonomously to creating prototype software concerning all the algorithms designed and analyzed in the specific program. However, in order to make more significant comparisons and in order that each unit can easily use and improve the software made by other units, in the coordinating meetings we will state the common features which all the different pieces of software must satisfy. We will create a network of workstations which constitute the hardware structure where the prototype software made by the different units is kept, tested, elaborated, compared and integrated. This hardware structure will store also the set of test problems which will be constructed in the research activity. The access to the information is opened and is realized by means of web pages.

Concerning the costs of the project we planned some specific expenses, having a global or strategic value, for the overall amount of about 41000 euros. They are: research contracts and research fellowships for 33.000 euros which will strengthen units U1 and U2; the contribution of about 8000 euros (U1) for organizing the fifth edition of the International Workshop "Matrix Analytic Method in Stochastic Models" MAM5, to be held in Pisa, June 2005 (http://www.dm.unipi.it/~mam5). The conference, which covers topics in applied probability, engineering and numerical analysis, is an international forum where the state of the art in the field of numerical methods in applied probability will be traced and discussed.

Concerning the research activity, we will pursue the goals reported in section 2.1 of this form, to which we refer the reader for what follows. Here, rather than giving an exhaustive description of all the parts (which can be found in the "modello B" of each unit), we prefer to point out the synergies between the different parts of the program.

PART A:
More specifically, concerning part A1 on Toeplitz and locally Toeplitz matrices, the picture is quite complete so far concerning the asymptotical spectral analysis (distribution, localization, extremal behaviour), even for locally Toeplitz matrices (including PDEs with variable coefficients or over geometrically more complicated domains). Topics which still deserve more study are
- the analysis of the spectral conditioning (extremal behaviour) for multi-index matrices, by following the approach of Boettcher and Grudsky;
- the analysis of the interplay between spectral properties and convergence of preconditioned iterative methods in the case where asymptotic properties of the sequence of linear systems are known independently of the structure. In fact, we believe that the spectral distribution function plays a fundamental role to this regard even for unstructured problems.
- Concerning multilevel (multi-index) matrices (A7), the analysis is motivated by the need of designing efficient preconditioners (B7) for the iterative solution of multilevel Toeplitz systems encountered in many applications like image processing, integral equations, inverse scattering (B12,C3,C9). Special attention is deserved to the following topics.
- Multigrid methods (B6), where special emphasis is addressed to the choice of projector/smoother, to the extension of the optimality [ADSC] to the multilevel case, applications to image restoration (C3) and to PDEs (B5).
- Preconditioning (B7), trying to generalize the optimality results of [S. Serra, MathComp. 66,1997] to the multilevel case; introducing "enriched" matrix algebras of the kind UTU* (A4) as preconditioners, where U is unitary (related to a fast transform) and T has some sparsity feature in order to find preconditioners which are superlinear or optimal. Designing preconditioners for the GMRES (B13) where the preconditioner is updated at each step of the iteration.
- Projection methods in weighted Wiener algebras (B14) [Boettcher, Silbermann, "Analysis of Toeplitz operators" Springer 1990, Gohberg, Feldman, vol 41 of Transl. Math. Monog. 1974] will be considered for possible extension to multilevel Toeplitz matrices in the nondefinite and in the positive definite block case.
- Generation of classes of test matrices (D1) by generalizing the results of [MNS,MS].
- Using the computational methods of [MRS1] for infinite multilevel perturbed Toeplitz systems for the numerical solution of integral equations with structured kernel (B12).
- Applications to inverse scattering problems in acoustics, quantum mechanics, and remote sensing (C9).

Concerning part A2 on semi-separable matrices, we will investigate on
- the interplay between diagonal plus semiseparable matrices and rational Krylov matrices and orthogonal rational functions;
- semiseparability properties of generalized companion matrices (see part A5) and eigenvalues computation (B2); in particular on the properties of the QR iteration applied to generalized nxn companion matrices and on algorithms for the QR step in O(n) ops [BDG], with applications to polynomial rootfinding (B8);
- reduction to a general symmetric matrix into semiseparable form.

Sequences of parametric matrices of the kind Aj=A+vj Ej will be investigated in part A3. This is a generalization of shifted sequences where Ej is the identity matrix. Systems with this class of matrices are encountered in several popular techniques for eigenvalues computation. Here we investigate on indefinite incomplete updated factorization preconditioners, with Krylov projection methods, and multilevel incomplete factorizations. Application of these techniques to solving total least squares problems (TLS) are considered.

In part A4 concerning new matrix algebras, besides the enriched matrices cited above, we analyze the use of matrix algebras in approximating the Hessian matrix in minimization problems (B11) in the line of [DFLZ]. Other matrix algebras will be analyzed in studying the role of boundary conditions in image restoration problems (C3, B4).

Concerning generalized companion and resultant matrices in part A5 we consider nxn diagonal plus rank-one matrices, arrowhead matrices, commerade and Frobenius matrices for which there is an explicit relation between their entries and their characteristic polynomial. Algorithms for performing one step of the QR iteration with O(n) cost will be designed and analyzed in terms of their complexity and stability. The problem of computing all the eigenvalues of generalized companion matrices is investigated (B2) with extension to higher rank corrections. This part is related with part A2 for the semiseparable structure, and with part B8 for the design of polynomial rootfinders.

We consider also resultant matrices whose characteristic polynomial is a multiple of the resultant of two polynomials, say Bezout matrices. Here the goal is to represent such matrices in different polynomial bases, say Bernstein polynomials, and analyze and exploit the matrix structures in order to find more efficient algorithms for certain polynomial computations (B8).

Block Toeplitz matrices of part A6 will be investigated in the attempt to extend to positive definite multilevel block Toeplitz matrices the results of Boettcher, Silbermann, and of Gohberg, Feldman on weighted Wiener algebras.

Semi-infinite Toeplitz matrices (A8) and Wiener-Hopf factorizations (B10) will be investigated with the aim of providing a better understanding of the numerical solution of certain Markov chains encountered in queueing models (C6) and in order to provide still more efficient solution algorithms in the line of [BM,BM3,BM4]

Nonconventional structures in part A9 consist of any matrix structures which do not fall in the described classes. In fact, we expect to encounter new structures from the analysis of applications, especially in web search engines (C1) queueing models (C6), problems in astronomy (C9).

Part B:
Structured linear systems in part B1 will be dealt in terms of preconditioned iterative methods and multigrid according to the structure involved. Eigenvalue problems will be similarly treated in terms of the underlying structures.

Functional approximation issues in part B3 will pursue the previous research on interpolation and approximation problems with rational functions, particularly to the analysis of structured conditioning issues and optimal pole placements.

Inverse problems analysis (B4) will concern the analysis of the number of iterations as a regularizing parameter, another direction concerns the extension of regularizing families of preconditioners to the reconstruction of nonnegative images and applications to the LBT system. Another topic is the design and analysis of algorithms for systems obtained by Tikhonov-like regularization.

Concerning PDEs (B5), convergence properties of GMRES in solving systems discretizing the convection-diffusion equation with variable diffusion coefficients are investigated, as well as time-dependent convection-diffusion equations in human metabolism models (C2).

Multigrid technique will be used for regularizing the solution of ill-posed problems (B6,B4).

Preconditioning (B7) is mainly concerned with multilevel Toeplitz matrices

Concerning polynomial computations (B8), the properties of weak Wiener-Hopf factorizations (B10) are analyzed, where both the factors in the factorization may have zeros of unit modulus; polynomial root-finders are designed based on the QR algorithm applied to generalized companion matrices (A5) which maintain the semi-separable structure (A2). The representations of polynomials in the Bernstein basis together with their structured matrix counterparts are studied in order to design efficient algorithms for the intersection of Bezier curves and of surfaces with applications in CAGD (C7). We will relay on hybrid techniques for the related computational problems with tools in projective geometry, computer algebra and numerical analysis. Finally, algorithms for the computation of the eigenvalues of tridiagonal matrices are considered.

Concerning matrix equations (B9) we continue the study of [BM], [BGM1],[BGM2],[BG2].
- We investigate the generalization of the shift technique (introduced in [He,Meini,Rhee, SIMAX,23 2001/02] in the context of Markov chains) to general matrix equations of polynomial type.
- The cyclic reduction algorithm of G. Golub [BGN] adjusted to Markov chains by [BM3],[BM4] and analyzed in [BGM1],[BGM2], will be considered for solving algebraic Riccati equations. Also the computation of the principal p-th root of a matrix will be faced in terms of Wiener-Hopf factorizations (B10), Laurent series inversion and Newton's iteration and with the techniques of [M4], [Ia]
- Matrix equations modeling queueing problems will be taken into account.

For minimization problems (B11) the study of [D], [DFLZ], [DLZ] is continued with the analysis of sufficient conditions which guarantee the convergence of the quasi-Newton minimization techniques where the Hessian matrix is replaced with a matrix in the Hartley algebra [BF] or with some structured matrix. Here the conditions will concern the boundedness of the operators appearing in the minimization process and on the condition number of the structured matrix. Also algorithms for total least squares problems for structured matrices will be analyzed with applications to blind image deblurring (A1,C3).

Integral equation B12 will be considered in connection with multilevel semi-infinite Toeplitz systems (A7,A8) with applications in inverse scattering, acoustics and remote sensing (C4) and in astronomy problems (C9).

PART C:
- Concerning C1, the most recent web search engines compute the dominant eigenvalue of a sparse block matrix with a rank-one correction [KHMG]. Here our goal is to design faster algorithms for computing the PageRank vector.
- The two-level quasi-Newton approach implemented for remote sensing problems, will be used together with the structured matrix technology for solving nonlinear inverse scattering problems in electric engineering (C4).
- Non-classical inverse eigenvalue problems for tridiagonal matrices and other closely related matrix structures (also including diagonal-plus-semiseparable matrices) have been used as models in identification problems (C5) in civil engineering. Our aim is solving both theoretical and computational issues arising in this framework.
- The most part of queueing models encountered in engineering (telecommunications, internet, metropolitan networks) are modeled by Markov chains described by infinite block Toeplitz matrices. We aim to continue applying the Toeplitz tools to solving the main computational problems encountered in this framework, among which solving matrix equations and solving infinite systems, in the line of [Anastasi, Lenzini, Meini, Perf.Eval. 29,1997].

Problems of CAGD (C7) involve computing intersection of curves and surfaces represented in terms of Bernstein polynomials. Many computational problems can be reduced to performing operations with structured matrices (Bezout, Sylvester etc). The aim is to apply structured matrix technology to the problems in this area together with tools in computer algebra and projective geometry by integrating symbolic and numerical computations.

Neural networks and automatic learning (C8) are applications of algorithms for minimization problems (B11).

PART D:
Concerning part D, we already mentioned test matrices (D1). Here we want to continue the line of the previous project 2002-2003. We propose to develop a Matlab toolbox specialized to structured matrices with the following features: 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. In this part we intend to better organize the experimental work made by the different units and the different researchers in the previous project, by providing a common framework based on Matlab.

In the project we planned the following collaborations partially started in the previous project 2002-2003:

D. Calvetti and G. Saidel (Ohio),
G. Golub (Stanford)
A. Morassi (Udine)
D. Noutsos and P. Vassalos (Ioannina)
M. Pastorino (DIBE, Genova)
M. Van Barel, S. Van Huffel (Leuven)
G. Latouche (Bruxelles)
N. Higham, F. Tisseur (Manchester)
J. Winkler (Sheffield)
V. Pan (New York)
N. Rhee e K.Sorhaby (Kansas City)
L. Rodman and I.M. Spitkovsky, H.J. Woerdeman (College of William and Mary)
C. Brezinski (Lille)
M. Tasche (Rostock, Germany)

Subjects treated by each unit:

U1: A1 A2 __ A4 A5 A6 __ A8 A9
U2: A1 A2 A3 A4 A5 A6 A7 __ A9
U3: A1 ___________ A6 A7 A8 A9

U1: B1 B2 ______________ B8 B9 B10 B11 ___ ___ ___
U2: B1 B2 B3 B4 B5 B6 B7 _________________ B13 ___
U3: B1 _____ B4 _____ B7 _____ B10 ___ B12 B13 B14

U1: __ __ __ __ __ C6 C7 C8 __ __ __ D3
U2: C1 C2 C3 C4 C5 __ __ __ __ __ __ D3
U3: __ __ __ C4 __ __ __ __ C9 D1 D2 D3

Risultati parziali attesi:

We expect that the theoretical achievements of our research (part A) will allow us to obtain very effective computational and algorithmic advances, among which:

U1,U3: Better understanding of numerical methods for structured Markov chains (C6) in terms of weak Wiener-Hopf factorizations (B10,A1,A6,A8). New existence results on Wiener-Hopf factorization for certain multilevel block Toeplitz matrices.

U1: Efficient solution of fluid queues obtained (C6, B9) with cyclic reduction and Cayley transform. Computation of reward of M/G/1 Markov chains (C6). Extension and generalization of the shift technique to general Markov chains (B9,C6)

U1: Algorithms for the p-th root of a matrix (B9) and Wiener-Hopf factorizations (B10). Solution of algebraic Riccati (B9) equations by cyclic reduction

U1: Analysis of algorithms for polynomials represented in the Bernstein basis with applications to CAGD (B8, C7)

U1: Design and analysis of quasi-Newton minimization methods based on approximating the Hessian matrix in matrix algebras, applications to neural networks (A4, B11, C8).

U1, U2: Design analysis and implementation of polynomial rootfinders based on the computation of eigenvalues of diagonal plus rank-one matrices (A2, B8, B2). Polynomial rootfinders for polynomials represented in terms of Szego polynomials computed as eigenvalues of unitary Hessenberg matrices plus rank-one (A2, B8). Algorithms for eigenvalues of diagonal plus semiseparable matrices (A2,A5,B2). Reduction of simmetric matrices to semiseparable form (A2,B2).

U1,U2: Analysis of total least squares problems for structured matrices (B1)

U2: Design of algorithms for parametric systems based on Krylov projection methods and multilevel preconditioning (A3, A7, B7, B13)

U2: Inverse problems in imaging, extension of regularizing families of preconditioners, reconstruction of nonnegative images, design of algorithms for linear systems generated by Tikhonov-like regularization, applications to the LBT problem (A1,B4,C3)

U2: Denoising by wavelets in astronomical images, chopped and nodded images (near infrared), measured PSF used in classical restoration, over-iterated reconstruction (B4,C3).

U2,U3: Preconditioning analysis for the GMRES, applications to PDEs in convection diffusion problems in d-dimensional domains (B13, B5, A7). Use of GMRES and Krylov subspaces for ill conditioned structured systems (B13, A7, B15).

U1,U2: Regularization by multigrid, design of algorithms based on multigrid techniques for the regularized solution of ill conditioned systems, applications to image processing (B6, B15, C3).

U2: Analysis of boundary conditions in image restoration, analysis of anti-reflective conditions, analysis of the associated matrix algebra, analysis of the interplay of boundary conditions and regularization (A1,A4,B15,C3).

U2: Web search engines, analysis of the structures encountered in problems of information retrieval (Google) in order to improve the efficiency of their solution, by computing the dominant eigenvector of large sparse plus rank-one matrices (C1)

U3: Design analysis and implementation of prototype software for solving (perturbed) semi-infinite matrices (A8,B1,D3)

U3: Analysis of nonconventional matrix structures arising from the analysis of polarized light propagation in astronomy problems (C9)

U3: Creation of a set of multilevel (multi-index) test matrices with the identification of their asymptotic condition number (A7, D1). Creation of a MatLab toolbox with the main software for structured matrices (D2).

U1,U2,U3: Implementation and validation of the algorithms designed in the project at a prototype level (D3).

Among the expected results we have the organization of the international conference "Matrix Analytic Methods in Stochastic Models", Pisa June 2005, and the organization of intermediate coordination workshops and of a final workshop concluding the project.

We also expect to create the web pages of the project where the research advances are reported with a continuous update, and where the most recent results, in the form of reports (postscript or pdf files), can be freely downloaded as well as the software developed during the project.

Unita' di ricerca impegnate: · Unità nº 1· Unità nº 2· Unità nº 3

2.5 Criteri suggeriti per la valutazione globale e delle singole fasi

The evaluation of the project should be done in terms of the quality of the scientific results obtained. This evaluation can be performed as follows:
1- by looking at the quality of the journals where the main results are published;
2- by looking at the international visibility and dissemination of the results; this can be performed by looking at the number and the relevance of the international conferences where the results are presented.
3- The quality of the algorithmic achievements can be also evaluated in terms of the reduction of the cpu time needed to execute the algorithms and in terms of the numerical performances.
A dynamical monitoring will be performed: as already written in part 2.4, the coordinating committee, formed by the coordinators of the Research Units, will meet periodically. At the end of each meeting, a report on the state of the advancement of the project will be written and inserted in a web page containing all the relevant information of the project.