MINISTERO DELL'ISTRUZIONE, DELL'UNIVERSITÀ E DELLA RICERCA
DIPARTIMENTO PER LA PROGRAMMAZIONE IL COORDINAMENTO E GLI AFFARI ECONOMICI - SAUS
PROGRAMMI DI RICERCA SCIENTIFICA DI RILEVANTE INTERESSE NAZIO NALE
RICHIESTA DI COFINANZIAMENTO
(DM n. 20 del 19 febbraio 2002)
PROGETTO DI UNA UNITÀ DI RICERCA - MODELLO B
Anno 2002 - prot. 2002014121_001


Parte: I
1.1 Programma di Ricerca di tipo:interuniversitario

Area Scientifico Disciplinare: Scienze Matematiche


1.2 Durata del Programma di Ricerca:24 mesi

1.3 Coordinatore Scientifico del Programma di Ricerca: BINI DARIO ANDREA, professore ordinario, Università di PISA, Facoltà di SCIENZE MATEMATICHE FISICHE e NATURALI , Dipartimento di MATEMATICA "Leonida Tonelli", (MAT/08) bini@dm.unipi.it, tel: 050-2213279, fax: 050-2213224


1.4 Responsabile Scientifico dell'Unità di Ricerca: BINI DARIO ANDREA, professore ordinario, Università di PISA, Facoltà di SCIENZE MATEMATICHE FISICHE e NATURALI , Dipartimento di MATEMATICA "Leonida Tonelli", (MAT/08) bini@dm.unipi.it


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

Dario Bini, professore ordinario di analisi numerica dal 1986, e' autore di piu' di 70 pubblicazioni scientifiche e di diversi libri di analisi numerica e matematica computazionale. La sua esperienza nel settore dell'analisi di matrici con struttura, disegno di algoritmi numerici e di polynomial computations e' di oltre 20 anni. E' membro dell'editorial board della rivista Calcolo, ha organizzato congressi internazionali su tematiche di algebra lineare numerica e su matrici con struttura. E' stato editor di raccolte di articoli su tematiche del settore. E' stato relatore di numerose tesi di dottorato. I suoi principali interessi sono attualmente lo studio delle matrici di Toeplitz e gli operatori di dislocamento, lo studio dei problemi computazionali relativi al trattamento dei polinomi, lo studio di metodi per la risoluzione numerica di catene di Markov e risoluzione di equazioni di matrici.


1.6 Pubblicazioni scientifiche più significative del Responsabile Scientifico dell'Unità di Ricerca
  1. BINI D.A., GEMIGNANI L., MEINI B. (2001). Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations. NUMERISCHE MATHEMATIK. vol. 89 (2001), no. 1, pp. 49--82.
  2. 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.
  3. 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.
  4. BINI D.A., B. MEINI. (1998). Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: application to queueing problems. LINEAR ALGEBRA AND ITS APPLICATIONS. vol. 272, pp. 1-16.
  5. BINI D.A., B. MEINI. (1996). On the solution of a nonlinear matrix equation arising in queueing problems. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. vol. 17, pp. 906-926.

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

1.7.1 Personale universitario dell'Università sede dell'Unità di Ricerca
Cognome Nome Dipart./Istituto Qualifica Settore
scient.
Mesi
uomo
2002 2003
Personale docente:
1  BINI  DARIO ANDREA  MATEMATICA "Leonida Tonelli"  Prof. ordinario  MAT/08  9
(ore: 1233)
 7
(ore: 959)
2  GEMIGNANI  LUCA  MATEMATICA "Leonida Tonelli"  Prof. associato  MAT/08  9
(ore: 1233)
 7
(ore: 959)
3  MEINI  BEATRICE  MATEMATICA "Leonida Tonelli"  Ricercatore  MAT/08  9
(ore: 1233)
 7
(ore: 959)
4  STEFFE'  SERGIO  MATEMATICA "Leonida Tonelli"  Prof. associato  MAT/08  11
(ore: 1507)
 11
(ore: 1507)
Altro personale:
5  FIORENTINO  GIUSEPPE  MATEMATICA "Leonida Tonelli"  tecnico laureato 8^ livello    3
(ore: 411)
 3
(ore: 411)

