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

BINI  DARIO ANDREA 
Professore Ordinario  02/01/1950  BNIDND50A02F023O 
MAT/08 - Analisi numerica 
Università di PISA 
Facoltà di SCIENZE MATEMATICHE FISICHE e NATURALI  
Dipartimento di MATEMATICA "Leonida Tonelli" 
050/2213279
(Prefisso e telefono)
 
050/2213224
(Numero fax)
 
bini@dm.unipi.it
(Email)
 


1.5 Curriculum scientifico del Responsabile Scientifico dell'Unità di Ricerca

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.6 Pubblicazioni scientifiche più significative del Responsabile Scientifico dell'Unità 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.; G. LATOUCHE; B. MEINI (2002). Solving matrix polynomial equations arising in queueing problems LINEAR ALGEBRA AND ITS APPLICATIONS. (vol. 340 pp. 225-244)  
3. 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)  
4. BINI D.A.; FIORENTINO G. (2000). Design, Analysis and Implementation of a Multiprecision Polynomial Rootfinder NUMERICAL ALGORITHMS. (vol. 23 pp. 127-173)  
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.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. BINI  Dario Andrea  Dip. MATEMATICA  Prof. Ordinario  MAT/08  9  7 
2. GEMIGNANI  Luca  Dip. MATEMATICA  Prof. Associato  MAT/08  8  6 
3. MEINI  Beatrice  Dip. MATEMATICA  Ricercatore Universitario  MAT/08  9  6 
4. STEFFE'  Sergio  Dip. MATEMATICA  Prof. Associato  MAT/08  8  7 
5. BOZZO  Enrico  Dip. INFORMATICA  Ricercatore Universitario  MAT/08  7  7 
6. TRAVERSO  Carlo  Dip. MATEMATICA  Prof. Ordinario  MAT/02  3  3 
7. GIANNI  Patrizia  Dip. MATEMATICA  Prof. Ordinario  MAT/02  3  3 
  TOTALE              47  39 


Altro personale

Cognome  Nome  Dipartimento   Qualifica  Mesi Uomo 
1° anno  2° anno 
1. Fiorentino  Giuseppe  Dip. MATEMATICA  Tecnico Laureato  3  3 
  TOTALE          


1.7.2 Personale universitario di altre Università

Personale docente

Cognome  Nome  Università  Dipartimento  Qualifica  Settore Disc.  Mesi Uomo 
1° anno  2° anno 
1. ZELLINI  Paolo  ROMA "Tor Vergata"  Dip. MATEMATICA  PO  MAT/08  9  8 
2. DI FIORE  Carmine  ROMA "Tor Vergata"  Dip. MATEMATICA  RU  MAT/08  9  8 
3. FANELLI  Stefano  ROMA "Tor Vergata"  Dip. MATEMATICA  PA  MAT/08  9  8 
  TOTALE                 27  24 


Altro personale

Cognome  Nome  Università  Dipartimento   Qualifica  Mesi Uomo 
1° anno  2° anno 
1. Arico'  Antonio  Università degli Studi di PAVIA  Matematica "F. Casorati"  Dottorando  8  7 
  TOTALE             


1.7.3 Titolari di assegni di ricerca


Nessuno

1.7.4 Titolari di borse

Cognome  Nome  Dipartimento  Anno di inizio borsa  Durata
(in anni) 
Tipologia  Mesi Uomo 
1° anno  2° anno 
1. Iannazzo  Bruno  Dip. MATEMATICA  2004  3  Dottorato  8  8 
  TOTALE                


1.7.5 Personale a contratto da destinare a questo specifico programma

Qualifica  Costo previsto  Mesi Uomo  Note 
1° anno  2° anno 
1. Altre tipologie  15.000  4  6  Contratto di ricerca per laureato 
  TOTALE  15.000    


1.7.6 Personale extrauniversitario indipendente o dipendente da altri Enti

Cognome  Nome  Nome dell'ente  Qualifica  Mesi Uomo 
1° anno  2° anno 
1. Mastronardi  Nicola  CNR-IAC (Bari)  Primo ricercatore  5  5 
  TOTALE          





PARTE II

2.1 Titolo specifico del programma svolto dall'Unità di Ricerca

Numerical and algebraic computations with structured matrices and polynomials: analysis and applications


