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
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
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 |
Altro personale
nº |
Cognome |
Nome |
Dipartimento |
Qualifica |
Mesi Uomo |
1° anno |
2° anno |
1. |
Fiorentino |
Giuseppe |
Dip. MATEMATICA |
Tecnico
Laureato |
3 |
3 |
|
TOTALE |
|
|
|
3 |
3 |
1.7.2 Personale universitario di altre
Università
Personale docente
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 |
Altro personale
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 |
1.7.3 Titolari di assegni di ricerca
Nessuno
1.7.4 Titolari di borse
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 |
1.7.5 Personale a contratto da destinare a questo
specifico programma
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 |
|
1.7.6 Personale extrauniversitario indipendente o
dipendente da altri Enti
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 |
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 |
.