MODELLO

nº	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

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

nº	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

nº	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					8	7

nº	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						8	8

nº	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	4	6

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

Gran parte di importanti problemi in matematica pura e applicata coinvolge matrici con struttura. L'analisi di proprieta' teoriche e computazionali di tali strutture e' un passo fondamentale nel disegno di algoritmi efficienti. Strutture di matrici sono mutuate dalle specifiche proprieta' del problema analizzato. Caratteristiche comuni a problemi in diverse aree, come la invarianza per traslazione, supporto compatto, separabilita' di variabili, si traducono in strutture che sono comuni a matrici incontrate in campi diversi quali matrici di Toeplitz, con struttura displacement (incluse matrici di Hankel, Bezout, Cauchy, Frobenius, Pick, Vandermonde), matrici a banda, semiseparabili, ad albero ecc. Infatti tali strutture si incontrano in problemi di statistica, probabilita', teoria delle code, computer algebra, CAGD, risoluzione numerica di equazioni differenziali e integrali, elaborazione di segnali e immagini.

L'interesse nelle strutture, gia' vivo negli anni '60 [GS] e '70 [Tr],[GoS] con i metodi diretti per sistemi di Toeplitz e con i risolutori veloci di Poisson [BGN], e' aumentato di importanza negli anni grazie al lavoro di diversi ricercatori. Piu' recentemente un forte interesse e' stato rivolto a diversi problemi di ricerca legati all'analisi di strutture e agli algoritmi. Una vasta letteratura si e' consolidata su diversi problemi correlati. Si sono sviluppati molti gruppi di ricerca e sono stati organizzati diversi congressi dedicati a queste tematiche e alle loro applicazioni.

I maggiori avanzamenti sono anche riportati in alcuni libri, alcuni dei quali sono pietre miliari in questo campo: i libri di Iohvidov [I] e di Heinig e Rost [HR] sulle strutture Toeplitz e Hankel, i libri di Bultheel e Van Barel [BvB] con le relazioni fra strutture e polinomi, il libro di Bini e Pan [BP] con algoritmi per matrici strutturate e polinomi, i libri di Grenander e Szego [GS] e Boettcher e Silbermann [BS] sulle proprieta' spettrali asintotiche delle Toeplitz, i libri di Gohberg, Goldberg and Kaashoek [GGK] e di Gohberg Lancaster and Rodman [GLR] su questioni piu' teoriche, il libro di Dewilde and van der Veen [DV] relativo a matrici semiseparabli, i libri editi da Kailath e Sayed [KS], da Bini, Tyrtyshnikov e Yalamov [BTY], e da Olshevsky [O] che contengono recenti avanzamenti nel campo, il lavoro di review di Chan e Ng [CN] sul precondizionamento di Toeplitz.

Riguardo a settori di ricerca piu' specifici di questa unita' si cita come base di partenza la teoria degli operatori displacement di Kailath et al [KS] e l'ampia letteratura che si e' originata, in particolare l'analisi degli operatori displacement e le formule di rappresentazione per matrici Toeplitz-like [DZ],[DF],[BZ],[Bo1] e i problemi relativi ad algebre di matrici strutturate [Bo],[BD],[BF]. Si citano le relazioni fra matrici con struttura e polinomi [BP], e l'ampia letteratura eistente fra cui [BiBo], [BGM1], [G1-G7]. Citiamo l'approccio metodologico di integrare algoritmi numerici e simbolici e i risultati scaturiti dal progetto europeo FRISCO (FRamework for the Integration of Symbolic and numeric Computing) che costituiscono una solida base della nostra ricerca. Si cita inoltre [CGTW] dove viene fatto uso di strumenti numerici e simbolici in computer algebra.
Si cita la teoria spettrale delle matrici di Toeplitz [BS], [GS] con i numerosi lavori sul precondizionamento e le applicazioni. Questi strumenti che formano la "Structured matrix technology" hanno ruolo fondamentale nella soluzione di molti problemi di interesse per l'Unita' fra cui:

-- Algoritmi per polinomi
-- Risoluzione numerica di sistemi tipo Toeplitz
-- Risoluzione numerica di catene di Markov e di problemi di code
-- Risoluzione di equazioni di matrici
-- Problemi di minimo e minimi quadrati
-- Intersezione di curve e supefici nel CAGD
-- analisi di strutture semiseparabili

per cui di recente si sono avuti avanzamenti importanti.