2.2 Settori scientifico-disciplinari interessati dal Programma di Ricerca

 

MAT/08 - Analisi numerica 
MAT/02 - Algebra 


2.3 Parole chiave
STRUCTURED MATRICES ; TOEPLITZ MATRICES ; SEMISEPARABLE MATRICES ; NUMERICAL METHODS FOR MARKOV CHAINS ; MATRIX EQUATIONS ; POLYNOMIAL COMPUTATIONS


2.4 Base di partenza scientifica nazionale o internazionale

Large part of important problems in pure and applied mathematics involves structured matrices. The analysis of theoretical and computational properties of these structures is a fundamental step in the design of efficient algorithms. Matrix structures are inherited by the specific properties of the problem. Common features shared by problems in different areas, like shift invariance, compact support, separability of variables, turn into structures which are common to matrices encountered in different fields, like the Toeplitz structure, the displacement structure (including Hankel, Cauchy, Bezout, Frobenius, Pick, Vandermonde matrices), band matrices, semiseparable matrices, arrowhead matrices etc. In fact, these structures are encountered in many different problems in statistics, probability, queueing theory, polynomial computations, computer algebra, CAGD, numerical solution of differential and of integral equations, image and signal processing.


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 some active researchers. Most recently a very strong interest has been devoted to several research problems related to structured analysis and computations. A wide literature has been consolidated on different related mathematical problems. Many international research groups have grown around these problems and many international conferences specially devoted to structured matrix analysis and its applications have been organized.

The main advances in this field are also reported in some books related to this research area, some of which are milestones in this field: 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 and on more computational issues, the book 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] 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 very recent advances in the field, and the review paper by Chan and Ng [CN] on Toeplitz preconditioning.


Concerning the more specific research subjects of this Research Unit, we cite as starting basis the theory of displacement operators by Kailath et al [KS] and the large literature originated around it. Specifically, the analysis of displacement operators and representation formulae for Toeplitz-like matrices [DZ], [DF],[BZ],[Bo1] and the problems related to structured matrix algebras (trigonometric algebras) [Bo2],[BD],[BF]. We cite the interplay of structured computations and polynomial computations [BP], and the wide existing literature, among which [BiBo], [BGM1], [G1-G7]. We cite also the methodological approach of the interplay between numerical and symbolic computations and the mess of results originated by the European project FRISCO (FRamework for the Integration of Symbolic and numeric Computing) which constitutes a solid basis for our research. We cite [CGTW] where numeric and symbolic tools are used in computer algebra. We cite the spectral theory of Toeplitz matrices [BS], [GS] with the many papers on preconditioning theory and the many applications. All these tools which constitute the "Structured matrix technology" have a fundamental importance in the solution of many problems of interest for this Unit, among which

-- Polynomial computations
-- Numerical solution of Toeplitz-like systems
-- Numerical solution of Markov chains and problems in queueing theory
-- Solving matrix equations
-- Minimum problems and least squares
-- Intersection of surfaces and of curves in CAGD
-- analysis of semiseparable structures

for which recently we had impressive achievements.

In fact, polynomial computations are strongly related to structured matrices [BP]. In the papers [G1-G7], [BiBo],[BGM1], the interplay between structured matrices and polynomials is pointed out and exploited for computational purposes. Problems concerning the location and the approximation of polynomial zeros are solved in terms of LU factorization of Hankel and Bezout matrices over (finite) fields or integral domains [G2-G4]. These methods rely on the Schur complement properties of certain structured matrices. These properties are used in [BG1] for the effective computation of the generalized Euclidean algorithm. Methods for approximating polynomial zeros are obtained by reinterpreting the LR algorithm applied to suitable structured matrices [G5-G7]. The most recent results concern the problem of factoring polynomials or analytic functions with respect to the unit circle, and the computation of spectral factorizations in terms of the Wiener-Hopf factorization [BGM1],[BiBo].

Concerning the computation of Wiener-Hopf factorization, Laurent polynomials and bi-infinite Toeplitz matrix inversion, the most recent results are in [BGM1] where the Graeffe method is used for inverting Laurent polynomials.

Another set of problems for which there is a solid basis concerns the theory of displacement operators and the concept of approximate displacement rank [BM6]. Successful applications are shown to image restoration problems [BM6] and to Toeplitz least squares [BCV]. Preconditioning techniques have a very wide basis [KS],[KS1].

