Vai al contenuto| Home page|

   Ti trovi in: HOME »Programmi, progetti e risultati »I progetti »PRIN - Programmi di ricerca di Rilevante Interesse Nazionale»Programma di ricerca
INIZIO_TESTO_DA_INDICIZZARE

PROGRAMMA DI RICERCA 2004

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

Analisi di strutture di matrici: metodi numerici e applicazioni

Università di Pisa
Abstract
MOTIVAZIONI
Ampia parte di problemi di Calcolo Scientifico e' ricondotta a risolvere problemi di algebra lineare. Le grandi dimensioni e la complessita' dei modelli matematici si traduce in una grande massa di dati e nell'alta complessita' di risoluzione di problemi computazionali. Metodi generali di risoluzione non sono in pratica applicabili per il loro grande costo, ed e' quindi necessario ricorrere a metodi appositamente progettati sulle caratteristiche specifiche del problema.

Queste specificita', tradotte nel linguaggio dell'algebra lineare, si ritrovano in termini di struttura e sparsita' delle matrici coinvolte nel modello.

Molte strutture sono ricorrenti in diversi contesti e applicazioni. Ad esempio, matrici a banda si incontrano nel trattamento numerico di problemi differenziali, nelle equazioni alle differenze, nell'interpolazione spline, etc; proprieta' di invarianza per traslazione che si incontrano nel trattamento digitale di segnali e immagini, in statistica, nella risoluzione di catene di Markov, conducono a matrici di Toeplitz. Problemi multi dimensionali conducono a matrici multilivello e a blocchi.

Spesso le proprieta' del modello originale conducono a strutture non evidenti (non lineari) come strutture displacement, localmente Toeplitz, semiseparabili.

L'analisi di matrici con struttura e il disegno di algoritmi specifici per problemi di algebra lineare numerica ha ricevuto grande >>>

Coordinatore Scientifico del Programma di Ricerca
Dario Andrea BINI Università di PISA
Obiettivo del Programma di Ricerca
Il progetto si basa sulle seguenti linee guida e idee base:

- Le matrici strutturate hanno un ruolo fondamentale in larga parte di problemi matematici nella teoria e nelle applicazioni.
- L'analisi di matrici strutturate, oltre all'interesse teorico in se', e' un passo obbligato per il disegno di algoritmi di risoluzione efficienti.
- La tecnologia delle matrici con struttura sviluppata negli anni, puo' essere usata per risolvere importanti problemi applicativi che difficilmente potrebbero essere risolti da algoritmi generici.
- La tecnologia delle matrici con struttura puo' fornire strumenti di risoluzione per problemi apparentemente non strutturati.
- Il progetto e l'analisi di algoritmi ritagliati sulle strutture specifiche deve essere complementato dallo studio della robustezza e stabilita' numerica.

Quindi, alla base di questo progetto si colloca l'analisi di proprieta' teoriche e computazionali di matrici con struttura al fine di migliorare le conoscenze nel settore e di introdurre nuovi strumenti di progettazione e analisi di algoritmi per risolvere problemi teorici e di calcolo scientifico.

Per chiarezza il programma viene idealmente suddiviso nelle seguenti parti:

-A- Svolgere l'analisi di proprieta' teoriche e computazionali di matrici strutturate.

-B- Mettere a puno strumenti "strutturati" per il progetto di algoritmi efficienti per risolvere ampie classi di >>>

Risultati parziali attesi
È previsto che gli avanzamenti teorici della ricerca (punto A) condurranno a risultati computazionali e algoritmici molto efficaci, tra cui:

U1,U3: Migliore comprensione di metodi numerici per catene di Markov (C6) in termini di fattorizzazioni deboli di Wiener-Hopf (B10,A1,A6,A8). Nuovi risultati di esistenza della fattorizzazione per certe matrici multilivello di Toeplitz a blocchi.

U1: Risoluzione efficiente di fluid queues mediante riduzione ciclica e trasformata di Cayley (C6,B9). Calcolo del Reward per catene di Markov M/G/1 (C6). Estensione e generalizzazione della tecnica di shift per catene di Markov generiche (B9,C6).

U1: Algoritmi per la radice p-esima di una matrice (B9) e fattorizzazioni di Wiener-Hopf (B10). Soluzione di equazioni algebriche di Riccati con riduzione ciclica (B9).

U1: Analisi di algoritmi per polinomi rappresentati nella base di Bernstein e applicazioni al CAGD (B8,C7).

U1: Elaborazione e analisi di metodi di minimizzazione quasi-Newton basati sull'approssimazione dell'Hessiano in algebre matriciali, applicazioni a reti neurali (A4,B11,C8).

U1,U2: Elaborazione, analisi e implementazione di risolutori polinomiali basati sul calcolo di autovalori per matrici diagonali+rango 1 (A2,B8,B2). Calcolo di zeri di polinomi espressi nella base di Szego, visti come autovalori di matrici di Hessenberg unitarie+rango 1 (A2,B8). Algoritmi per autovalori di matrici >>>

Durata
24 mesi
Base di partenza scientifica nazionale o internazionale
Molti problemi importanti in matematica pura e applicata coinvolgono classi di matrici con struttura frequentemente incontrate in contesti diversi. Le strutture di matrici sono la traduzione algebrica delle proprieta' specifiche dei problemi che modellizzano. Proprieta' generali quali l'invarianza per shift, il supporto compatto, la separabilita' di variabili, condivisi da numerosi problemi in aree diverse, si traducono in strutture di matrici che sono pervasive come le matrici di Toeplitz, matrici a banda, semi separabili e quasi separabili. Esse si incontrano in diversi problemi in analisi numerica, statistica, probabilita', computer algebra, analisi di segnali e immagini digitali, acustica, astronomia, giusto per citarne alcuni. Altre strutture correlate quali matrici di Hankel, Vandermonde, Cauchy, Pick, Bezout Sylvester non sono meno rilevanti.

L'analisi di matrici con struttura e' molto importante per individuare algoritmi di risoluzione veloce ed efficiente di molti problemi che, per le loro dimensioni, non potrebbero essere risolti con algoritmi generali.

L'interesse per matrici con struttura, gia' vivo negli anni 60 [GS] e 70' [Tr], [GoS] con i metodi diretti per sistemi di Toeplitz e implicitamente con i risolutori veloci di Poisson [BGN], e' cresciuto di importanza negli anni per il lavoro di diversi gruppi internazionali di ricerca molto attivi. Si e' consolidata un'ampia letteratura su diversi problemi matematici correlati e sono >>>