1.7.2 Personale universitario di altre Università
Cognome Nome Università Dipart./Istituto Qualifica Settore
scient.
Mesi
uomo
2002 2003
Personale docente:
1  DI FIORE  CARMINE  ROMA "Tor Vergata"  MATEMATICA  Ricercatore  MAT/08  11
(ore: 1507)
 7
(ore: 959)
2  FANELLI  STEFANO  ROMA "Tor Vergata"  MATEMATICA  Prof. associato  MAT/08  11
(ore: 1507)
 7
(ore: 959)
3  ZELLINI  PAOLO  ROMA "Tor Vergata"  MATEMATICA  Prof. ordinario  MAT/08  11
(ore: 1507)
 7
(ore: 959)
Altro personale:

1.7.3 Titolari di assegni di ricerca
Cognome Nome Dipart./Istituto Anno del titolo Mesi
uomo
2002 2003
 

1.7.4 Titolari di borse per Dottorati di Ricerca e ex L. 398/89 art.4 (post-dottorato e specializzazione)
Cognome Nome Dipart./Istituto Anno del titolo Mesi uomo
1. BACCIARDI  ALESSIO  INFORMATICA  2003  11 
(ore: 1507) 

1.7.5 Personale a contratto da destinare a questo specifico programma
Qualifica Costo previsto Mesi uomo
1. Laureato  18000  18 
(ore: 2475) 

1.7.6 Personale extrauniversitario dipendente da altri Enti
Cognome Nome Ente Qualifica Mesi uomo
1. MASTRONARDI  NICOLA  IRMA, CNR, Bari  Primo Ricercatore  16 
(ore: 2200) 


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

Analisi di matrici con struttura di dislocamento e applicazioni


2.2 Settori scientifico-disciplinari interessati dal Programma di Ricerca
  • MAT/08 - ANALISI NUMERICA

2.3 Parole chiave

MATRICI DI TOEPLITZ ; RANGO DI DISLOCAMENTO ; MATRICI CON STRUTTURA ; METODI NUMERICI PER CATENE DI MARKOV ; CALCOLO POLINOMIALE ; EQUAZIONI MATRICIALI


2.4 Base di partenza scientifica nazionale o internazionale

Gran parte di importanti problemi di matematica pura e applicata conduce alla risoluzione di problemi di algebra lineare numerica in cui intervengono matrici dotate di particolari strutture. Lo studio di queste strutture e' un passo fondamentale per costruire algoritmi di risoluzione dotati di grande efficienza.
Una delle strutture piu' spesso incontrate e' la struttura Toeplitz. Una matrice e' di Toeplitz se i suoi elementi sono funzione della differenza dei loro indici. La struttura Toeplitz riflette le proprieta' di invarianza sotto traslazione condivisa da enti matematici di varia natura che intervengono nel modello. Matrici di Toeplitz sono un caso particolare della piu' ampia classe di matrici con struttura di dislocamento. Spesso si incontrano strutture correlate, tipo matrici di Pick, Cauchy, Frobenius ecc, o matrici definite ricorsivamente, quali le matrici ad albero, che riflettono la specificita' del problema.
Matrici con struttura si incontrano su piu' livelli (ad esempio matrici di Toeplitz a blocchi con blocchi di Toeplitz) quando si modellizzano problemi in piu' dimensioni.
L'interesse alle problematiche legate alle matrici con struttura, gia' presente negli anni '60 [GS] e '70 con i lavori di Trench
[Tr] e di Gohberg-Semencul [GoS] sui metodi diretti per matrici di Toeplitz e implicitamente con i metodi per la risoluzione del problema discreto di Poisson sul rettangolo, si e' via via accresciuto negli anni successivi grazie alle ricerche di alcuni gruppi scientifici. Negli ultimi anni un forte interesse a livello internazionale si e' coagulato attorno alle problematiche legate all'analisi di strutture di matrici e un ampia letteratura si e' consolidata sui problemi matematici correlati. Diversi gruppi di ricerca internazionali si sono sviluppati attorno a questi problemi. Numerosi congressi specifici, o speciali sessioni in congressi generali si sono tenuti negli ultimi anni e sono programmati per gli anni a venire. Per poter meglio tracciare in modo sintetico gli avanzamenti raggiunti negli ultimi anni e' importante citare alcuni dei principali libri prodotti nel settore. In particolare si fa riferimento ai testi di Iohvidov [I] e di Heinig e Rost [HR] sull'analisi di strutture Toeplitz e Hankel, al libro di Bultheel e Van Barel [BvB] per quello che riguarda la relazione fra strutture e approssimazione di funzioni, al libro di Bini e Pan [BP] sulle relazioni fra "structured matrix computations" e "polynomial computations" e sugli aspetti piu' computazionali, al libro di Grenander e Szego [GS] e di Boettcher e Silbermann [BS] sulle proprieta' spettrali asintotiche di matrici Toeplitz, ai libri di Gohberg, Goldberg e Kaashoek [GGK], e di Gohberg, Lancaster e Rodman [GLR], ai libri editi da Kailath e Sayed [KS], da Bini, Tyrtyshnikov e Yalamov [BTY], da V. Olshevsky [O] che raccolgono i risultati piu' avanzati ottenuti nel settore e al lavoro di rassegna di Chan e Ng sulla teoria del precondizionamento di Toepliz.
 