Algoritmi per polinomi sono correlati con matrici strutturate [BP]. Nei lavori [G1-G7],[BiBo],[BGM1] tali correlazioni sono evidenziate e utilizzate a fini computazionali. Problemi di localizzazione e approssimazione di zeri di polinomi sono risolti in termini di fattorizzazioni LU di matrici di Hankel e di Bezout su integral domains [G2-G4]. Questi metodi si basano su proprieta' dei complementi di Schur di matrici strutturate, usate in [BG1] per la realizzazione efficiente dell'algoritmo euclideo. Metodi per approssimare zeri di polinomi sono ottenuti interpretando l'algoritmo LR applicato a opportune matrici strutturate [G5-G7]. Risultati recenti riguardano il problema della fattorizzazione di polinomi e serie di potenze rispetto al cerchio unitario e il calcolo della fattorizzazione di Wiener-Hopf [BGM1],[BiBo] e le relative proprieta' di polinomi di Laurent, matrici bi-infinite di Toeplitz dove l'iterazione di Graeffe gioca un ruolo importante.

Un'altra serie di problemi in cui c'e' un solida base riguarda la teoria degli operatori displacement e il concetto di rango displacement approssimato[BM6]. Applicazioni a problemi di image restoration sono mostrati in [BM6] and in [BVC] per problemi di minimi quadrati per Toeplitz. Tecniche di precondizionamento hanno un'ampia base [KS],[KS1].

Molti problemi di teoria delle code modellati da catene di Markov [Ne], [LR] sono descritti da matrici di Toeplitz con strutture addizionali [BMR]. I risultati ottenuti in [BM1],[BM3],[BM4], basati su analisi di strutture hanno condotto a nuovi algoritmi veloci dotati di speedup di diverse centinaia. La Fast Ramaswami Formula [M1] permette una forte accelerazione nel calcolo di certe catene di Markov e si basa su Toeplitz computations e FFT. In [BM3] il metodo della riduzione ciclica e' applicato ed esteso alla soluzione di sistemi tridiagonali a blocchi di Toeplitz e a sistemi in forma di Hessenberg a blocchi generalizzata.

Un altro importante problema legato ai modelli di code e presente in molte applicazioni dove le strutture hanno un ruolo importante e' la risoluzione di equazioni matriciali [HK]. In [BM4],[M3],[BGM2] sono disegnati nuovi efficaci metodi; analisi specifiche e nuovi algoritmi sono proposti in [M4],[M3].

Recentemente applicazioni di analisi di strutture di matrici a problemi non strutturati di minimizzazione si sono mostrate molto efficienti [D],[DFLZ],[DLZ]. Applicazioni a reti neurali sono fatte in [BDFZ]. L'analisi di problemi ai minimi quadrati totali per matrici strutturate e' svolta in [MLV], [LMV], applicazioni di speech compression sono fatte in [LMV1].

Problemi di computer aided geometric design coinvolgono polinomi di Bernstein e curve di Bezier. Tali manipolazioni sono delicate dal punto di vista numerico per problemi di mal condizionamento. Per questo motivo l'integrazione di strumenti numerici e simbolici e' determinante. Oltre ai risultati del progetto FRISCO, importanti studi sono stati svolti da J. Winkler, piu' recentemente alcuni risultati sono stati ottenuti collegando polinomi di Bernstein e matrici di Bezout [BG1],[BGW].

Oltre ai classici risultati di Gohberg, Eidelman, Dewilde, Chandrasekaran, alcuni avazamenti sono stati recentemente ottenuti dal gruppo di Van Barel e dal gruppo della presente unita' nello studio di matrici semiseparabili. In particolare in [VBM1] sono mostrate interessanti transformazioni per similitudine in forma semiseparabile, in [BGT] le proprieta' di semiseparabilita' sono usate per disegnare algoritmi efficienti per autovalori di tridiagonali. In [BDG] si mostra che le iterazioni QR applicate a una matrice di Frobenius nxn lasciano inalterata la struttura semiseparabile e un algoritmo di costo O(n) puo' essere disegnato per il QR. Altri risultati relativi sono in [FMV], [FG1], [FG3].

Questa Unita' di ricerca ha antiche tradizioni nell'analisi di matrici strutturate e nel disegno di algoritmi per polinomi e matrici. L'esperienze dei membri dell'Unita' includono questioni teoriche e computazionali, disegno e analisi di algoritmi e software. Alcuni membri sono molto attivi nella risoluzione numerica di catene di Markov e di equazioni matriciali. Importanti risultati sono stati ottenuti nel progetto di cui questo documento e' proposta di continuazione.

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.