Many problems in queueing theory modeled by Markov chains (see [Ne], [LR]) are described by Toeplitz matrices which often have additional structures [BMR]. The results obtained in [BM1], [BM3], [BM4], based on structure analysis, lead to new algorithms which are much faster than the ones available in the literature with a speedup factor of several hundreds. The Fast Ramaswami Formula of [M1] allows a strong acceleration on the computation of certain Markov chains, based on the use of Toeplitz computations and FFT. In [BM3] the cyclic reduction algorithm is applied and extended to the solution of block tridiagonal block Toeplitz systems and to systems in generalized Hessenberg form.

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 [HK]. In [BM4], [M3], [BGM2] new effective methods based on structure analysis are designed; specific analysis and new solution algorithms are presented in [M4],[M3].

Recently, application of structured matrix analysis to unstructured minimization problems has shown to be very effective [D],[DFLZ],[DLZ]. Application to neural networks is made in [BDFZ]. Analysis of structured total least squares problems is performed in [MLV], [LMV], applications to Speech compression are shown in [LMV1].

Problems in computer aided geometric design (CAGD) involve playing with Bernstein polynomials and Bezier curves. These manipulations are very delicate from the numerical point of view due to ill-conditioning of certain transformations. For this reason, hybrid algorithms which complement numerical computations with symbolic computations are particularly effective. Besides [G1] and the already cited mess of results of the FRISCO project, some studies have been carried out by J. Winkler on the conditioning of such transformations. More recently some results have been stated relating Bernstein polynomials and Bezout matrices [BG1], [BGW].

Besides the classical results on semiseparable structures of Gohberg, Eidelman, Dewilde, Chandrasekaran, recently some important 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. In [BDG] it is shown that the QR iteration applied to a Frobenius matrix leave unchanged the semiseparable structure and an O(n) algorithm for the QR iteration is designed. Other related results are in [FMV], [FG1], [FG3].

This research Unit has a long tradition in structured matrix analysis and in polynomial and matrix computations. The expertise of the members of the Unit includes theoretical and computational issues, design and analysis of algorithms and software. Some members are very active in certain applications concerning the numerical solution of Markov chains and of matrix equations. Recent results have been obtained in the project of which this document is a proposal of continuation.


2.4.a Riferimenti bibliografici