Per quanto riguarda piu' specificamente gli argomenti di interesse dei ricercatori della presente unita' operativa si cita come base di partenza la teoria del rango di dislocamento sviluppata da Kailath et al [KS] e le formule di inversione, in particolare le formule di rappresentazione delle matrici Toeplitz-like[Bo1],[BZ],[DF],[DZ], i problemi connessi all'analisi delle proprieta' di algebre di matrici strutturate [BB], [Bo2], [Bo3], [BD], [BF]. Rilevante e' l'uso di questi strumenti per la risoluzione di numerosi problemi di interesse per la presente unita' operativa quali
 

-- Polynomial computations
-- Fattorizzazione e inversione di matrici di Toeplitz finite e infinite
-- Equazioni matriciali
-- Problemi di teoria delle code
-- Problemi di minimo e di minimi quadrati

per i quali recentemente si sono avuti degli avanzamenti notevoli.
Infatti operazioni con polinomi sono ricondotte a operazioni con matrici struttrate [BP] ed e' importante citare gli avanzamenti raggiunti in questa direzione in [G1-7], [BGM], [BGM1], [BG1], [BP1], [B], in particolare sul disegno di algoritmi veloci per la fattorizzazione di polinomi e serie di potenze. Problemi di approssimazione e localizzazione degli zeri di polinomi univariati e bivariati vengono risolti mediante metodi di fattorizzazione di matrici di Hankel e/o Bezout sia su campi che su domini di integrita'. Alternativamente metodi per l'approssimazione di zeri di polinomi univariati sono ottenuti reinterpretando in chiave polinomiale il classico algoritmo LR applicato a opportune matrici strutturate [G5].
 

Relativamente al calcolo delle fattorizzazioni di Wiener-Hopf, ai polinomi di Laurent e all'inversione di matrici bi-infinite di Toeplitz i risultati piu' recenti sono raccolti in [BGM1] dove il metodo di Graeffe viene usato per invertire polinomi di Laurent e in [BiBo] dove viene applicata la teoria delle sezioni finite. Un altro insieme di problemi per cui esiste una solida base di partenza riguarda la teoria del rango di dislocamento e il concetto recentemente introdotto in [BM5], [BM6] del rango approssimato di dislocamento. Usando questo nuovo strumento e' infatti possibile disegnare nuovi algoritmi per la risoluzione di sistemi con matrici di Toeplitz multilivello mediante una opportuna implementazione della riduzione ciclica e mediante l'uso dell'iterazione di Newton proiettata su spazi di matrici a rango di dislocamento contenuto. Queste nuove metodologie sono state applicate al problema del restauro di immagini [BFFM].
 

Le proprieta' delle matrici con struttura costituiscono una base importante nella risoluzione di equazioni matriciali non lineari. In [BM4], [M2], vengono forniti metodi di risoluzione molto efficienti basati sulle proprieta' delle matrici strutturate; in [FM1],[FM2], si utilizzano iterazioni funzionali. Analisi specifiche e nuovi metodi di risoluzione sono studiati in [M2],[M3].
 

