MINISTERO DELL'UNIVERSITÀ E DELLA RICERCA SCIENTIFICA E TECNOLOGICA
PROGRAMMI DI RICERCA ANNO 2002
COMPITI E SUDDIVISIONE DELLE UNITÀ DI RICERCA



 
 
 Obiettivo della Ricerca 

Gli obiettivi principali del progetto si articolano nelle seguenti 4 linee generali:

-A- Analisi. 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, matrici semiseparabili, matrici a banda); 

-B- Algoritmi. Utilizzare tali proprieta' al fine di individuare metodologie numeriche generali per il disegno e l'analisi di algoritmi efficienti di risoluzione di problemi di interesse rilevante; 

-C- Applicazioni. Applicare i risultati a problemi di natura applicativa e di calcolo scientifico su grande scala;

-D- Software. Realizzare un'implementazione prototipale degli algoritmi individuati e la loro validazione sperimentale. 

Piu' specificamente:

-A- Analisi spettrale asintotica di successioni di matrici e teoria degli operatori; estensione di matrici localmente Toeplitz; analisi astratta di precondizionatori nel caso multilivello; algebre di matrici e trasformate discrete; studio di condizionamento asintotico e strutturato; analisi di fattorizzazioni spettrali in algebre pesate e per matrici Toeplitz multi-indice e a blocchi; problemi diretti e inversi agli autovalori per matrici semiseparabili, relazioni con funzioni razionali ortogonali. 

-B- Disegno e analisi di precondizionatori, studio di proprieta' regolarizzanti; algoritmi per sistemi lineari infiniti di Toeplitz con perturbazioni compatte; metodi PCG e metodi multigrid. Metodi per il calcolo di autovalori, equazioni matriciali, fattorizzazione di polinomi, fattorizzazioni spettrali; calcolo di zeri di polinomi. Metodi per l'iterazione QR di matrici di Frobenius, Cauchy e semiseparabili. Metodi per l'approssimazione razionale. 

-C- Applicazione degli algoritmi a problemi di PDE (discretizzate mediante FD e FE), risoluzione di equazioni integrali con nucleo strutturato, applicazioni a problemi di geofisica, acustica, meccanica quantistica. Applicazioni a restauro di immagini: immagini LBT e all'infrarosso. Applicazioni a problemi di teoria delle code e risoluzione di catene di Markov. Problemi di approssimazione e quadratura e problemi di interpolazione razionale e polinomiale. Applicazioni a problemi di minimo non vincolato, e a problemi di minimi quadrati con struttura; applicazioni al disegno di reti neuronali. 

-D- implementazione e confronto numerico di algoritmi, creazione di un insieme di matrici test, software per metodi multigrid, creazione di pagina web con link al software e con i risultati raggiunti.
 

Innovazione rispetto allo stato dell'arte nel campo

Si ritiene che l'analisi delle proprieta' specifiche di un problema computazionale, condotta in termini di analisi di strutture matriciali, possa portare ad avanzamenti algoritmici importanti e innovativi. 
L'innovazione e' principalmente costituita da una analisi sistematica e qualificata delle proprieta' di struttura, condotta integrando le diverse competenze matematiche algoritmiche e numeriche delle 3 unita' scientifiche. 

Si prevedono avanzamenti a livello teorico, nel disegno e nell'analisi di algoritmi e nella applicazione dei risultati raggiunti; in particolare nei settori quali la risoluzione di problemi modellizzati dalla teoria delle code mediante catene di Markov, di elaborazione di immagini, di geofisica applicata, acustica e meccanica quantistica. Infatti l'uso delle metodologie di algebra lineare numerica strutturata in problemi quali la risoluzione di equazioni integrali, differenziali, matriciali e di catene di Markov costituisce un approccio positivamente collaudato dai ricercatori delle 3 unita' scientifiche che si ritiene debba ancora produrre risultati particolarmente innovativi. 