[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

MOTIVAZIONI:

Buona parte di problemi in matematica pura e applicata coinvolge matrici strutturate. L'analisi di proprieta' teoriche e computazionali di queste strutture e' un passo fondamentale nel disegno di algoritmi efficienti, specificamente disegnati per questi problemi, specialmente nei casi molto frequenti in cui metodi di risoluzione generale non possono essere applicati per il loro enorme costo computazionale dovuto alle grandi dimensioni del problema.

Matrici con struttura sono mutuate dalle specifiche proprieta' del problema. Caratteristiche comuni condivise da problemi in aree diverse come la shift invariance, il supporto compatto, la separabilita' delle variabili, si trasformano in strutture che sono comuni a matrici incontrate in campi diversi quali la struttura Toeplitz, le strutture displacement (incluse le matrici di Hankel, Cauchy, Bezout, Frobenius, Pick, Vandermonde), le matrici a banda, le semi-separabili le matrici ad albero ecc. In fatti queste strutture si incontrano in molti problemi diversi in statistica, probabilita', teoria delle code (inclusi problemi di telecomunicazioni, internet, analisi e valutazione di prestazioni, processi stocastici), calcoli con polinomi, algebra computazionale, CAGD, risoluzione numerica di equazioni differenziali e integrali, elaborazione di segnali e immagini digitali, giusto per citarne alcuni.

Spesso, le proprieta' del problema originale si trasformano in strutture che non appaiono evidenti, ad esempio strutture non lineari come la struttura displacement o la struttura semiseparabile dove le matrici appaiono come fossero non strutturate.

L'analisi di strutture e il conseguente disegno di algoritmi specifici per risolvere problemi in algebra lineare numerica ha ricevuto grande attenzione ed ha prodotto importanti avanzamenti nel disegno ed analisi di algoritmi. Da una parte sono stati raggiunti avanzamenti nello studio di proprieta' teoriche di classi di matrici con struttura, dall'altra, il disegno di algoritmi specifici ha permesso la risoluzione efficiente di importanti problemi in diversi campi applicativi. Giusto per citare un esempio, recenti algoritmi per risolvere equazioni matriciali o problemi di teoria delle code modellati da catene di Markov, basati su proprieta' di matrici di Toeplitz e su fattorizzazioni di Wiener-Hopf, si sono rivelati estremamente efficienti e hanno permesso di ridurre il tempo di cpu di un grande fattore mantenendo ottimo comportamento numerico [ALM]. In altri casi gli strumenti delle matrici con struttura hanno permesso di risolvere problemi non strutturati di minimizzazione in modo molto efficiente [D], [DFLZ], [DLZ].

In sintesi, le ricerche di questa unita' sono dettate dalle seguenti linee guida:

1- Le matrici con struttura giocano un ruolo fondamentale in gran parte di modelli matematici e nelle applicazioni.

2- L'analisi di strutture, oltre al suo interesse teorico, e' un passo fondamentale per disegnare algoritmi specifici di risoluzione. I risultati ottenuti in questo modo costituiscono un bagaglio di strumenti utili in molti contesti e costituisce la "structured matrix technology".

3- La structured matrix technology puo' essere usata per risolvere problemi di larga scala, di grande importanza applicativa, che difficilmente potrebbero essere risolti altrimenti con algoritmi generali. Allo stesso tempo, anche per la risoluzione di problemi non strutturati la tecnologia delle matrici strutturate puo' offrire importanti miglioramenti.

4- Il disegno e l'analisi di algoritmi ritagliati su specifiche strutture del problema non e' sufficiente. Cio' deve essere integrato con una rigorosa analisi di robustezza e stabilita' numerica. In certe situazioni dove il mal condizionamento e' una caratteristica intrinseca del problema, l'uso di tecniche di multiprecisione o l'uso di approcci ibridi numerico-simbolici diventano un passo obbligato.

LINEE GENERALI DI RICERCA

L'attivita' di ricerca e' condotta secondo le seguenti linee

-A- Condurre l'analisi di proprieta' algebriche, strutturali, analitiche spettrali e computazionali di classi di matrici strutturate che intervengono in problemi di matematica teorica e applicata (incluse matrici di Toeplitz, Hankel, Bezout, Cauchy, Frobenius, displacement, a banda, semiseparabili, ad albero, matrici con elementi scalari e a blocchi, multilivello).

-B- Sfruttare le proprieta' ottenute da questa analisi per generare metodologie per il disegno e l'analisi di algoritmi efficaci di risoluzione.

-C- Applicare gli algoritmi di risoluzione a problemi provenienti da certe applicazioni e dal calcolo scientifico su grande scala.

-D- Implementare in termini di software prototipo gli algoritmi ottenuti in questa ricerca e svolgere confronti computazionali e validazione numerica.

-E- Condurre una analisi dell'errore e della robustezza, teorica o sperimentale, in modo da selezionare algoritmi affidabili. Per problemi dotati di mal condizionamento intrinseco, disegnare nuove tecniche ibride basate su metodi numerici e simbolici, su multiprecisione e adattivita'.

ARGOMENTI SPECIFICI

Argomenti specifici di questa unita' sono

1- Polynomial computations: Analisi di fattorizzazioni di Wiener-Hopf (deboli) dove entrambi i fattori possono avere zeri unitari. Disegno di polynomial rootfinders basati sulle iterazioni QR applicate a matrici companion generalizzate che mantengano la struttura semiseparabile o quasiseparabile. Disegno di polynomial rootfinders basati sulle iterazioni di Newton, Laguerre, Halley con i teoremi di inclusione tipo Gerschgorin, e il concetto di pseudozero. Usare le rappresentazioni di polinomi nella base di Bernstein assieme alle loro controparti matriciali strutturate in modo da disegnare algoritmi per l'intersezione di curve di Bezier e superfici. Uso di algoritmi ibridi e di strumenti di geometria proiettiva, computer algebra ed analisi numerica per problemi di CAGD. Calcolo di autovalori di matrici tridiagonali [BGT].

2- Equazioni matriciali: lo scopo e' il disegno di algoritmi per risolvere equazioni di matrici basati su fattorizzazioni di Wiener-Hopf e su proprieta' di strutture. Casi di interesse sono la risoluzione dell'equazione algebrica di Riccati e il calcolo di radici p-esime di matrici.

3- Proprieta' strutturali e computazionali di matrici semiseparabili e quasiseparabili, matrici di Toeplitz, algebre trigonometriche. Fra gli obiettivi il disegno di algoritmi per il calcolo di autovalori e calcolo di zeri di polinomi (vedi parte1).

4- Problemi di minimizzazione: disegno ed analisi di algoritmi quasi-Newton per problemi di minimizzazione dove l'Hessiano e' approssimato con matrici strutturate.

5- Applicazione della parte 1) alla risoluzione di problemi di CAGD come l'intersezione di curve e superfici assegnate parametricamente o implicitamente. Applicazione della parte 2) alla risoluzione di catene di Markov che si incontrano in modelli di code. Applicazione della parte 3) al disegno di algoritmi per il calcolo di zeri di polinomi. Applicazione della parte 4) alla risoluzione di problemi di reti neurali.