Molti problemi di teoria delle code in cui intervengono catene di Markov del tipo MG1, GM1, QBD, BMAP, TREE [Ne], [LR] sono descritte da matrici di tipo Toeplitz spesso dotate di ulteriori strutture [BMC], [BMR]. I risultati ottenuti in [BM1], [BM2], [BM3], [BM4], basati sull'analisi delle strutture, hanno permesso di costruire algoritmi di risoluzione molto piu' veloci degli algoritmi al momento disponibili in letteratura con speedups di alcune centinaia. Ad esempio in [M1] viene introdotta la Fast Ramaswami Formula che permette, attraverso l'uso delle matrici di Toeplitz e la FFT, di accelerare enormemente il calcolo di certi parametri relativi al modello di code. In [BM3] viene generalizzato l'algoritmo di riduzione ciclica alla risoluzione di sistemi a banda di Toeplitz o in forma di Hessenberg con elementi scalari o a blocchi. Altri metodi basati su metodologie divide-et-impera sono presentati in [BM2].
 

Uso di strutture in problemi di minimo e' fatto in [DFFZ], problemi di minimi quadrati totali con struttura sono trattati in [MLV],[LMV].
 

L'Unita' operativa ha una lunga tradizione di ricerca nel settore delle matrici con struttura e nel disegno di algoritmi efficienti per computazioni con matrici e polinomi. Ha competenze sia a livello teorico che di analisi e implementazione di algoritmi. Alcuni elementi sono particolarmente attivi nell'analisi di metodi numerici per catene di Markov.