Al livello algoritmico si prevedono diversi miglioramenti di risultati esistenti e contributi fortemente innovativi. Fra questi, nuovi algoritmi a complessita' quadratica per il calcolo di autovalori di matrici di Frobenius mediante metodo QR; nuovi algoritmi efficienti per il calcolo di autovalori generalizzati di matrici tridiagonali, e per il trattamento di matrici semiseparabili; nuovi metodi per la fattorizzazione QR di matrici Cauchy-like e relazioni con la teoria delle funzioni ortogonali razionali. Risultati innovativi sono attesi anche nella risoluzione di sistemi multilivello mediante l'integrazione fra metodi multigrid e precondizionatori a banda. Infatti per questa classe di problemi i classici precondizionatori in algebre non permettono di raggiungere l'ottimalita' della convergenza.
 

Criteri di verificabilità

1) Produzione scientifica della ricerca valutata sia in termini della quantita' di contributi dati che dalla qualita' delle riviste in cui essi vengono diffusi.

2) Diffusione internazionale e visibilita' dei risultati, valutati in termini di numero e importanza dei congressi internazionali in cui i risultati vengono presentati.

3) Avanzamenti algoritmici. La verificabilita' degli avanzamenti e' data dalla riduzione di complessita' raggiunta e/o dalla riduzione del tempo di cpu richiesto dagli algoritmi in una loro implementazione mediante calcolatore. Un altro parametro di valutazione e' la stabilita' numerica.

4) Monitoraggio dinamico. A consuntivo di ogni incontro verra' riportato sulla pagina web del progetto il rapporto sullo stato di avanzamento del progetto.

Unità di Ricerca
 
1]  Unità di       Universita' di PISA
     Responsabile DARIO ANDREA BINI
     Compito

Si intendono individuare, studiare e confrontare algoritmi efficienti per le seguenti classi di problemi:
 

1) Polynomial Computations: calcolo di fattorizzazioni di Wiener-Hopf di polinomi di Laurent a coefficienti scalari e matriciali; calcolo del reciproco di un polinomio di Laurent a coefficienti scalari/matriciali; applicazione alla fattorizzazione di polinomi rispetto alla circonferenza unitaria e rispetto all'asse immaginario. Relazioni fra il metodo di Graeffe per polinomi e il metodo della riduzione ciclica, e le possibili estensioni a matrix polynomials. Analisi dei metodi di evaluation/interpolation e del metodo di Wilson. Studio delle relazioni fra il problema della fattorizzazione di polinomi e la risoluzione di certe equazioni matriciali (successivo punto 3), metodi basati sulle iterazioni funzionali. Applicazione della fattorizzazione di polinomi scalari e/o matriciali alla risoluzione di sistemi lineari con matrici Sylvester-like scalari e/o a blocchi. Metodi per il calcolo di fattorizzazioni QR di matrici Cauchy-like e connessioni con problemi spettrali diretti e inversi per matrici semiseparabili, costruzione di insiemi di funzioni razionali ortogonali (in collaborazione con l'Unita' 2). Calcolo di zeri di polinomi mediante il calcolo di autovalori di matrici di Frobenius e companion generalizzate. Metodi per problemi generalizzati agli autovalori per matrici tridiagonali. 

2) Fattorizzazione di matrici di Toeplitz a elementi scalari e a blocchi. Applicazione dei risultati del punto 1 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). Individuazione e analisi di metodi efficienti per la fattorizzazione di matrici Toeplitz-like con elementi su anelli con applicazioni a problemi di computer graphics. 

3) Risoluzione di equazioni matriciali. Equazioni di tipo Riccati, di tipo polinomiale e definite da serie di potenze; tecniche di deflazione per accelerare la convergenza di schemi noti e disegnare nuovi metodi basati sull'uso delle proprieta' delle matrici di Frobenius. Problema della risoluzione di equazioni matriciali e la fattorizzazione di polinomi. Calcolo di radici quadrate di matrici. 

4) Risoluzione di sistemi lineari finiti con struttura. Studio di precondizionatori per gradiente coniugato (in collaborazione con l'Unita' 3). Metodi multigrid per matrici di Toeplitz mono e multilivello (in collaborazione con l'Unita' 2). 

5) Problemi di teoria delle code. Analisi di strutture di matrici nei modelli QBD, BMAP, PH1, NonSkipFree e Tree.

