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)
PROGRAMMA DI RICERCA - MODELLO A
Anno 2004 - prot. 2004015437
Parte: I
1.1 Programma di Ricerca di tipo: interuniversitario
Area Scientifico Disciplinare: Scienze
Matematiche e informatiche
1.2 Titolo del
Programma di Ricerca
1.3 Abstract
del Programma di Ricerca
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 attenzione
negli anni e
ha condotto a grandi avanzamenti. Da un lato sono stati raggiunti
avanzamenti
teorici nello studio di proprieta' astratte delle piu' frequenti
strutture,
dall'altro il disegno di algoritmi ad hoc ha permesso di risolvere
problemi
significativi in diversi campi applicativi. Ad esempio, algoritmi per
risolvere
equazioni matriciali in modelli di code, basati su proprieta' di
matrici di
Toeplitz, hanno condotto ad un abbattimento del tempo di cpu nella
risoluzione
di modelli ingegneristici di reti metropolitane.
IL PROGETTO:
Il progetto e' la continuazione del precedente progetto MIUR 2002-2003,
il suo
scopo e' ampliare il range di strumenti strutturati e delle loro
applicazioni
espandendo e integrando i risultati ottenuti nel 2002-2003 (si veda
http://bezout.dm.unipi.it), secondo le seguenti linee:
A- Analisi di proprieta' algebriche analitiche e computazionali di
classi di
matrici strutturate incontrate in problemi teorici e applicativi,
incluse
strutture lineari e non lineari. In particolare, strutture
displacement,
(Toeplitz, Hankel, Cauchy, Bezout, etc), semi-separabili, multi livello
(multi
indice), matrici con strutture locali, sistemi parametrici.
B- Disegno di algoritmi veloci e numericamente affidabili (stabili e
robusti)
per risolvere problemi computazionali che coinvolgono matrici
strutturate, come
minimi quadrati totali, sistemi lineari, autovalori e autovettori.
Adattamento
a specifiche strutture di tecniche note quali multigrid, PCG, GMRES,
iterazioni
QR. Uso di strumenti di algebra lineare strutturata per problemi
localmente
strutturati o senza struttura.
C- Applicazione dei risultati alla risoluzione di problemi
computazionali di
calcolo scientifico inclusi: trattamento di immagini, problemi inversi
non
lineari, modelli di code, equazioni matriciali, equazioni differenziali
e
integrali, scattering inverso, approssimazione di zeri di polinomi,
problemi di
Computer Aided Geometric Design, modelli del metabolismo umano, motori
di
ricerca sul web, reti neurali.
D- Implementazione degli algoritmi in versione prototipale, confronti
numerici
e validazioni.
STATO DELL'ARTE:
Diversi gruppi internazionali di ricerca sono molto attivi nel campo.
Il gruppo
italiano lavora nell'area da molti anni. C'e' una solida base teorica e
algoritmica fatta di potenti strumenti e tecniche efficaci sviluppati
negli
anni da molti ricercatori. Esistono diverse linee di ricerca dove gli
interessi
si stanno incanalando e sviluppando a livello internazionale. Alcune
linee sono
gemmate dal progetto MIUR 2002-2003.
1.4 Durata del
Programma di Ricerca: 24
Mesi
1.5 Settori
scientifico-disciplinari interessati dal Programma di Ricerca
·
MAT/08 -
Analisi Numerica
·
MAT/07 -
Fisica Matematica
·
INF/01 –
Informatica
·
MAT/02 –
Algebra
·
MAT/05 -
Analisi Matematica
1.6 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
1.7
Coordinatore Scientifico del Programma di Ricerca
DARIO ANDREA BINI,
Professore ordinario,
Dipartimento di
Matematica "Leonida Tonelli", Università di PISA,
Facoltà di Sienze
Matematiche Fisiche e Naturali bini@dm.unipi.it
1.8 Curriculum
scientifico
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 e associate editor di SIAM J. Matrix Anal. Appl., 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, degli operatori di dislocamento e di matrici semiseparabili, 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.9 Pubblicazioni scientifiche
più
significative del Coordinatore del Programma 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.; L.
GEMIGNANI; B. MEINI (2003). Solving
certain matrix equations by means of Toeplitz computations: algorithms
and
applications CONTEMPORARY MATHEMATICS. (vol. 323 pp. 151-167)
3.
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)
4.
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)
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.10 Elenco delle
Unità di Ricerca
|
Nº |
Responsabile scientifico |
Qualifica |
Settore |
Università |
Dipart./Istituto |
Mesi |
|
1. |
Prof. ordinario |
MAT/08 |
PISA |
MATEMATICA "Leonida Tonelli" |
16 |
|
|
2. |
Prof. associato |
MAT/08 |
GENOVA |
MATEMATICA |
14 |
|
|
3. |
Prof. ordinario |
MAT/08 |
CAGLIARI |
MATEMATICA |
12 |
1.11 Mesi uomo
complessivi dedicati al programma
|
|
|
Numero |
Mesi uomo |
Mesi uomo |
Totale mesi uomo |
|
Personale
universitario dell'Università sede dell'Unità di Ricerca |
14 |
83 |
73 |
156 |
|
|
Personale
universitario di altre Università |
10 |
69 |
67 |
136 |
|
|
Titolari di
assegni di ricerca |
1 |
9 |
7 |
16 |
|
|
Titolari di borse |
Dottorato |
1 |
8 |
8 |
16 |
|
Post-dottorato |
0 |
|
|
|
|
|
Scuola di
Specializzazione |
0 |
|
|
|
|
|
Personale a
contratto |
Assegnisti |
1 |
9 |
7 |
16 |
|
Borsisti |
0 |
|
|
|
|
|
Dottorandi |
0 |
|
|
|
|
|
Altre
tipologie |
1 |
4 |
6 |
10 |
|
|
Personale
extrauniversitario |
2 |
8 |
8 |
16 |
|
|
TOTALE |
|
30 |
190 |
176 |
366 |
Parte:
II
2.1 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 problemi
computazionali
C- Applicare i nuovi algoritmi a problemi di carattere applicativo.
D- Implementare in termini di software prototipo gli algoritmi ottenuti
nel
progetto e svolgere confronti computazionali e validazione.
Gli argomenti considerati sono problemi di algebra lineare numerica
strutturata
(ALNS), che sono una naturale continuazione delle questioni di maggiore
interesse trattate nel precedente progetto MIUR 2002-2003 "Structured
matrix analysis: numerical methods and applications", o problemi che
sebbene non in programma nel 2002-2003, sono risultati di particolare
interesse
in se' e per le applicazioni. Infatti, nel nuovo progetto maggior
attenzione e'
rivolta alle applicazioni. Argomenti applicativi sono una sorgente di
problemi
teorici interessanti e di nuove strutture, allo stesso tempo
costituiscono un
banco di lavoro dove collaudare l'efficienza degli algoritmi
individuati con
strumenti dell'ALNS.
Si considerano matrici di Toeplitz e con struttura displacement
(incluse
matrici di Hankel, Cauchy, Pick, Vandermonde, Sylvester, Bezout,
Frobenius, e
companion generalizzate), matrici localmente Toeplitz, a banda, semi
separabili
e quasi separabili, multi livello (multi indice), matrici parametriche,
algebre
trigonometriche.
Problemi computazionali includono la risoluzione di sistemi lineari,
calcolo di
autovalori, equazioni matriciali, problemi di minimi quadrati (totali),
problemi di minimizzazione, fattorizzazione di Wiener-Hopf, calcoli con
polinomi.
Gli aspetti computazionali considerati sono l'analisi di
precondizionatori,
tecniche multigrid, fattorizzazioni di matrici, sequenze di Krylov,
iterazioni
QR, metodi di regolarizzazione, metodi di proiezione, condizionamento
numerico
e stabilità, integrazione di strumenti simbolici e numerici,
relazioni fra
operazioni con polinomi e matrici strutturate.
Le applicazioni riguarderanno problemi di elaborazione di immagini,
inclusi LBT
e restauro, problemi di code modellati da catene di Markov di tipo
M/G/1, G/M/1
e QBD, problemi di acustica e di scattering inverso, problemi di CAGD,
modelli
differenziali di metabolismo umano, motori di ricerca sul web, reti
neurali e
apprendimento ottimale, equazioni integrali.
Piu' precisamente le classi di matrici strutturate e i relativi
problemi
computazionali studiati nelle parti A,B,C,D, sono tracciati di seguito.
Per una
descrizione di maggior dettaglio si rimanda alla sezione 2.4 e ai
modelli B
delle tre unita' operative.
A1- Matrici di Toeplitz e localmente Toeplitz
A2- Matrici semi separabili e quasi separabili
A3- Matrici parametriche
A4- Algebre di matrici e trasformate trigonometriche
A5- Matrici companion generalizzate e matrici risultante
A6- Matrici di Toeplitz a blocchi
A7- Matrici multi livello (multi indice)
A8- Matrici infinite di Toeplitz
A9- Strutture non convenzionali
I problemi computazionali nella parte B sono:
B1- Sistemi lineari e problemi di minimi quadrati totali
B2- Problemi di autovalori
B3- Approssimazione funzionale
B4- Problemi inversi e regolarizzazione
B5- PDEs
B6- Multigrid
B7- Precondizionamento
B8- Polynomial computations
B9- Equazioni matriciali
B10- Fattorizzazioni di Wiener-Hopf
B11- Problemi di minimo
B12- Equazioni integrali con nucleo strutturato
B13 Metodi GMRES e di Krylov
B14 Metodi di proiezione in algebre di Wiener pesate
Le applicazioni nella parte C riguarderanno:
C1- Motori di ricerca sul web
C2- Modelli di metabolismo umano
C3- Restauro di immagini
C4- Scattering inverso, problemi inversi non lineari, acustica e remote
sensing
C5- Problemi di identificazione
C6- Catene di Markov e modelli di code
C7- Computer Aided Geometric Design
C8- Reti neurali
C9- Problemi di astronomia
Per la parte D si considerano:
D1- Generazione di matrici test
D2- Toolbox di MatLab
D3- Creazione di software prototipo
Infine fra gli obiettivi del progetto e' inclusa l'organizzazione della
quinta
edizione del congresso internazionale
Matrix Analytic Method in Stochastic Models" MAM5, Pisa, Giungo 2005
(http://www.dm.unipi.it/~mam5).
Il congresso che copre argomenti di probabilita' applicata, ingegneria
e
analisi numerica e' un forum internazionale per tracciare e discutere
lo stato
dell'arte delle ricerche nel settore dei metodi numerici in
probabilita'
applicata.
2.2 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 state organizzati numerosi congressi internazionali dedicati a
matrici con
struttura, algoritmi e applicazioni.
La base teorica ed algoritmica su cui s'innesta il progetto e' molto
ampia e
ricca di strumenti e risultati.
Storicamente i principali avanzamenti nel campo delle matrici con
struttura si
trovano in diversi libri alcuni di essi sono pietre miliari del
settore. Qui
per ragioni di spazio possiamo citarne solo alcuni. I libri di Iohvidov
[I] e
di Heinigh e Rost [HR] su strutture Toeplitz e Hankel, il libro di
Bultheel e
Van Barel [BvB] sulle relazioni fra strutture e polinomi ortogonali, il
libro
di Bini e Pan [BP] sulle relazioni fra operazioni con matrici
strutturate
polinomi, i libri di Grenander and Szego [GS] e Boettcher e Silbermann
[BS]
sulle proprieta' spettrali di matrici di Toeplitz, i libri di Gohberg,
Goldberg
e Kaashoek [GGK] e di Gohberg Lancaster e Rodman [GLR] e la serie
"Operator Theory and Applications:" della Birkhauser, su questioni
piu' astratte. Il libro [DV] di Dewilde e van der Veen collegato a
matrici
semiseparabili, i libri editi da Kailath e Sayed [KS], da Bini,
Tyrtyshnikov e
Yalamov [BTY], e da Olshevsky [O] che contengono avanzamenti recenti
nel
settore e il lavoro di rassegna di Chan e Ng [CN] sul
precondizionamento di
Toeplitz.
La teoria dei displacement operators di Kailath et al [KS] e
l'ampia
letteratura originatasi attorno costituisce una base solida e
importante.
Richiamiamo i risultati di distribuzione spettrale asintotica
iniziati
nel lavoro pioneristico di Szego [BS] e culminati nel lavoro di
Tyrtyshnikov
[TZ] sul "comportamento globale" dello spettro di successioni di
Toeplitz. In letteratura si trovano estensioni a funzioni generatrici a
valori
matriciali e a sequenze che nascono nella teoria del precondizionamento
come
pure alcune applicazioni alla approssimazione e alla quadratura.
Un'altra
importante estensione riguarda le matrici localmente Toeplitz
cioe'
strutture che sono di Toeplitz solo "localmente" o che posseggono
diverse strutture locali [Ti] e includono in particolare le matrici che
discretizzano operatori differenziali con condizioni al bordo.
Proprieta' spettrali asintotiche giocano un ruolo importante nel
disegno di precondizionatori
per gradiente coniugato. Le matrici circolanti associate
alla trasformata
discreta di Fourier che Strang [St] propose nel 1986, sono state
affiancate
da piu' generali algebre trigonometriche. Un trattamento
sistematico del
precondizionamento e' stato fatto da molti ricercatori fra cui T.Chan,
R.Chan,
S.Serra, F. DiBenedetto, G.Fiorentino, E.Tyrtyshnikov, T. Huckle,
Potts,
Steidl, Nagy, Plemmons nel caso mono e multi livello. Altre algebre
trigonometriche sono state studiate da Kailath, Olshevsky, e dal gruppo
italiano.
I metodi GMRES, Lanczos e gradiente coniugato sono strumenti
importanti
nel progetto. A riguardo esiste un'ampia letteratura consolidata in
numerosi
articoli e libri classici.
Per matrici multi-indice di Toeplitz non esiste molta
letteratura per la
mancanza di una teoria algebrica di operatori matriciali multi indice a
fronte
di un interesse oggettivo sull'argomento in molti campi applicativi.
Contributi
in questa direzione sono dati dal gruppo di van der Mee, Rodriguez,
Seatzu,
Ehrardt. Esclusivamente nel caso scalare, due metodi di
fattorizzazione
spettrale in algebre di Banach pesate sono stati sviluppati
rispetto ad un
ordinamento totale fissato. Nel caso multi indice di Toeplitz a blocchi
esistono solo risultati parziali sulla fattorizzazione spettrale.
Matrici strutturate hanno un ruolo importante in molte polynomial
computations dove molti problemi legati alla approssimazione
polinomiale e
razionale possono essere descritti in termini di matrici strutturate,
incluse
le matrici di Cauchy, Pick, Vandermonde, localmente
Toeplitz e semiseparabili. Citiamo il libro [BP] e l'ampia
letteratura con
i contributi di Bini, Boettcher, Gemignani, Meini, Fiorentino. Riguardo
al
calcolo di fattorizzazioni di Wiener-Hopf, inversione di
polinomi di
Laurent e di matrici bi-infinite di Toeplitz, si citano [BGM1,
GMRS, MRS].
Le relazioni fra calcolo simbolico e numerico sono importanti
in questo
contesto. A questo riguardo il progetto europeo FRISCO (FRamework for
the
Integration of Symbolic and numeric Computing) costituisce una solida
base per
la nostra ricerca, un'integrazione avanzata di strumenti numerici e
simbolici e
fatta in [CGTW].
Matrici semi separabili e quasi separabili hanno un ruolo
particolare in
questo progetto. Esiste un'ampia e solida letteratura a riguardo, oltre
ai
risultati classici di Gohberg, Eidelman, Dewilde, Chandrasekaran,
alcuni
interessanti risultati sono stati recentemente ottenuti dal gruppo di
van Barel
e dal gruppo italiano. In particolare in [VBM1] sono mostrate
interessanti
trasformazioni di matrici simmetriche in forma semi separabile, in
[BGT] le
proprieta' delle matrici semiseparabili sono usate per realizzare
efficienti
risolutori del problema tridiagonale di autovalori.
Un altro studio che nasce in diversi contesti (elaborazione di
immagini, PDE
dipendenti dal tempo, risolutori iterativi di autovalori) riguarda i shifted
linear systems del tipo (A+eI)x=b. Talvolta I e' sostituita con una
generale matrice diagonale [BeBe].
Infine l'applicazione di matrici strutturate fatta di recente a
problemi senza
struttura, come certi problemi di minimizzazione o a problemi
di minimi
quadrati totali, si e' mostrata molto efficace. Si veda [DFLZ,LMV1]
dove
sono mostrate alcune applicazioni a reti neurali e allo speech
compression.
Metodi numerici per catene di Markov e' un settore in cui la
tecnologia
delle matrici strutturate ha prodotto grandi avanzamenti. Si fa
riferimento ai
libri [Ne], [LR] per la descrizione dei problemi e ai lavori di Bini,
Meini e
Latouche per un esempio di algoritmi basati su matrici di Toeplitz. In
particolare il metodo di riduzione ciclica di [BGN] si e'
recentemente
rivelato uno strumento potente per risolvere catene di Markov di tipo
M/G/1,
G/M/1 e QBD [BM3]. Un altro problema importante collegato ai modelli di
code e
incontrato in diverse altre applicazioni dove matrici con struttura
hanno un
ruolo importante riguarda la risoluzione di equazioni matriciali
non lineari
[HK] su cui esiste un'ampia letteratura [BGM2,M4].
Un recente strumento di acquisizione ottica che richiede la risoluzione
di intressanti
problemi di ricostruzione e' il Large Binocular Telescope (LBT)
[AHSS].
Tutti i metodi numerici nella ricostruzione di immagini devono
utilizzare
qualche forma di regolarizzazione. La ricostruzione ottenuta
con metodi
di base puo' essere migliorata con strumenti avanzati, in particolare
lo studio
delle boundary conditions (vedi [J,NCT] per proposte classiche
e [S3]
per l'idea delle condizioni anti riflettenti) e l'uso delle wavelets
[CCSS].
Vari problemi applicati di astronomia come lo studio del trasferimento
di luce
in atmosfera planetaria conduce al trattamento di varie matrici con
strutture
non convenzionali. Alcune di queste sono studiate in [HMD]. Gran parte
di
ricerca nell'inverse scattering in particolare in acustica,
ottica e
elettromagnetismo, dipende strettamente dalla soluzione di equazioni
integrali con nucleo strutturato e le loro analoghe discrete. A
questo
proposito, i risultati piu' rilevanti di analisi funzionale e teoria
degli
operatori si trovano nella serie Operator Theory and Applications della
Birkhauser.
Un'interessante estensione del metodo band extension method che
sembra
promettente per risolvere sistemi multi indice e' stato ottenuto di
recente in
[GW].
Diversi contributi sono stati dati recentemente nell'ambito del
progetto MIUR
2002-2003 (vedi la pagina web http://bezout.dm.unipi.it) di cui questa
e' una
proposta di continuazione, e dei quali riportiamo di seguito una lista
di
principali lavori con gli avanzamenti piu' rilevanti. Questi sono nel
campo
della analisi spettrale e computazionale di ampie classi id matrici con
struttura, incluse matrici di Toeplitz, localmente Toeplitz e
semiseparabili,
nella regolarizzazione di problemi inversi che si incontrano in diverse
applicazioni, in altre aree applicative che includono trattamento di
immagini
digitali, approssimazioni funzionali, equazioni differenziali, nel
campo di
polynomial computations e CAGD, nelle catene di Markov e modelli di
code,
equazioni matriciali, problemi di minimizzazione, nelle matrici multi
indice e
fattorizzazioni spettrali, nei sistemi mal condizionati.
Molti di questi risultati sono stati presentati a numerosi congressi
organizzati in questa area, fra cui il 14-esimo congresso IWOTA
International
Workshop on Operator Theory and Applications, Cagliari, giugno 2003, i
cui
proceedings saranno pubblicati nella serie OT della Birkhauser, editori
Kaashoek, van der Mee e Seatzu.
I ricercatori di questo progetto hanno una lunga tradizione nel campo
delle
matrici con struttura con una esperienza di base forte e particolari
specializzazioni in settori diversi. Tali specializzazioni includono
questioni
teoriche e computazionali, disegno e analisi di algoritmi e software,
esperienze di applicazioni in campi diversi quali elaborazione di
immagini
digitali, equazioni differenziali e integrali, modelli di code e catene
di
Markov, polynomial computation e computer algebra.
[ADS] A.Aricò, M.Donatelli, S.Serra, Multigrid optimal
convergence for
certain (multilevel) structured linear systems. SIMAX, in press.
[BBCR] M.Bertero, P.Boccacci, A.Custo, M.Robberto, A Fourier-based
method for
the restoration of chopped and nodded images, Astron. Astroph. 406,2003
[BCV]D.Bini,G.Codevico,M.Van Barel, Solving Toeplitz Least Squares
Problems by
Means of Newton's Iteration, Num.Algo.,33,2003
[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.Neur.Netw. 14,2003
[BDG]D.Bini F.Daddi L.Gemignani. On the shifted QR iteration applied to
Frobenius matrices, Dip.Mat. Univ.Pisa 2003
[BeBe]M.Benzi,D.Bertaccini, Approximate inverse preconditioning for
shifted
linear systems. BIT 43,2003
[BG1]D.Bini L.Gemignani. Bernstein-Bezoutian matrices. Theor.Comp.Sci
2004.
[BG2]D.Bini L.Gemignani. Solving quadratic matrix equations and
factoring
polynomials: new fixed point iterations based on Schur complements of
Toeplitz
matrices. Numer.Lin.Alg.Appl.
2004.
[BGP]D.Bini L.Gemignani V.Pan. Inverse Power and Durand-Kerner
Iterations for
Univariate Polynomial Root-Finding, Comp.Math.Appl.
[BFGM]D.Bini, G.Fiorentino L.Gemignani B.Meini. Effective fast
algorithms for
polynomial spectral factorization. Num.Algo. 34,2003
[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
[BLM]D.Bini G.Latouche B.Meini, Solving nonlinear matrix equations
arising in
tree-like stochastic processes,Lin.Alg.Appl. 366, 2003
[BM]D.Bini B.Meini. Non-skip-free M/G/1 type Markov chains and Laurent
matrix
power series, Fourth Int.Conf. Num. Sol. of Markov Chains, vol. 1, 2003
[BN]D.Bertaccini M.Ng, Band-Toeplitz Preconditioned GMRES Iterations
for
time-dependent PDEs. BIT 43,2003
[D]C.DiFiore, Structured matrices in unconstrained minimization
methods,
Cont.Math.323,2003
[DiB]F.DiBenedetto, The m-th difference operator applied to L2
functions on a
finite interval Lin.Alg.Appl. 366,2003
[DLZ]C.DiFiore F.Lepore P.Zellini, Hartley-type algebras in
displacement and
optimization strategies, Lin.Alg.Appl.366,2003
[ET]C.Estatico A.Tamasan, A Newton linearization approach for solving
the
atmospheric retrieval problem. Tech. Rep., UCLA, 2003
[FG1]D.Fasino L.Gemignani. Fast and stable solution of
banded-plus-semiseparable linear systems. CALCOLO 39,2002
[FG3]D.Fasino L.Gemignani Direct and inverse eigenvalue problems for
diagonal-plus-semiseparable matrices, Num.Algo.34,2003
[FMB]D.Fasino N.Mastronardi M.Van Barel, Fast and stable algorithms for
reducing diagonal plus semiseparable matrices to tridiagonal and
bidiagonal
form. Cont.Math. 323,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
[FS]D.Fasino, S.Serra, From Toeplitz matrix sequences to zero
distribution of
orthogonal polynomials, Cont.Math. 323,2003
[GL]L.Gemignani G.Lotti. Efficient and stable solution of M-matrix
linear
systems of (block) Hessenberg form. SIMAX 24,2003
[HMD]J.W.Hovenier C.van der Mee H.Domke. Transfer of polarized light in
planetary atmospheres. Basic concepts and practical methods. Kluwer,
Dordrecht,
2004,to appear
[Ia] B.Iannazzo, A note on computing the matrix square root. CALCOLO,
2004.
[LMV1] P.Lemmerling,N.Mastronardi,S.VanHuffel, Efficient implementation
of a
structured total least squares based speech compression method,
Lin.Alg.Appl.
366,2003
[M4] B.Meini, The matrix square root from a new functional perspective:
theoretical results and computational issues , SIMAX to appear
[MNS] C.van der Mee M.Z.Nashed S.Seatzu, Sampling expansions and
interpolation
in unitarily translation invariant reproducing kernel Hilbert spaces,
Adv.Comp.Math.,19,2003.
[MRS1] C.van der Mee G.Rodriguez S.Seatzu. Semi-infinite multi-index
perturbed
block Toeplitz systems. Lin.Alg.App. 366,2003
[MS] C.van der Mee S.Seatzu. A method for generating infinite positive
definite
self-adjoint test matrices and Riesz bases. Preprint 2004
[NSV] D.Noutsos, S.Serra, P.Vassalos, Spectral equivalence and matrix
algebra
preconditioners for multilevel Toeplitz systems: a negative result,
Cont.Math.,
323,2003
[S3] S.Serra, A note on anti-reflective boundary conditions and fast
deblurring
models. SIAM J.Sci.Comp. 25,2003
[S4] S.Serra, Generalized Locally Toeplitz sequences: spectral analysis
and
applications to discretized Partial Differential equations,
Lin.Alg.Appl.
366,2003
[ST1] S.Serra, C.Tablino Possio, Analysis of preconditioning strategies
for
collocation linear systems. Lin.Alg.App.369,2003
[ST2] S.Serra, C.Tablino Possio, Superlinear preconditioners for Finite
Differences linear systems. SIMAX 25,2003
[STy1] S.Serra E.Tyrtyshnikov, How to prove that a preconditioner can
not be
superlinear, Math.Comp.72 2003
2.2.a Riferimenti bibliografici
[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 algorithm for 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
2.3 Numero di
fasi del Programma di Ricerca: 1
2.4
Descrizione del Programma di Ricerca
Fase 1
Durata: 24 mesi Costo
previsto: 187.000 Euro
Descrizione:
Diverse collaborazioni sono gia' in atto fra le
diverse Unita', di seguito denotate con U1, U2, U3. Al fine di meglio
articolare organicamente le attivita' di ricerca e creare sinergie, si
prevede di
formare un comitato di coordinamento costituito dai 3 responsabili
delle unita'
che si riunira' periodicamente per tracciare il punto della situazione,
scambiare informazioni sui risultati parziali ottenuti e valutare
l'opportunita' di ulteriori incontri fra i partecipanti.
Si prevede una riunione iniziale di coordinamento fra tutti i
ricercatori
partecipanti al progetto da svolgere all'inizio dell'attivita' di
ricerca del
progetto stesso. Si prevede un workshop intermedio da organizzarsi
circa dopo
il primo anno di attivita' e un workshop finale aperto anche ad altre
componenti italiane e internazionali della ricerca del settore in cui
vengono
presentati i vari risultati ottenuti.
Una linea strategica del progetto consiste nel favorire le relazioni
fra gli
aspetti piu' applicativi (vedi obiettivi C e D nel punto 2.1) e quelli
teorici
facendo interagire i ricercatori delle varie unita' con maggior
esperienza
nelle applicazioni con i ricercatori che hanno maturato maggior
esperienza
nell'algebra lineare numerica strutturata, al fine di creare sinergie e
ricadute applicative. Infatti, si ritiene che da una parte cio'
favorisca
l'applicazione e l'adattamento degli strumenti astratti e
computazionali ai
problemi specifici con la conseguente creazione di software efficiente,
dall'altra cio' permetta di analizzare piu' a fondo i problemi
applicativi
specifici e conseguentemente di sviluppare nuovi strumenti teorici e
computazionali di interesse generale per trattarne le strutture. Questo
verra'
realizzato organizzando giornate di lavoro tematiche che potranno
essere
aperte, se necessario, a ricercatori di altri gruppi internazionali che
verranno invitati periodicamente nelle varie unita'. Sono quindi
previsti
frequenti interazioni fra le varie unita' in relazione ai punti di
ricerca
comuni. Sono anche previsti frequenti contatti con ricercatori di altri
gruppi
internazionali e permanenze piu' o meno prolungate di ricercatori del
presente
progetto all'estero presso altri gruppi di ricerca con interessi
comuni. Un congresso
internazionale su temi specifici dei metodi numerici per catene di
Markov sara'
organizzata a Pisa nel giugno 2005.
Si ritiene che ogni unita' operativa provveda autonomamente alla
realizzazione
del software prototipale relativo agli algoritmi analizzati. Si
richiede
comunque che, per poter effettuare un confronto piu' possibilmente
significativo, e affinche' i componenti delle varie unita' possano
usare
facilmente il software prodotto da altre unita', tale software debba
soddisfare
ad opportune specifiche che verranno stabilite nelle riunioni di
coordinamento.
Si intende poi attivare una rete di workstations che fornisca la
struttura
hardware dove viene mantenuto, sperimentato e messo a confronto il
software
prototipale prodotto dalle varie unita', assieme a tutti i problemi
test
selezionati. L'accesso alle informazioni sara' aperto e realizzato
mediante
pagina web.
Per quanto riguarda i costi del progetto sono previste alcune spese
specifiche
per un totale di circa 41000 euro che sono: il costo di contratti e
assegni di
ricerca per un totale di 33000 euro che rafforzeranno le unita' U1 e
U2, e il
contributo di 8000 euro per il costo dell'organizzazione della quinta
edizione
del congresso internazionale, "Matrix Analytic Method in Stochastic
Models"
MAM5, Pisa, giungo 2005 (http://www.dm.unipi.it/~mam5). Il congresso
che copre
argomenti di probabilita' applicata, ingegneria e analisi numerica e'
un forum
internazionale per tracciare e discutere lo stato dell'arte delle
ricerche nel
settore dei metodi numerici in probabilita' applicata.
Per quanto riguarda le attivita' di ricerca, verranno perseguiti gli
obiettivi
riportati nel punto 2.1, cui fa riferimento il programma che segue.
Qui,
piuttosto che dare una descrizione esaustiva delle varie parti (che
puo' essere
trovata nei vari modelli B delle unita') preferiamo evidenziare le
sinergie fra
le diverse parti del programma.
PARTE A:
Piu' specificamente, riguardo la parte A1 sulle matrici di
Toeplitz e
localmente Toeplitz il quadro e' abbastanza completo riguardo
all'analisi
spettrale asintotica (distribuzione, localizzazione, comportamento
estremale),
anche per matrici localmente Toeplitz (incluse PDE con coefficienti
variabili
su domini irregolari). Argomenti che richiedono ulteriore studio sono:
- l'analisi del condizionamento spettrale (comportamento estremale) di
matrici
multi indice, seguendo l'approccio di Boettcher and Grudsky;
- l'analisi delle relazioni fra proprieta' spettrali e convergenza di
metodi
iterativi precondizionati nel caso in cui le proprieta' asintotiche
della
successione di sistemi lineari sono note indipendentemente dalla
struttura.
Crediamo infatti che la funzione di distribuzione spettrale giochi un
ruolo
importante a riguardo anche per problemi non strutturati.
- Per le matrici multilivello (A7) l'interesse e' motivato dalla
necessita' di costruire precondizionatori efficienti (B7) per la
risoluzione iterativa di sistemi multi livello di Toeplitz incontrati
in molte
applicazioni quali trattamento di immagini, equazioni integrali,
scattering
inverso (B12,C3,C9). Attenzione speciale e' rivolta ai seguenti
argomenti
- Metodi multigrid (B6), dove particolare enfasi e' rivolta alla
scelta
del proiettore/smoother, all'estensione dei risultati di ottimalita' di
[ADSC]
al caso multilivello, applicazioni a problemi di restauro di immagini (C3)
e di PDE (B5).
- Precondizionamento (B7), dove si cerca di generalizzare i
risultati di
ottimalita' di [S. Serra, MathComp. 66,1997] al caso multi livello;
introdurre
algebre "arricchite" del tipo UTU* (A4) come
precondizionatori, dove U e' unitaria e legata a trasformate
trigonometriche e
T ha caratteristiche di sparsita', in modo da trovare precondizionatori
che
diano convergenza superlineare o siano ottimali. Costruire
precondizionatori
per il GMRES (B13) in cui il precondizionatore viene aggiornato
ad ogni
passo iterativo.
- Metodi di proiezione in algebre di Wiener con peso (B14)
[Boettcher,
Silbermann, "Analysis of Toeplitz operators" Springer 1990, Gohberg,
Feldman, vol 41 of Transl. Math. Monog. 1974] saranno considerate per
possibili
estensioni a matrici multi livello nel caso non definito o a blocchi
positivo
definito.
- Generazione di classi di matrici test (D1) ottenute
generalizzando i
risultati di [MNS,MS].
- Usare i metodi computazionali di [MRS1] per sistemi infiniti (A8)
multi livello (A7) perturbati per la risoluzione numerica di
equazioni
integrali con nucleo strutturato (B12).
- Applicazioni a problemi di scattering inverso in acustica, meccanica
quantistica e remote sensing (C9).
Per la parte A2 sulle matrici semi separabili studieremo:
- le relazioni tra matrici diagonali piu' semi separabili, matrici
razionali di
Krylov e funzioni razionali ortogonali;
- proprieta' di semiseparabilita' di matrici companion generalizzate (A5)
e calcolo di autovalori (B2); in particolare, studieremo le
proprieta'
dell'iterazione QR applicata a matrici nxn companion generalizzate e
gli
algoritmi per realizzare il passo QR in O(n) operazioni [BDG] con
applicazioni
al calcolo di zeri di polinomi (B8);
- la riduzione di una matrice generale simmetrica in forma
semiseparable.
Nella parte A3 si
studieranno sequenze di matrici del tipo Aj=A+vj Ej . Queste sono una
generalizzazione delle sequenze shiftate dove Ej e' la matrice
identica. Sistemi
con queste classi di matrici si incontrano in metodi classici per il
calcolo di
autovalori. Noi studiamo precondizionatori basati su fattorizzazioni
incomplete
indefinite per metodi di Krylov e fattorizzazioni incomplete
multilivello. Si
considerano applicazioni alla risoluzione di problemi di minimi
quadrati
totali.
Nella parte A4 riguardante algebre di matrici, oltre alle
matrici
"arricchite" citate sopra, si studia l'uso di matrici in algebre per
approssimare l'hessiano in problemi di minimo (B11) nella linea
di
[DFLz]. Altre algebre di matrici saranno analizzate nello studio delle
condizioni al contorno e del loro ruolo in problemi di restauro di
immagini (C3,C4).
Per le matrici companion generalizzate e le matrici risultanti nella parte
A5, si considerano matrici nxn diagonali piu' rango 1, matrici a
freccia,
commerade e Frobenius per le quali esiste una relazione diretta col
polinomio
caratteristico. Saranno studiati metodi per il passo QR di costo O(n),
in
termini di complessita' e stabilita'. Viene studiato il problema del
calcolo di
tutti gli autovalori (B2) con estensione a correzioni di rango
maggiore.
Questa parte riguarda anche A2 per le strutture semi separabili e B8
per
metodi di calcolo di zeri di polinomi.
Si considerano matrici risultanti, cioe' il cui polinomio
caratteristico e'
multiplo del risultante di due polinomi assegnati. Lo scopo e'
rappresentare
tale matrice in basi polinomiali diverse, ad esempio di Bernstein e
delle
potenze, e sfruttare le strutture per individuare algoritmi efficienti
per
polinomi (B8).
Matrici a blocchi verranno studiate nella parte A6 nel
tentativo di
estendere i risultati di Boettcher, Silbermann, e di Gohberg, Feldman
su
weighted Wiener algebras a matrici di Toeplitz a blocchi definite
positive.
Matrici semi-infinite di Toeplitz (A8) e fattorizzazioni di
Wiener-Hopf
(B10) saranno studiate allo scopo di fornire una migliore
comprensione
della risoluzione numerica di catene di Markov M/G/1, G/M/1 e QBD
incontrate in
modelli di code (C6) per individuare algoritmi efficienti nella
linea di
[BM,BM3,BM4].
Strutture non convenzioanli nella parte A9 consistono in ogni
struttura
che non ricade in quelle descritte finora. Infatti ci si aspetta di
incontrare
nuove classi nello studio di alcune applicazioni, in particolare nello
studio
di motori di ricerca sul web (C1), modelli di code (C6) e
problemi di astronomia (C9).
PARTE B:
Sistemi strutturati nella parte B1 verranno trattati in termini
di
metodi iterativi precondizionati e con metodi multigrid secondo le
strutture
coinvolte. I problemi agli autovalori saranno trattati similmente in
termini
delle strutture coinvolte.
Vogliamo proseguire alcune ricerche intraprese su problemi di
interpolazione o
approssimazione con funzioni razionali (B3), con particolare
riguardo
all'analisi del condizionamento strutturato e al posizionamento
ottimale dei
poli.
L'analisi di problemi inversi (B4) riguardera' lo studio del
numero di
iterazioni inteso come parametro regolarizzante, un'altra direzione
riguarda
l'estensione delle famiglie di precondizionatori regolarizzanti per la
ricostruzione di immagini non negative con applicazione al sistema LBT.
Un
altro argomento e' il disegno e l'analisi di algoritmi per sistemi
ottenuti da
regolarizzazione di tipo Tikhonov.
Per il punto sulle PDEs (B5), si studieranno proprieta' di
convergenza
del GMRES nella risoluzione di sistemi che discretizzano l'equazione di
convezione-diffusione con coefficienti di diffusione variabili, come
pure le
equazioni di convezione-diffusione dipendenti dal tempo in modelli di
metabolismo umano (C2).
Verranno studiate le proprieta' regolarizzanti dei metodi multigrid per
la
risoluzione di problemi mal posti (B6,B4).
Il precondizionamento al punto B7 riguardera' principalmente
matrici
multi livello di Toeplitz.
Per le polynomial computations (B8), si analizzeranno le
proprieta'
della fattorizzazione debole di Wiener-Hopf (B10) dove entrambe
i
fattori possono avere zeri di modulo unitario. Risolutori di equazioni
polinomiali saranno studiati in termini di iterazioni QR per matrici
companion
generalizzate (A5) che mantengano la struttura semi separabile (A2).
Si
studieranno rappresentazioni di polinomi nella base di Bernstein e le
loro
controparti matriciali con lo scopo di ottenere algoritmi efficienti
per
l'intersezione di curve di Bezier e superfici in CAGD (C7). Ci
affideremo a tecniche ibride numerico/simboliche e a strumenti di
geometria
proiettiva, computer algebra e analisi numerica. Si studieranno
algoritmi per
autovalori di matrici tridiagonali.
Per le equazioni matriciali al punto B9 si continua lo studio
di [BM],
[BGM1],[BGM2],[BG2] con particolare attenzione a
- generalizzare la tecnica di shift di [He,Meini,Rhee, SIMAX,23 2001/02]
- applicare la riduzione ciclica introdotta da G. Golub [BGN] e
adattata a
catene di Markov in [BM3],[BM4], per la risoluzione dell'equazione
algebrica di
Riccati;
- usare la fattorizzazione di Wiener-Hopf (B10) e l'iterazione di
Newton per il
calcolo della radice matriciale p-esima estendendo le tecniche di
[M4],[Ia].
- studiare le equazioni che modellizzano problemi di code.
Per problemi di minimo non vincolato B11 si proseguono gli
studi di [D],
[DFLZ], [DLZ] con l'analisi di condizioni sufficienti che garantiscono
la
convergenza dei metodi quasi-Newton in cui l'hessiano e' approssimato
con
matrici nell'algebra di Hartley [BF]. I problemi riguardano la
limitatezza
degli operatori coinvolti nel processo di minimizzazione. Si
analizzeranno
anche metodi per i minimi quadrati totali con applicazioni a blind
deblurring (A1,C3).
Si studieranno equazioni integrali in connessione con matrici multi
livello
semi infinite di Toeplitz (A7,A8) con applicazione a problemi di
scattering inverso, di acustica, remote sensing (C4) e in problemi di
astronomia (C9).
PARTE C:
- Riguardo a C1, i motori di ricerca sul web piu' recenti
calcolano
l'autovalore dominante di una matrice a blochi sparsa con correzione di
rango 1
[KHMG]. Lo scopo consiste nel progettare algoritmi piu' veloci per il
calcolo
del vettore di page rank.
- Si utilizzera' l'approcio Two-level quasi-Newton, implementato per
problemi
di remote sensing, complementato dall'uso degli strumenti della
"structure
matrix technology" per risolvere problemi di scattering inverso non
lineare nell'ingegneria (C4).
- Problemi inversi agli autovalori, non classici, per matrici
tridiagonali e
altre strutture correlate che includono matrici diagonali piu semi
separabili (A2),
sono stati usati come modelli in problemi di identificazione (C5)
in
ingegneria civile. Qui lo scopo e' utilizzare gli strumenti strutturati
per
risolvere sia i problemi teorici incontrati che quelli computazionali.
- La maggior parte di problemi di code incontrati in ingegneria e in
problemi
di reti e telecomunicazioni sono modellati da catene di Markov
descritte da
matrici semi infinite di Toeplitz. Si intendono proseguire gli studi
avviati e
considerare nuove applicazioni nella linea di [Anastasi, Lenzini,
Meini,
Perf.Eval. 29,1997].
Problemi di CAGD (C7) coinvolgono il calcolo di intersezioni di
curve e
superfici rappresentate in termini di polinomi di Bernstein. Molti
problemi si
riconducono a trattare matrici con struttura. Lo scopo e' applicare in
un
contesto numerico/simbolico gli strumenti sviluppati.
Reti neurali e apprendimento ottimale (C8) sono applicazioni di
problemi
di minimizzazione (B11).
PARTE D:
Per la parte D si intende proseguire la costruzione di matrici test (D1)
avviata nel progetto 2002-2003. Si propone di sviluppare un toolbox
specializzato per matrici strutturate per l'ambiente Matlab (D2),
uno
dei piu' diffusi strumenti software per il calcolo e la visualizzazione
scientifica. Le caratteristiche su cui si porra' particolare cura ed
attenzione
saranno: la facilita' d'uso, l'integrazione con l'ambiente Matlab e con
le sue
routine di calcolo intrinseche e l'ottimizzazione dei tempi di
elaborazione e
occupazione di memoria. Come primo obiettivo si intende focalizzare
l'attenzione su alcune tipologie di matrici strutturate e sugli
algoritmi di
base per la risoluzione di sistemi lineari, sia con metodi iterativi
precondizionati che con metodi diretti basati sulla displacement
structure.
L'obiettivo finale e' quello di costruire un software flessibile e
facilmente
estedibile, anche nel caso multiindice, ai nuovi algoritmi di calcolo.
Nel progetto sono programmate le seguenti collaborazioni alcune
iniziate nel
precedente progetto 2002-2003:
D. Calvetti and G. Saidel (Ohio),
G. Golub (Stanford)
A. Morassi (Udine)
D. Noutsos and P. Vassalos (Ioannina)
M. Pastorino (DIBE, Genova)
M. Van Barel, S. Van Huffel (Leuven)
G. Latouche (Bruxelles)
N. Higham, F. Tisseur (Manchester)
J. Winkler (Sheffield)
V. Pan (New York)
N. Rhee e K.Sorhaby (Kansas City)
L. Rodman and I.M. Spitkovsky, H.J. Woerdeman (College of William and
Mary)
C. Brezinski (Lille)
M. Tasche (Rostock, Germania)
Argomenti trattati dale unita' U1,U2, U3:
U1: A1 A2 __ A4 A5 A6 __ A8 A9
U2: A1 A2 A3 A4 A5 A6 A7 __ A9
U3: A1 ___________ A6 A7 A8 A9
U1: B1 B2 ______________ B8 B9 B10 B11 ___ ___ ___
U2: B1 B2 B3 B4 B5 B6 B7 _________________ B13 ___
U3: B1 _____ B4 _____ B7 _____ B10 ___ B12 B13 B14
U1: __ __ __ __ __ C6 C7 C8 __ __ __ D3
U2: C1 C2 C3 C4 C5 __ __ __ __ __ __ D3
U3: __ __ __ C4 __ __ __ __ C9 D1 D2 D3
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
diagonali+semiseparabili (A2,A5,B2). Riduzione di matrici simmetriche a
forma
semiseparabile (A2,B2).
U1,U2: Analisi di problemi ai minimi quadrati totali per matrici
strutturate
(B1).
U1,U2: Regolarizzazione tramite multigrid; algoritmi basati su tecniche
multigrid per la soluzione regolarizzata di sistemi malcondizionati,
applicazioni alle immagini (B6,B4,C3).
U2: Elaborazione di algoritmi per sistemi parametrici basati su metodi
proiettivi di Krylov e precondizionamento multilivello (A3,A7,B7,B13).
U2: Problemi inversi nell'imaging; estensione di famiglie di
precondizionatori
regolarizzanti, ricostruzione di immagini non negative, algoritmi per
sistemi
lineari generati dalla regolarizzazione alla Tikhonov, applicazioni al
problema
LBT (A1,B4,C3).
U2: Denoising tramite wavelet di immagini astronomiche; chopping e
nodding (nel
vicino infrarosso), PSF misurate in uso nel restauro classico,
ricostruzioni
sovra-iterate (B4,C3).
U2: Motori di ricerca web; analisi di strutture riscontrate in problemi
di
information retrieval (Google) e miglioramento dell'efficienza di
risoluzione,
mediante il calcolo dell'autovettore dominante di matrici sparse+rango
1 di
grandi dimensioni (C1).
U2,U3: Analisi del GMRES precondizionato, applicazioni a PDE in
problemi di
convezione-diffusione in domini a d dimensioni (B13,B5,A7). Uso del
GMRES e
sottospazi di Krylov per sistemi strutturati malcondizionati
(B13,A7,B4).
U3: Elaborazione, analisi e implementazione di software prototipale per
sistemi
semi-infiniti perturbati (A8,B1,D3).
U3: Analisi di strutture matriciali non convenzionali che intervengono
nell'analisi di propagazione della luce polarizzata in problemi di
astronomia
(C9).
U3: Creazione di un insieme di matrici test multilivello (multi-indice)
e
identificazine del loro condizionamento asintotico (A7,D1). Creazione
di un
toolbox Matlab contenente software per matrici strutturate (D2).
U1,U2,U3: Implementazione e validazione a livello prototipale di
algoritmi
elaborati nel progetto (D3).
Tra i risultati attesi figura l'organizzazione del convegno
internazionale
"Matrix Analytic Methods in Stochastic Models", Pisa Giugno 2005, e
l'organizzazione di workshop intermedi di coordinamento e di un
workshop finale
a conclusione del progetto.
Si prevede infine la creazione di pagine web del progetto, che
riportino gli
avanzamenti delle ricerche in continuo aggiornamento, e da cui i
risultati più
recenti in forma di report (file postscript o pdf) e il software
sviluppato
possano essere scaricati liberamente.
Unita' di ricerca impegnate: · Unità nº 1·
Unità
nº 2· Unità nº 3
2.5 Criteri
suggeriti per la valutazione globale e delle singole fasi
La valutazione del progetto va fatta in termini di
qualita' scientifica dei risultati ottenuti. Cio' puo' essere valutato
nei
seguenti modi:
1- mediante la qualita' delle riviste internazionali in cui i risultati
ottenuti verranno pubblicati;
2- in base alla diffusione internazionale dei risultati che puo' essere
rilevata in base al numero e all'importanza dei congressi
internazionali in cui
i risultati stessi vengono presentati.
3- La qualita' degli avanzamenti algoritmici puo' essere anche valutata
in
termini della riduzione del tempo di cpu richiesto dagli algoritmi
implementati
e in termini delle prestazioni numeriche.
4- Monitoraggio dinamico del progetto: come gia' scritto nella parte
2.4,
verranno svolte periodicamente riunioni del comitato di coordinamento
costituito dai responsabili delle unita' operative. A consuntivo di
ogni
incontro sarà prodotto un rapporto sullo stato di avanzamento
del progetto, che
includerà tutta la documentazione necessaria. Il suddetto
rapporto sarà
inserito in una pagina web del progetto.