2.4.a Riferimenti bibliografici
[B] D.Bini, Using FFT-based techniques in polynomial and matrix computations: recent advances and applications. Numer.Funct.Anal.Optim. 21(2000),47-66.
[BB] R.Bevilacqua, E.Bozzo, On algebras of symmetric Loewner matrices. Lin.Alg.Appl. 248(1996),241-251.
[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),312-326.
[BF] D.Bini,P.Favati, On a matrix algebra related to the discrete Hartley transform. SIMAX 14(1993),500-507.
[BFi] D.A.Bini,G.Fiorentino, Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numer. Algo. 23(2000),127-173.
[BFFM] D.Bini,A.Farusi,G.Fiorentino,B.Meini, On the regularized solution of block banded block Toeplitz systems, Proc. of SPIE, Vol. 4116, F. T. Luk Editor, 135-146, 2000.
[BG1] D.Bini,L.Gemignani, Fast fraction-free triangularization of Bezoutians with applications to sub-resultant chain computation. Lin.Alg.Appl. 284(1998).
[BGHN] A.Bultheel, et Al, Orthogonal Rational Functions, Cambridge Univ. Press, 1999.
[BGM] D.Bini,L.Gemignani,B.Meini, Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations, Numer. Math.89,2001.
[BGM1] D.Bini,L.Gemignani,B.Meini, Computations with infinite Toeplitz matrices and polynomials, Lin.Alg.Appl., 343,2002.
[BiBo] D.Bini,A.Boettcher, Polynomial factorization through Toeplitz matrix computations. T.R. 1326, 2001 Dip.to di Matematica, Univ. Pisa.
[BM1] D.Bini,B.Meini, Effective methods for solving banded Toeplitz systems. SIMAX. 20(1999),700-719.
[BM2] D.Bini,B.Meini, Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: application to queueing problems. Lin.Alg.Appl. 272(1998), 1-16.
[BM3] D.Bini,B.Meini, Improved cyclic reduction for solving queueing problems. Numer.Algo. 15(1997),57-74.
[BM4] D.Bini,B.Meini, On the solution of a nonlinear matrix equation arising in queueing problems. SIMAX 17 (1996),906-926.
[BM5] D.Bini,B.Meini, Solving Block banded block Toeplitz systems with structured blocks: algorithms and applications, in Structured Matrices: Recent Developments in Theory and Computation, D. Bini, E. Tyrtyshnikov and P. Yalamov Editors, Nova Science Inc., New York, 2001.
[BM6] D.Bini,B.Meini, Approximate displacement rank and applications, Contemporary Mathematics, 281, AMS 2002.
[BMC] D.Bini,B.Meini, S.Chakravarthy, Control of the BMAP/PH/1/K queue with group services, in Advances in Algorithmic Methods for Stochastic Models, G. Latouche and P. Taylor eds., Notable Publications, 2000, 57-72.
[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, Proc. G. Latouche and P. Taylor eds., Notable Publications, 2000, 73-86.
[Bo1] E.Bozzo, A note on matrix displacement representation. Int. Eq. Op. Th. 29 (1997)368-372.
[Bo2] E.Bozzo, Algebras in matrix spaces with displacement structure. Lin. and Mult.Alg. 42(1997),23-41.
[Bo3] E.Bozzo, Algebras of higher dimension for displacement decompositions and computations with Toeplitz plus Hankel matrices. Lin.Alg.Appl. 230(1995),127-150.
[BP] D.Bini,V.Pan. Polynomial and matrix computations. Vol. 1. Birkhäuser Boston, MA, 1994
[BP1] D.Bini,V.Pan, Graeffe's, Chebyshev-like, and Cardinal's processes for splitting a polynomial into factors. J. Complexity 12 (1996),492-511.
[BP2] D.Bini,V.Pan, Improved parallel computations with Toeplitz-like and Hankel-like matrices. Lin.Alg.Appl. 188/189 (1993), 3-29.
[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.Van Barel, 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), 5-41.
[CN] R.Chan, M.Ng, Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38(1996), 427-482
[Da] K.Datta, Numerical Linear Algebra and Applications. 1995, Brooks/Cole Publ.
[DF] C.DiFiore, Matrix algebras in displacement decomposition. SIMAX 2000.
[DFFZ] C.DiFiore,S.Fanelli,P.Zellini, Matrix algebras in quasi-Newtonian algorithms for optimal learning in multi-layer perceptrons. Proc. ICONIP '99, Dunedin, New Zeeland, 1999.
[DZ]C.DiFiore,P.Zellini, Matrix displacement decomposition and applications to Toeplitz linear systems. Lin.Alg.Appl. 268(1998)
[FS] G.Fiorentino,S.Serra, Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions SIAM J. Sci Comp 17(1996).
[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),221-238.
[G2] L.Gemignani, Computing a factor of a polynomial by means of multishift LR algorithms. SIMAX 19(1998), 161-181
[G3] L.Gemignani, Schur complements of Bezoutians and the inversion of block Hankel and block Toeplitz matrices. Lin.Alg.Appl. 253(1997),39-59.
[G4] L.Gemignani, Computationally efficient applications of the Euclidean algorithm to zero location. Lin.Alg.Appl. 249(1996),79-91.
[G5] L.Gemignani, Polynomial root computation by means of the LR algorithm. BIT 37(1997),333-345.
[G6] L.Gemignani, Computing a factor of a polynomial by means of multishift LR algorithms. SIMAX 19(1998),161-181
[G7] L.Gemignani, Computing a Hurwitz factorization of a polynomial. J. Comput.Appl.Math. 126(2000),369-380.
[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), 201-223.
[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.
[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. Van Huffel, Fast algorithm for Solving the Hankel/Toeplitz Structured Total Least Squares Problem, Numer. Algo, 23,371-392,2000.
[M1] B.Meini An improved FFT-based version of Ramaswami's formula. Comm. Statist. Stoch. Models, 13:223-238, 1997.
[M2] B.Meini, Matrix equations and structures: efficient solution of special discrete algebraic Riccati equations, Proc, of the WLSSC00, Bulgaria, 2000.
[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.
[MLV] N.Mastronardi,P.Lemmerling,S. Van Huffel, Fast structured total least squares algorithm for solving the basic deconvolution problem, SIMAX 22,533-553,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, Contemporary Mathematics 281, 2001.
[Tr] W.Trench. An algorithm for the inversion of finite Toeplitz matrices. J. Soc. Indust. Appl. Math. 12 1964 515-522.

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

L'analisi e la sintesi di algoritmi numerici per il trattamento di matrici con struttura e' parte integrante del calcolo scientifico su grande scala. Gli avanzamenti raggiunti nella analisi e sintesi di algoritmi basati sulle strutture sono stati fondamentali nella risoluzione di molti problemi applicativi.
Oltre agli interessanti aspetti teorici presenti nella analisi astratta di strutture e' rivolto anche un forte interesse algoritmico, computazionale e applicativo nelle ricerche della presente unita'. Infatti matrici con struttura intervengono in importanti problemi quali l'analisi di modelli di teoria delle code (problemi di reti, telecomunicazioni, performance analysis, processi stocastici [LR]), risoluzione numerica di equazioni differenziali e integrali, filtraggio di segnali, restauro di immagini, problemi inversi e di acustica, problemi di interpolazione, analisi di serie temporali, problemi di algebra computazionale, risoluzione di equazioni matriciali, giusto per citare alcuni esempi (si veda [BP], [BTY], [BvB], [KS], [Ne], [LR],[Da]).
Gli obiettivi principali di questa unita' di ricerca si articolano nelle seguenti tre linee generali:

-- Condurre l'analisi di proprieta' strutturali, algebriche, analitiche, spettrali e computazionali di matrici Toeplitz-like finite, semi-infinite e bi-infinite, di matrici con struttura di dislocamento e semi separabili che intervengono in problemi di matematica teorica e applicata (e che includono matrici di Hankel, Cauchy-like, matrici multilivello, a elementi scalari o a blocchi, matrici definite ricorsivamente);

-- utilizzare di tali proprieta' al fine di individuare metodologie numeriche generali per il disegno e l'analisi di algoritmi efficienti di risoluzione con particolare attenzione rivolta a problemi di natura applicativa e di calcolo scientifico su grande scala;

-- realizzare un'implementazione prototipale degli algoritmi individuati e la loro validazione sperimentale.

In particolare, si intendono individuare, studiare e confrontare algoritmi efficienti per le seguenti classi di problemi:
 

1) Polynomial Computations. Si intendono proseguire le ricerche presenti in [BGM], [BGM1], in particolare sul calcolo di fattorizzazioni di Wiener-Hopf di polinomi di Laurent a coefficienti scalari e matriciali; calcolo dei coefficienti della serie di Laurent (se esiste), reciproco di un polinomio di Laurent assegnato, sia nel caso di coefficienti scalari che matriciali; applicazione alla fattorizzazione di polinomi rispetto alla circonferenza unitaria e rispetto all'asse immaginario; calcolo del reciproco di polinomi multivariati (come serie di Laurent se esiste). Si intendono approfondire le relazioni fra il metodo di Graeffe per polinomi e il metodo della riduzione ciclica (come elaborato in [BGM1], [BGM], [BM3]), e le possibili estensioni a matrix polynomials. Si vuole approfondire l'analisi dei metodi di evaluation/interpolation nella linea di [BiBo] e del metodo di Wilson. Si vogliono approfondire le relazioni fra il problema della fattorizzazione di polinomi e la risoluzione di certe equazioni matriciali (si veda il successivo punto 3) e analizzare metodi basati sulle iterazioni funzionali. Si intendono applicare le tecniche di fattorizzazione di polinomi scalari e/o matriciali alla risoluzione di sistemi lineari con matrici Sylvester-like scalari e/o a blocchi. Si intendono quindi sviluppare metodi per il calcolo di fattorizzazioni QR di matrici Cauchy-like evidenziandone le connessioni con problemi spettrali diretti e inversi per matrici semiseparabili e con la costruzione di insiemi di funzioni razionali ortogonali (parte di questa ricerca e' svolta in collaborazione con l'Unita' 2). Tali funzioni intervengono in problemi generalizzati dei momenti e di interpolazione razionale [BGHN].
 

2) Fattorizzazione di matrici di Toeplitz a elementi scalari e a blocchi. Si intendono applicare i risultati del punto 1 e di [BGM], [BGM1], [Goodman et al. Adv. Comput. Math. 7 (1997)], all'inversione di matrici semi-infinite e bi-infinite di Toeplitz a elementi scalari e a blocchi, mono e multi-livello (in collaborazione con l'Unita' 3). Si intendono quindi proseguire le ricerche di [G7] per l'individuazione e l'analisi di metodi efficienti per la fattorizzazione di matrici Toeplitz-like con elementi su anelli con possibili applicazioni a problemi di computer graphics (intersezioni di curve e superfici).
 

3) Risoluzione di equazioni matriciali. Si considerano equazioni di tipo Riccati (XAX+BX+XC+D=0), di tipo polinomiale (A_0+A_1X+...+A_nX^n=0), e definite da serie di potenze (A_0+A_1X+A_2X^2+...=0), nella linea dei lavori [BM4], [M2], [HK]; si intendono sviluppare tecniche di deflazione per accelerare la convergenza di schemi noti e disegnare nuovi metodi basati sull'uso delle proprieta' delle matrici di Frobenius. Una certa attenzione verra' rivolta alla riduzione di Ramaswami [BMR] per ridurre equazioni relative a serie di potenze ad equazioni polinomiali. Si intende inoltre approfondire il legame fra il problema della risoluzione di equazioni matriciali e la fattorizzazione di polinomi e di serie di potenze di matrici.
 

4) Risoluzione di sistemi lineari finiti con struttura. Si intendono analizzare le proprieta' delle inverse di matrici mono e multilivello di Toeplitz bi-infinite da poter usare come precondizionatori per tecniche di gradiente coniugato (in collaborazione con l'Unita' 3). Si intendono analizzare metodi multigrid per matrici di Toeplitz mono e multilivello nella linea di [FS] (ricerca da svolgere in collaborazione con l'Unita' 2). Si intende approfondire l'analisi e l'utilizzazione delle proprieta' del rango di dislocamento approssimato [BM6], in particolare in relazione al calcolo dell'inversa di matrici Toeplitz-like con l'iterazione di Newton. Si intendono analizzare algoritmi veloci e stabili per il calcolo della decomposizione spettrale di matrici diagonali piu' semiseparabili e per la risoluzione di sistemi lineari dove la matrice dei coefficienti ha tale struttura.
 

5) Problemi di teoria delle code. Si intende approfondire l'analisi di strutture di matrici nei modelli QBD, BMAP, PH1, NonSkipFree e Tree (vedi [BMC], [BMR], [Ne], [LR]) in cui intervengono strutture su piu' livelli (ad esempio, struttura esterna di Toeplitz e interna di Frobenius o di Kronecker) per individuare metodi di risoluzione specifici piu' efficienti nella linea dei lavori [BCM], [BMR]. Inoltre, in connessione col precedente punto 3 si intendono studiare specifiche equazioni matriciali che intervengono nei modelli di code definiti da strutture ricorsive quali le Tree structures [LR].
 