6) Problemi di minimo non vincolato e minimi quadrati. Uso di algebre di matrici con struttura nella minimizzazione non vincolata di funzioni non lineari. Applicazione a processi di apprendimento su reti neuronali supervisionate. Algoritmi veloci e stabili per problemi ai minimi quadrati totali con struttura. 

7) Implementazione di software prototipo e validazione di algoritmi. 


2]  Unità di       Universita' degli Studi di GENOVA
     Responsabile FABIO DI BENEDETTO
 
     Compito

A) Analisi di successioni di matrici
A1) Convergenza dei metodi iterativi
La discretizzazione di alcune PDE porta a sistemi lineari Hermitiani non definiti o non Hermitiani. Si prevedono per questi casi risultati asintotici e di localizzazione sullo spettro di strutture precondizionate e non. 
A2) Algebra lineare asintotica
a) Estensione della nozione di successione Localmente Toeplitz al caso multilivello.
b) Estensione della classe delle funzioni Test nei risultati distribuzionali per successioni di Toeplitz.
c) Studio del condizionamento classico di matrici Laplaciane di Grafo e del condizionamento strutturato per matrici con struttura di dislocamento (Cauchy, Vandermonde). 
A3) Relazioni con la teoria degli operatori
a) connessioni tra i problemi infinito dimensionali espressi nel linguaggio di Teoria degli Operatori e problemi di Algebra Lineare Asintotica. 
b) inquadramento dei metodi iterativi precondizionati nella teoria analitica classica degli operatori di regolarizzazione per problemi mal posti. 
A4) Risultati astratti sul precondizionamento multilivello
Caratterizzazione topologica dell'insieme dei simboli f per cui la successione di Toeplitz associata non ammette precondizionatori superlineari o ottimali in una data successione di algebre. 

B) Analisi e Sintesi di algoritmi ad hoc per matrici strutturate
B1) Metodi multigrid
Analisi e sintesi di algoritmi tipo multigrid per la risoluzione di sistemi lineari strutturati multilivello con attenzione a matrici in Algebre e Toeplitz Multilivello. 
B2) Precondizionamento di sistemi lineari strutturati
Proprietà regolarizzanti del precondizionatore "superottimale" di Tyrtyshnikov e dei precondizionatori "filtranti" da esso derivati. Proposta di un nuovo precondizionatore per sistemi lineari shiftati, legato a una modifica delle inverse approssimate in forma fattorizzata. 
B3) Tecniche di continuazione per il calcolo di autovalori
Studio di fattibilità per due tecniche numeriche effettivamente veloci per calcolare tutti gli autovalori di una matrice di Toeplitz specifiche: i flussi isospettrali e i metodi di omotopia. 
B4) Altre strutture
Costruzione di algoritmi veloci e stabili per la fattorizzazione QR di matrici Cauchy-like. Studio di proprietà spettrali e computazionali delle matrici diagonali-più-semiseparabili. 

C) Applicazioni a problemi specifici della Matematica Applicata
C1) Elaborazione di immagini
a) individuazione di metodi numerici particolarmente efficienti per risolvere il problema LBT;
b) prosecuzione dello sviluppo di algoritmi veloci di ricostruzione SPECT basati sul modello a pixel naturali.
C2) Sistemi lineari e PDE
a) Problemi ellittici e semi-ellittici
Analisi e sintesi di algoritmi veloci ad hoc per la risoluzione di sistemi lineari strutturati multilivello, con attenzione alle discretizzazioni con FD, FE, Collocazione di PDE con coefficienti non costanti e su domini rettangolari e non. Analisi di precondizionatori per il gradiente coniugato e delle relative proprietà di clustering ed equivalenza spettrale. 
b) Problemi di evoluzione
Studio di precondizionatori circolanti a blocchi per sistemi lineari non simmetrici legati ai metodi ai limiti per PDE dipendenti dal tempo. 
C3) Approssimazione e quadratura
a) determinazione della distribuzione limite per gli zeri di successioni di polinomi ortogonali con coefficienti di ricorrenza periodici dipendenti da parametro; 
b) quadratura di funzioni di classe L1 e analisi numerica dell'immagine essenziale di funzioni semplicemente misurabili tramite formule ergodiche;
c) analisi di algoritmi per risolvere problemi di interpolazione polinomiale e razionale basati sulle strutture Cauchy, Pick e Vandermonde. 