[BCV] D.Bini,G.Codevico,M.Van Barel, Solving Toeplitz Least Squares Problems by Means of Newton's Iteration, Num.Algo.,33,2003
[BD] E.Bozzo,C.Di Fiore, On the use of certain matrix algebras associated with discrete trigonometric transforms in matrix displacement decomposition. SIMAX 16,1995
[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.NeuralNetworks 14,2003
[BDG] D.Bini F.Daddi L.Gemignani. On the shifted QR iteration applied to Frobenius matrices, Dip.Mat., Univ. Pisa 2003
[BF] D.Bini P.Favati, On a matrix algebra related to the discrete Hartley transform. SIMAX 14,1993
[BFi] D.Bini G.Fiorentino, Design, analysis, and implementation of a multiprecision polynomial rootfinder. Num.Algo. 23,2000
[BG1] D.Bini L.Gemignani, Fast fraction-free triangularization of Bezoutians with applications to sub-resultant chain computation. Lin.Alg.Appl. 284,1998
[BGN] Buzbee,Golub,Nielson, On Direct Methods for Solving Poisson's Equations SIAM NumAn 1970
[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
[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
[BiBo] D.Bini A.Boettcher, Polynomial factorization through Toeplitz matrix computations, Lin.Alg.Appl. 366, 2003
[BLM] D.A.Bini G.Latouche B.Meini, Solving nonlinear matrix equations arising in tree-like stochastic processes,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
[BM6] D.Bini,B.Meini, Approximate displacement rank and applications, Cont. Math., 281,2002
[BMR] D.Bini B.Meini V.Ramaswami, Analyzing M/G/1 paradigms through QBDs: the role of the block structure in computing the matrix G, in Adv. in Alg. Methods for Stoch. Models, Notable Publications, 2000
[Bo1] E.Bozzo, A note on matrix displacement representation. Int. Eq. Op. Th. 29,1997
[Bo2] E.Bozzo, Algebras in matrix spaces with displacement structure. Lin.Mult.Alg. 42,1997
[BP] D.Bini V.Pan. Polynomial and matrix computations. Vol. 1. Birkhäuser Boston, 1994
[BS] A.Boettcher B.Silbermann, Introduction to Large Truncated Toeplitz Matrices, Universitext, Springer-Verlag, 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
[BZ] R.Bevilacqua,P.Zellini, Structure of algebras of commutative matrices. Lin.Alg.Appl. 233,1996
[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
[D] C.DiFiore, Structured matrices in unconstrained minimization methods, Cont. Math. 323,2003
[Da] K.Datta, Numerical Linear Algebra and Applications. 1995, Brooks/Cole Publ.
[DF] C.DiFiore, Matrix algebras in displacement decomposition. SIMAX 2000.
[DFLZ] C.DiFiore S.Fanelli F.Lepore P.Zellini Matrix algebras in quasi-Newton methods for unconstrained minimization, Num.Math. 94,2003
[DLZ] C.DiFiore F.Lepore P.Zellini, Hartley-type algebras in displacement and optimization strategies, Lin.Alg.Appl. 366,2003
[DV] P.Dewilde A.J. van der Veen, Time-varying Systems and Computations. Kluwer, 1998
[FG1] D.Fasino L.Gemignani. Fast and stable solution of banded-plus-semiseparable linear systems. CALCOLO 39,2002
[FG2] D.Fasino L.Gemignani A Lanczos-type algorithm for the QR factorization of Cauchy-like matrices, Cont.Math. 323,2003
[FG3] D.Fasino L.Gemignani Direct and inverse eigenvalue problems for diagonal-plus-semiseparable matrices, Num.Algo.34,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
[G1] L.Gemignani, A hybrid approach to the computation of the inertia of a parametric family of Bezoutians with application to some stability problems for bivariate polynomials. Lin.Alg.Appl. 283,1998
[G2] L.Gemignani, Computing a factor of a polynomial by means of multishift LR algorithms. SIMAX 19,1998
[G3] L.Gemignani, Schur complements of Bezoutians and the inversion of block Hankel and block Toeplitz matrices. Lin.Alg.Appl. 253,1997
[G4] L.Gemignani, Computationally efficient applications of the Euclidean algorithm to zero location. Lin.Alg.Appl. 249,1996
[G5] L.Gemignani, Polynomial root computation by means of the LR algorithm. BIT 37,1997
[G6] L.Gemignani, Computing a Hurwitz factorization of a polynomial. J. Comput.Appl.Math. 126,2000
[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
[GL] L.Gemignani G.Lotti. Efficient and stable solution of M-matrix linear systems of (block) Hessenberg form. SIMAX 24,2003
[GLR] I.Gohberg,P.Lancaster,L.Rodman, Matrix polynomials. Academic Press, Inc. New York, 1982
[GoS] I.Gohberg,A.Semencul, The inversion of finite Toeplitz matrices and their continual analogues. Mat. Issled. 7,1972
[GGK] I.Gohberg,S.Goldberg,M.Kaashoek. Classes of linear operators. Vol. I, Birkhäuser, Basel, 1990
[GS] U.Grenander,G.Szegö, Toeplitz forms and their applications. University of California Press, Berkeley-Los Angeles 1958
[HK] N.Higham,H.Kim, Numerical analysis of a quadratic matrix equation, IMA J. Num.Anal. 2000
[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
[Ia] B.Iannazzo, A note on computing the matrix square root. CALCOLO, 2004.
[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 Review 37, 1995
[LR] G.Latouche,V.Ramaswami, Introduction to matrix analytic methods in stochastic modeling. SIAM, Philadelphia, 1999
[LMV] P.Lemmerling,N.Mastronardi,S.VanHuffel, Fast algorithm for Solving the Hankel/Toeplitz Structured Total Least Squares Problem, Num.Algo, 23,2000
[LMV1] P.Lemmerling, N.Mastronardi, S.VanHuffel, Efficient implementation of a structured total least squares based speech compression method, Lin.Alg.Appl. 366,2003
[M1] B.Meini An improved FFT-based version of Ramaswami's formula. Comm. Statist. Stoch. Models, 13,1997
[M3] B.Meini, Efficient computation of the extreme solutions of X+A^* X^{-1}A=Q and X-A^*X^{-1}A=Q, Math. of Comp.2001
[M4] B.Meini, The matrix square root from a new functional perspective: theoretical results and computational issues , SIMAX to appear
[MLV] N.Mastronardi,P.Lemmerling,S. Van Huffel, Fast structured total least squares algorithm for solving the basic deconvolution problem, SIMAX 22,2000
[Ne] M.Neuts, Structured stochastic matrices of M/G/1 type and their applications. Marcel Dekker, Inc., New York, 1989
[O] V.Olshevsky Ed., Structured Matrices in Mathematics, Computer Science, and Engineering II, Cont. Math. 281, 2001
[Tr] W.Trench. An algorithm for the inversion of finite Toeplitz matrices. J. Soc. Indust. Appl. Math. 12 1964
[VBM1] R.Vandebril, M.Van Barel, N.Mastronardi, An orthogonal similarity reduction of a matrix to semiseparable form, TW355, K.U. Leuven 2003


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

Large part of important problems in pure and applied mathematics involves structured matrices. The analysis of theoretical and computational properties of these structures is a fundamental step in the design of efficient algorithms specifically designed for these problems especially in the very frequent cases where the general solution algorithms cannot be applied due to the huge size of the problem.

Matrix structures are inherited by the specific properties of the problem. Common features shared by problems in different areas, like shift invariance, compact support, separability of variables, turn into structures which are common to matrices encountered in different fields, like the Toeplitz structure, the displacement structure (including Hankel, Cauchy, Bezout, Frobenius, Pick, Vandermonde matrices), band matrices, semi-separable matrices, arrowhead matrices etc. In fact, these structures are encountered in many different problems in statistics, probability, queueing theory (including telecommunications, internet, performance analysis, stochastic processes), polynomial computations, computer algebra, Computer Aided Geometric Design, numerical solution of differential and of integral equations, image and signal processing just to quote a few.

Very often the properties of the original problem turn into structures which are not so evident, say, nonlinear structures like displacement structure, semi-separable or quasi-separable matrices, where the matrix under analysis looks like a "general" matrix.

The analysis of matrix structures and the consequent design of specific algorithms for solving problems in numerical linear algebra has received a great attention and has produced important advances in the algorithm design. On one hand, important theoretical advances have been reached in the study of theoretical properties of certain structured matrices, on the other hand the design of specific algorithms has allowed the effective solution of important problems in different applicative fields. Just to quote a few, algorithms for solving matrix equations, or for solving queueing models based on Toeplitz computations or on Wiener-Hopf factorization, recently designed, allowed to reduce the cpu time of a large factor still maintaining very good numerical performances [ALM]. In certain cases, the structured matrix tools have provided fast solution of unstructured problems [D], [DFLZ], [DLZ].

Summing up, the research of this unit are dictated by the following general guidelines and motivations:

1- Structured matrices play a fundamental role in a great part of mathematical models in applications and are almost pervasive.

2- The analysis of structured matrices, besides its theoretical interest, is a fundamental step for the design of specific solution algorithms. The results obtained in this way constitute a general toolbox which is useful in many different contexts and situations and constitutes the structured matrix technology.

3- The structured matrix technology can be used to effectively solve large scale problems of great importance in the applications, which could be hardly solved with general algorithms. At the same time, even for the solution of general unstructured problems, the structured matrix technology may provide important improvements.

4- The design and the analysis of algorithms taylored on the specific structures of the problem is not enough in itself. It must be integrated by a rigorous analysis of robustness and of numerical stability. In certain situations where the ill conditioning is an intrinsic feature of the problem, the use of multi-precision arithmetic or the use of hybrid approaches based on symbolic and numeric tools becomes a required step.


GENERAL RESARCH LINES

The research activity will be carried out according to the following research lines:

-A- To perform the analysis of algebraic, structural, analytic, spectral and computational properties of structured matrices which intervene in theoretical and applied mathematics (including Toeplitz, Hankel Bezout, Cauchy, Frobenius, and displacement generated matrices, banded matrices, semi-separable and quasi-separable matrices, arrowhead matrices, matrices with scalar entries and with blocks, multilevel matrices).

-B- To exploit the properties obtained from this analysis for creating general methodologies for the design and analysis of effective solution algorithms.

-C- To apply the solution algorithms to problems coming from certain applications and from large scale scientific computing.

-D- To implement, in terms of prototype software, the algorithms designed in this research and to perform experimental validation and comparison.

-E- To perform a theoretical or experimental rounding error analysis and robustness analysis in order to select reliable algorithms. For problems endowed of intrinsic ill conditioning, to design new techniques based on the use of multiple precision arithmetic complemented with the strategy of adaptiveness, and integrating numerical and symbolic tools into hybrid algorithms.


SPECIFIC TOPICS:

Specific topics of our research are:

1- Polynomial computations: Analysis of (weak) Wiener-Hopf factorizations where both the factors may have zeros of unit modulus. Polynomial root-finders based on the QR algorithm applied to generalized companion matrices which maintain the semi-separable (or quasi-separable) structure. Polynomial rootfinders based on Newton's and Laguerre's iteration whith Gerschgorin-like inclusion theorems and the concepts of pseudozeros. Using the representation of polynomials in the Bernstein basis together with their structured matrix counterpart in order to design efficient algorithms for the intersection of Bezier curves and of surfaces. Using hybrid techniques for the related computational problems with tools in projective geometry, computer algebra and numerical analysis. Computing eigenvalues of tridiagonal matrices.

2- Matrix equations: the aim is designing algorithms for solving matrix equations based on Wiener-Hopf factorizations. Algorithms for the Riccati equation, algorithms for computing the principal p-th root of a matrix.

3- Structural and computational properties of semi-separable, quasi-separable matrices, Toeplitz matrices and matrices in trigonometric algebras: one of the aim is designing algorithms for the computation of eigenvalues and for polynomial rootfinders (see part 1)

4- Minimization problems: design and analysis of quasi-Newton algorithms for minimization problems where the Hessian matrix is approximated by a structured matrix. Solving total least squares problems.

5- Applications of part 1) to solving Computer Aided Geometric Design problems like intersection of curves and of surfaces parametrically or implicitly assigned; application of part 2) to solving Markov chains encountered in queueing models; application of part 3) to the design of algorithms for polynomial rootfinding; application of part 4) to solving neural networks.




MAIN TASKS

Concerning part 1) we wish to generalize and extend the shift techniques introduced in [HMR], [BM7] for accelerating the convergence of solving certain equations in Markov chains, in order to deal with more general cases where the Wiener-Hopf factors may have zeros of modulus 1.
-- We wish also to investigate more closely on the algorithm designed in [BDG] where the QR iteration applied to an nxn Frobenius matrix is performed in O(n) ops per step. Here the main issues concern numerical stability and robustness. Also the algorithm introduced in [BGP] for the computation of the eigenvalues of a subclass of quasi-separable matrices will be closely investigated. Here the goal is to obtain an efficient polynomial rootfinder and investigate on a possible generalization of the class of matrices for which the QR iteration is closed.
-- Polynomial rootfinders will be analyzed also in terms of simultaneous and independent iterations based on the result of [HSS] trying to replace Newton's iteration with the modified Laguerre iteration and complementing it with some Gerschgorin like inclusion theorems for the approximations provided by the algorithm.
-- Bernstein polynomials and Bezier curves will be investigated as well. Here the main goal is to perform algebraic operations with polynomials represented in the Bernstein basis without changing to the power basis. In fact this transformation is severely ill conditioned. This goal requires that the algebraic operations which are usally performed in the power basis in terms of structured matrices (Bezout and Sylvester matrices) be performed in the Bernstein basis. Bernstein-Bezoutian metrices must be introduced and accurately analyzed. Moreover algorithms for the LU or QR decomposition of such matrices must be designed in such a way that either their numerical implementation is numerically stable or their symbolic implementation does not lead to a huge growth of the intermediate integers.
In this context, also the computation of the zeros of polynomials represented in the Bernstein basis plays an important role and will be investigated. Another related important topic is the application and integration of numerical tools, symbolic tools, computer algebra and projective geometry for solving computer aided geometric design problems [Gianni].

Concerning part 2) we continue our study of [BM], [BGM1],[BGM2],[BG2] on solving matrix equations. An important advance in this field was introduced in [HMR], [BM7] in the context of Markov chains by means of the "shift technique". Here we want to generalize this technique to general matrix equations of polynomial type.
-- We want to apply the cyclic reduction algorithm of G. Golub [BGN] adjusted to Markov chains by [BM3],[BM4] and analyzed in [BGM1],[BGM2] to 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, Laurent series inversion and Newton's iteration.
-- Any kind of matrix equations modeling queueing problems will be taken into account.
-- The problem of computing the p-th root of a matrix will be closely investigated by using the techniques of [M4] and of [Ia].

Concerning part 3, we focus our attention on properties of semi-separable and quasi-separable matrices with the aim of extending the algorithms of [BDG] and [BGP] for implementing the QR iteration in linear cost, to more general classes of matrices. This part is related to some polynomial computations of part 1). Concerning Toeplitz matrices and trigonometric algebras the interest is addressed to the analysis of algebraic multigrid methods for solving the related systems.