6) Problemi di minimo non vincolato, minimi quadrati totali e reti neurali. Algebre di matrici con struttura possono essere impiegate nelle formule di aggiornamento dell'Hessiano in metodi di tipo quasi-Newton per la minimizzazione non vincolata di funzioni non lineari generali di n variabili [DFFZ]. Si intende proseguire lo studio della nuova classe di metodi di minimizzazione quasi-newtoniani, denominati LQN e introdotti in [DFFZ], basati sull'uso di trasformate veloci e di complessita' O(nlogn) per passo. Vi sono diversi problemi aperti sulle proprieta' di convergenza di questi metodi. In particolare, si ritiene possibile trovare, generalizzando la tecnica di dimostrazione di Powell, un risultato di convergenza per i metodi LQN. Inoltre, sulla base di dati sperimentali, si e' fiduciosi nella possibilita' di ottenere una convergenza superlineare per una sottoclasse di tali metodi. Saranno anche studiate possibili estensioni a problemi non convessi di risultati classici di convergenza locale e globale. Si intendono poi applicare tali risultati per studiare proprieta' di convergenza "ad hoc" del processo di apprendimento su reti neuronali supervisionate (perceptroni multistrato e reti ricorrenti) e investigare nuovi algoritmi particolarmente efficienti per la minimizzazione della funzione di errore della rete. Si intendono inoltre analizzare lgoritmi veloci e stabili per il calcolo della soluzione di problemi ai minimi quadrati totali con struttura.
 

7) Implementazione di software prototipo. Gli algoritmi analizzati verranno implementati per essere confrontati numericamente su problemi significativi e in diversi ambiemti software, sia orientati alla sperimentazione (e.g. Mathematica, MATLAB) sia con linguaggi piu' efficienti (FORTRAN, C). Inoltre si intende sviluppare software per la fattorizzazione ricorsiva automatica di polinomi basato su aritmetiche multiprecisione nella linea software di [BFi] e con i risultati di {BGM1]. Per entrambi i compiti si intende disporre di un gruppo di workstation veloci connesse in rete ed utilizzabili anche dai ricercatori delle altre unita', in modo tale che software e dati risiedano fisicamente nello stesso posto e siano facilmente accessibili da tutti i ricercatori del progetto.