D) Stesura di codici software prototipali
a) implementazione degli algoritmi multigrid su problemi applicativi di dimensioni realistiche;
b) validazione numerica dei metodi avanzati introdotti per i problemi LBT e SPECT.
 


3]  Unità di       Universita' degli Studi di CAGLIARI
     Responsabile SEBASTIANO SEATZU
  
     Compito

L'unita' di Cagliari, svolgerà le proprie ricerche sulle seguenti tematiche:

1) Analisi di matrici infinite strutturate di tipo multi-indice. Tali ricerche fondamentalmente riguarderanno la fattorizzazione spettrale delle matrici multi-indice di Toeplitz a blocchi in algebre di Wiener con peso. Questo tipo di risultati esiste nel caso scalare. L'estensione al caso multiindice delle metodologie sviluppate nel caso monoindice non è tuttavia effettuabile perché, oltre a non esistere un equivalente della teoria dei polinomi matriciali multindice, non vale la compattezza delle matrici semi-infinite di Hankel. 

2) Risoluzione di sistemi lineari infiniti con matrici strutturate e loro perturbazioni. In tale ambito, relativamente ai sistemi lineari semi-infiniti con matrici mono-indice di Toeplitz a blocchi , ci si propone di effettuare un'analisi comparativa sull'efficacia dei metodi esistenti, in funzione delle proprietà di decadimento degli elementi della matrice del sistema e della complessita'. In via prioritaria, essa riguarderà il metodo, basato sulla teoria dei polinomi matriciali, il band extension method, il metodo di programmazione semidefinita e i metodi basati sulla risoluzione di equazioni matriciali quadratiche. 

3) Risoluzione numerica dei sistemi lineari finiti con matrici strutturate malcondizionate. Anche se la teoria e il calcolo numerico delle soluzioni dei sistemi finiti con matrici strutturate verranno principalmente studiati dalle altre unita', localmente ci si propone di studiare il caso particolare dei sistemi finiti con matrici strutturate mal condizionate, settore nel quale esistono specifiche competenze locali. L'unita' locale si propone inoltre di generalizzare al caso multiindice i metodi sviluppati per matrici circolanti. 

4) Applicazione dei risultati alla risoluzione numerica di equazioni integrali con nuclei strutturati. Poiché i sistemi lineari con matrici strutturate rappresentano l'analogo discreto delle equazioni integrali con nuclei strutturati, l'unità locale si propone di estendere alle equazioni integrali alcuni risultati recentemente ottenuti sui sistemi lineari di Toeplitz e loro perturbazioni. A tale scopo ci si propone di stabilire una sinergica collaborazione tra esperti di teoria degli operatori e analisti numerici, parzialmente già attuata dall'unità di Cagliari. Anche le recenti ricerche sulla teoria del campionamento in spazi di Hilbert con nucleo di 
riproduzione sembrano utili a tale scopo. L'unita' si propone, inoltre, di sviluppare metodologie di calcolo per sistemi lineari strutturati fortemente mal condizionati mediante l'applicazione di algoritmi veloci basati sulla struttura di displacement a metodi di regolarizzazione alla Tikhonov. 
Un'applicazione di interesse strettamente numerico, che si pensa di poter realizzare, riguarda la generazione di precondizionatori per matrici di notevoli dimensioni, sia scalari sia a blocchi, che siano perturbazioni di matrici di Toeplitz definite positive L'unità locale si propone infine di applicare i risultati teorici e numerici sulle equazioni integrali alla risoluzione di problemi tipici della geofisica applicata e dello scattering inverso in acustica e in meccanica quantistica. 

5) Sviluppo di software prototipale. Ci si propone infine di ampliare e di perfezionare, nelle diverse fasi operative, il software finora sviluppato per la risoluzione dei sistemi di Toeplitz semi-infiniti e loro perturbazioni.