COMPITI PRINCIPALI
Per il punto 1) si desidera generalizzare ed estendere le tecniche di shift introdotte in [MR], [BM7] per accelerare la convergenza nella risoluzione di certe equazioni incontrate nelle catene di Markov, in modo da poter trattare casi piu' generali in cui i fattori di Wiener Hopf possono avere zeri di modulo 1.
-- Si desidera anche investigare piu' da vicino l'algoritmo di [BDG] dove l'iterazione QR applicata a matrici nxn di Frobenius e' eseguita con costo O(n) per passo. Qui i problemi piu' rilevanti sono la stabilita' numerica e la robustezza. Anche gli algoritmi di [BGP] per il calcolo degli autovalori di una sottoclasse di matrici quasiseparabili saranno studiati piu' attentamente. Qui lo scopo e' individuare risolutori polinomiali efficienti e studiare possibili generalizzazioni di classi di matrici chiuse sotto l'iterazione QR.
-- Polynomial rootfinders saranno analizzati anche in termini di iterazioni simultanee indipendenti secondo i risultati di [HSS] cercando di sostituire l'iterazione di Newton con iterazioni piu' veloci complementate con risultati di inclusione tipo Gerschgorin per le approssimazioni fornite dall'algoritmo.
-- Polinomi di Bernstein e curve di Bezier saranno pure studiate. Qui lo scopo consiste nell'eseguire operazioni algebriche su polinomi rappresentati nella base di Bernstein senza cambiare rappresentazione nella base delle potenze. Infatti tale trasformazione e' fortemente mal condizionata. Questo scopo richiede che le operazioni algebriche che sono solitamente svolte nella base delle potenze in termini di matrici strutturate (matrici di Bezout e Sylvester) siano svolte nella base di Bernstein. Matrici di Bernstein-Bezout devono essere introdotte e studiate. Occorre inoltre sviluppare algoritmi per le fattorizzazioni LU e QR di tali matrici in modo che o la loro implementazione sia numericamente stabile o che la loro implementazione simbolica non conduca a forte crescita degli interi generati nei passi intermedi. In questo contesto anche il calcolo degli zeri di polinomi rappresentati nella base di Bernstein ha un ruolo importante e sara' studiato. Un altro argomento correlato di interesse e' l'applicazione e l'integrazione di strumenti simbolici e numerici, di algebra computazionale e geometria proiettiva per risolvere problemi di CAGD [FGPT].