Concerning part 4), we continue the study of [D], [DFLZ], [DLZ] 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 adaptive methods where the approximation of the Hessian is performed at each step of the iteration will be studied. Algorithms for total least squares problems for structured matrices will be analyzed with applications to blind image deblurring.


Concerning part 5) of applications, we will apply our algorithms for the listed applications. In particular, the results of 1) concerning Bernstein-Bezout matrices, Bernstein polynomials and hybrid algorithms will be applied to solving CAGD problems. We will apply the results of 2) to solving queueing models where the solution of the associated matrix equations is the most expensive task, we will consider some queueing models which are somehow related to the algebraic Riccati equation. Concerning applications to Markov chains and to queueing models, we planned to organize in Pisa in June 2005 the fifth edition of the international conference "Matrix Analytic Methods in Stochastic Models (MAM5)" which will be supported by this project. We will apply the results of 4) to solving neural networks problems which model automatic learning and to blind image restoration.


Part of the research in 3) on semi-separable and quasi-separable matrices and on multigrid and on 4) on image deblurring is performed in collaboration with the Unit of Genova.

[BG2] D.Bini,L.Gemignani, Solving quadratic matrix equations and factoring polynomials: new fixed point iterations based on Schur complements of Toeplitz matrices. To appear in Numer. Lin. Alg. Appl. 2004.
[BGFM] D.Bini, G.Fiorentino,,L.Gemignani,B.Meini, Effective fast algorithms for polynomial spectral factorization , Numer. Algo., 2003.
[BGP] D.Bini,L.Gemignani,V.Pan $QR$-like algorithms for generalized semiseparable matrices T.R. 1470, Dept. of Math., University of Pisa, 2003.
[BGT] D.Bini L.Gemignani F.Tisseur. The Ehrlich-Aberth method for the nonsymmetric tridiagonal eigenvalue problem. TR 428, Univ. of Manchester, England 2003
[BM7] D.Bini,B.Meini, Non-Skip-Free M/G/1-type Markov chains and Laurent matrix power series, Proc. "Numerical Solution of Markov Chains", Urbana, September 2003.
[FGPT] E.Fortuna, P.Gianni, P.Parenti, C.Traverso, Algorithms to compute the topology of orientable real algebraic surfaces, J. Symb. Comp., 36,2003
[HMR] C.He, B.Meini, N.Rhee, A shifted cyclic reduction algorithm for QBDs, SIMAX,23 2001/02.
[HSS] J.Hubbard,D.Schleicher,S.Sutherland, How to find all roots of complex polynomials by Newton's method. Invent. Math. 146 (2001).
[ALM] G.Anastasi, L.Lenzini, B.Meini, Performance evaluation of a worst case model of the MetaRing MAC protocol with global fairness. Performance Evaluation, 29:127--151, 1997.



2.8 Mesi uomo complessivi dedicati al programma




Numero Mesi uomo
1° anno
Mesi uomo
2° anno
Totale mesi uomo
University Personnel  8  50  42  92 
Other University Personnel  4  35  31  66 
Work contract (research grants, free lance contracts)  0       
PHD Fellows & PHD Students  PHD Students  1  8  8  16 
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  1  4  6  10 
No cost Non University Personnel  1  5  5  10 
TOTALE     15  102  92  194 


.