Per il punto 2) si continua lo studio avviato in [BM], [BGM1], [BGM2], [BG2] sulla risoluzione di equazioni matriciali. Importanti avanzamenti in questo campo sono stati raggiunti in [HMR],[BM7] nel contesto delle catene di Markov per mezzo della tecnica di shift. Si intende estendere questa tecnica a equazioni matriciali di tipo piu' generale.
-- Si intende applicare l'algoritmo della riduzione ciclica di G. Golub, adattato a catene di Markov da [BM3],[BM4] e analizzato in [BGM1],[BGM2] per risolvere equazioni algebriche di Riccati. Anche il calcolo della radice principale p-esima di una matrice sara' affrontato in termini di inversione di serie di Laurent, fattorizzazioni di Wiener-Hopf, e iterazioni di Newton, dove verranno utilizzati anche i metodi di [M4] e [Ia].
-- Altri tipi di equazioni provenienti da catene di Markov che modellano problemi di code saranno considerate.

Per il punto 3) poniamo l'attenzione sulle proprieta' delle matrici semiseparabili e quasiseparabili con l'intento di estendere gli algoritmi di [BDG], [BGP] per implementare l'iterazione QR a costo lineare a classi piu' generali di matrici. Per quanto riguarda matrici di Toeplitz e algebre trigonometriche l'interesse e' rivolto all'analisi del metodo multigrid algebrico.

Per la parte 4) si continua lo studio di [D], [DFLZ], [DLZ] con l'analisi di condizioni sufficienti che garantiscono la convergenza dei metodi di minimizzazione quasi-Newton dove la matrice Hessiana e' sostituita da matrici nell'algebra di Hartley [BF] o con altre matrici strutturate. Le condizioni riguarderanno la limitatezza di certi operatori che intervengono nel processo di minimizzazione eil condizionamento delle matrici strutturate. Verranno studiati anche metodi adattivi dove l'Hessiano e' aggiornato ad ogni passo. Un'altro problema trattato sara' il disegno di algoritmi veloci per i "total least squares" per matrici con struttura e applicazioni a problemi di blind image deblurring.

Per la parte 5) rivolgeremo gli algoritmi individuati alle applicazioni di principale interesse. In particolare i risultati di 1) sulle matrici di Bernstein-Bezout, sui polinomi di Bernstein e sugli algoritmi ibridi saranno applicati per risolvere problemi di CAGD. Si applicheranno i risultati di 2) per risolvere problemi di code dove la risoluzione di equazioni matriciali diventa il compito computazionalmente piu' pesante; considereremo modelli di code correlati all'equazione algebrica di Riccati. Per quanto riguarda le applicazioni alle catene di Markov e ai modelli di code, programmiamo di organizzare a Pisa nel Giugno 2005 la quinta edizione del congresso internazionale "Matrix Analytic Methods and Stochastic Models (MAM5)" che verra' finanziato dal presente progetto. Si intende inoltre completare la stesura del libro "Numerical Solution of Structured Markov Chains" per la Oxford University Press. Si applicano i risultati di 4) alla risoluzione di problemi di reti neurali che modellizzano problemi di apprendimento e a problemi di blind image deblurring.

Parte della ricerca ai punti 3) e 4) e' svolta in collaborazione con l'Unita' di 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.

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.

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"

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)

		Numero	Mesi uomo 1° anno	Mesi uomo 2° anno	Totale mesi uomo
Personale universitario dell'Università sede dell'Unità di Ricerca		8	50	42	92
Personale universitario di altre Università		4	35	31	66
Titolari di assegni di ricerca		0
Titolari di borse	Dottorato	1	8	8	16
	Post-dottorato	0
	Scuola di Specializzazione	0
Personale a contratto	Assegnisti	0
	Borsisti	0
	Dottorandi	0
	Altre tipologie	1	4	6	10
Personale extrauniversitario		1	5	5	10
TOTALE		15	102	92	194

		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

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)