Avanzamento

LEGENDA:
[*] = ancora da fare
[*] = in progress
[*] = obiettivo raggiunto
[*] = cancellato
[*] = obiettivo raggiunto nel 2002

Unità di Ricerca di Pisa

1) Polynomial Computations: calcolo di fattorizzazioni di Wiener-Hopf di polinomi di Laurent a coefficienti scalari e matriciali [BM-nsmc]; calcolo del reciproco di un polinomio di Laurent a coefficienti scalari/matriciali [BM-nsmc], [BGM-cm]; 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[BHM]. Analisi dei metodi di evaluation/interpolation e del metodo di Wilson [BaG]. Studio delle relazioni fra il problema della fattorizzazione di polinomi e la risoluzione di certe equazioni matriciali (successivo punto 3) [BHM], metodi basati sulle iterazioni funzionali [BG-hk].Applicazione della fattorizzazione di polinomi scalari e/o matriciali alla risoluzione di sistemi lineari con matrici Sylvester-like scalari e/o a blocchi [G-laa03]. 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) [FG], [VBM-1], [BFGM-tr]. Calcolo di zeri di polinomi mediante il calcolo di autovalori di matrici di Frobenius e companion generalizzate [BDG], [BGP-tr]. Metodi per problemi generalizzati agli autovalori per matrici tridiagonali [BGT].

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 [BG-tcs].

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

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 [BLM-book],NonSkipFree [BM-nsmc] e Tree [BLM].

6) Problemi di minimo non vincolato e minimi quadrati. Uso di algebre di matrici con struttura nella minimizzazione non vincolata di funzioni non lineari [DFLZ], [D], [DFZ-1], [DLZ]. Applicazione a processi di apprendimento su reti neuronali supervisionate. Algoritmi veloci e stabili per problemi ai minimi quadrati totali con struttura [LMV].

7) Implementazione di software prototipo e validazione di algoritmi.

• eigensolve  eigensolve.tgz
• Inverse Power Solve ips.tgz

Unità di Ricerca di Genova

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 L¹ 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.
 

Unità di Ricerca di Cagliari

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 [MRS1,MRR,EM,M1].

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' [MRSW,MRS2,MR,LMR]. 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 [BRZRS, RST,RT2,MRST]. 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 [MNS,MS]. 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 [RT1,R].
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. [MP1,MP2,M2]

OBIETTIVI MODELLO A – STATO DI AVANZAMENTO

Obiettivi principali sono:

-A-Analisi di proprieta' strutturali, algebriche, analitiche, spettrali e computazionali delle piu' importanti classi di matrici con struttura (incluse Toeplitz e Hankel -like, finite, semi e bi -infinite, semiseparabili, a banda, con elementi scalari o a blocchi, mono e multilivello, con strutture ricorsive e semiseparabili), che intervengono in problemi di matematica teorica e applicata.

B-Uso di tali proprieta' per individuare metodologie numeriche generali per il disegno e l'analisi di algoritmi efficienti di risoluzione di problemi computazionali con particolare attenzione rivolta a problemi di natura applicativa e di calcolo scientifico su grande scala.

-C-Applicazione degli algoritmi individuati per la risoluzione di alcuni specifici problemi di carattere teorico e applicativo.

-D-Creazione di software prototipo per il confronto e la validazione degli algoritmi analizzati;

In particolare per ogni obiettivo sopraelencato l'attivita' di ricerca si articola nei seguenti punti:

A-Aspetti teorici

A1 Studio di algebre di matrici strutturate in relazione alle trasformate veloci e a spazi lineari piu' generali delle algebre trigonometriche; studio di nuovi operatori displacement e di formule di inversione per il disegno di precondizionatori efficienti.

Studio  di proprieta' dei precondizionatori ottimali in algebre. Studio di precondizionatori in algebre per matrici multilivello. Estensione del risultato di Serra-Tyrtyshnikov sull'impossibilita' di ottenere cluster forti con l'algebra delle circolanti multilivello. Rango approssimato di dislocamento e inversione con metodo di Newton.

A2 Analisi spettrale e strutturale di successioni di matrici Toeplitz-like mono e multi-livello, individuazione di formule distribuzionali tipo Szego. Estensione dei risultati a funzioni a valori matriciali (matrici a blocchi). Estensione del concetto di successione "localmente Toeplitz" al caso multilivello, relazioni con la discretizzazione di PDE (punto C3). Estensione della classe delle funzioni test nei risultati distribuzionali per successioni di Toeplitz.

A3 Studio del condizionamento asintotico per successioni di matrici. Studio di matrici Laplaciane di Grafo. Studio del condizionamento strutturato per matrici con struttura di dislocamento (Cauchy e Vandermonde-like, Pick).

A4 Connessioni fra la teoria degli operatori (secondo l'approccio di Boettcher e Silbermann [BS]) e l'algebra lineare asintotica, allo scopo di facilitare la comunicazione delle competenze dei due settori in cui viene a volte usato un diverso linguaggio matematico.

A5 Fattorizzazioni spettrali di matrici multi-indice di Toeplitz a blocchi in algebre di Wiener con peso. Studio del comportamento asintotico dei coefficienti della fattorizzazione. Estensione dei risultati al caso multi-indice e a blocchi. Fattorizzazione e inversione di polinomi di Laurent mono e multivariati. Applicazione al disegno di  algoritmi per sistemi semi-infiniti di Toeplitz multilivello (punto B3) e al precondizionamento(punto B1).

A6 Studio di problemi diretti e inversi di autovalori per matrici semiseparabili, fattorizzazione QR di matrici con struttura Cauchy-like. Relazione con funzioni razionali ortogonali.

B- Metodologie numeriche

B1 Disegno ed analisi di precondizionatori per strutture multilivello. Analisi di precondizionatori per gradiente coniugato basati sul concetto di matrice localmente Toeplitz (punto A2) e applicazione a discretizzazione di PDE ellittiche con coefficienti non costanti e su domini arbitrari(punto C3). Analisi di precondizionatori basati su fattorizzazioni di Wiener-Hopf (punto A5).

Studio del precondizionatore superottimale di Tyrtyshnikov, analisi delle proprieta' regolarizzanti, applicazione al restauro di immagini (punto C1). Studio della risoluzione di problemi mal posti con matrici a piω livelli mediante precondizionamento superottimale. Precondizionatori basati su inverse approssimate e fattorizzazioni incomplete di sistemi con shift che utilizzano anche le strutture. Applicazione al calcolo di autovalori di matrici con struttura di dislocamento mediante flussi isospettrali e tecniche di omotopia.

B2 Disegno e analisi di metodi multigrid per la risoluzione di sistemi strutturati multilivello con attenzione a matrici in algebre e di Toeplitz + diagonale. Applicazioni a problemi di restauro di immagini (punto C1).

B3 Metodi per sistemi infiniti di Toeplitz mono e multilivello a elementi scalari e a blocchi. Metodi basati sulla teoria dei polinomi matriciali, e il band extension. Uso delle fattorizzazioni spettrali. Uso del metodo di riduzione ciclica e di Graeffe applicato a polinomi di Laurent. Caso di matrici di Toeplitz perturbate. Applicazione alle PDE (punto C3) e equazioni integrali.

B4 Equazioni matriciali. Analisi di equazioni di tipo Riccati, di tipo polinomiale, e definite da serie di potenze. Sviluppo di tecniche di deflazione, di metodi basati sulle matrici di Frobenius, di tecniche evaluation interpolation e dei risultati in A5,B3 e B5.

B5 Polynomial computations. Uso dei risultati in A5,B3,B4 per il disegno di algoritmi per la fattorizzazione di polinomi e serie di potenze. Estensione a matrix polynomials e polinomi multivariati. Relazioni fra il problema della fattorizzazione di polinomi e la risoluzione di equazioni matriciali (B4). Metodo di Wilson e uso di evaluation interpolation. Fattorizzazione ricorsiva di polinomi. Applicazione a risoluzione di sistemi lineari con matrici Sylvester-like scalari e/o a blocchi e alla fattorizzazione QR di matrici Cauchy-like (punto B6).

B6 Metodi per il calcolo della fattorizzazione QR di matrici Cauchy-like e applicazioni a problemi di approssimazione razionale (punto C5). Applicazioni a equazioni integrali con nucleo semiseparabile e risoluzione di sistemi lineari con matrici semiseparabili e correzione a banda.

C-Applicazioni specifiche

C1 Restauro di immagini e problemi inversi. Analisi di strutture e applicazione dei risultati ai punti A1,A2,B1,B2 per ricostruzione di immagini LBT. Uso dei precondizionatori ottimali. Uso di tecniche chopping e nodding per sottrarre il rumore di fondo dalle immagini all'infrarosso.

C2 Equazioni integrali. Risoluzione di equazioni con nuclei strutturati connesse con l'identificazione di disomogeneitΰ del sottosuolo con metodologie acustiche e sismiche mediante A2,A5,B3. Equazioni dello scattering inverso, in acustica e in meccanica quantistica.

C3 PDE. Applicazione di A2,A5 e B1 alla risoluzione numerica di PDE. Equazione di Helmholtz su una striscia sottile illimitata, (propagazione nelle guide d'onda). Disegno di precondizionatori ad hoc per discretizzazioni di PDE con FD e FE.

C4 Risoluzione numerica di catene di Markov. Analisi di strutture di matrici nei modelli QBD, BMAP, PH1, NSF e Tree, strutture su piu' livelli, applicazione di A1,B4,B5.

C5 Approssimazione e quadratura: distribuzione limite di zeri di polinomi ortogonali. Problemi di interpolazione polinomiale e razionale (Nevanlinna-Pick) mediante strutture Cauchy, Pick e Vandermonde. Quadratura numerica di funzioni multivariate non regolari note dai coefficienti di Fourier. Interpolazione approssimata tramite funzioni razionali mediante gli strumenti in B6.

C6 Problemi di minimo non vincolato: uso di algebre di matrici per l'approssimazione dell'Hessiano in problemi di minimo quasi Newtoniani, applicazione alla minimizzazione della funzione errore di reti neuronali. Problemi di minimi quadrati totali con struttura.

D- Software

D1 Implementazione e confronto numerico degli algoritmi.

D2 Creazione di un insieme di matrici test.

D3 Creazione di una pagina web con link al software e ai test effettuati e ai risultati raggiunti.

D4 Creazione di software per fattorizzazione ricorsiva di polinomi.

D5 Creazione di software per i metodi multigrid.

Classificazione di nuove algebre di matrici di tipo Hartley con le conseguenti formule di inversione. Possibilita' d'uso come precondizionatori. Possibilita' di uso in problemi di minimo non vincolato e in reti neuronali.
 

Disegno di nuovi precondizionatori efficienti che scaturiscono sia dalle analisi in A1 di nuove algebre di matrici sia dall'analisi spettrale asintotica in A2, sia dalle fattorizzazioni di matrici infinite in A5, con applicazioni efficaci alla risoluzione mediante differenze finite di equazioni ellittiche con condizioni al contorno arbitrarie, con realizzazione di software e validazione numerica.
 

Risultati di convergenza per il metodo multigrid nell'ambito di algebre di matrici, e disegno di metodi multigrid efficienti per algebre bi-circolanti. Studio dell'algebra dei coseni, possibilita' di costruire un metodo multigrid per tale algebra.
 

Disegno di precondizionatori con caratteristiche regolarizzanti basati sugli operatori superottimali, applicazione alla risoluzione di problemi di restauro di immagini. Migliore comprensione delle proprieta' degli operatori superottimali in relazione al precondizionamento regolarizzante. Migliori algoritmi per il modello LBT (Large Binocular Telescope) di restauro di immagini.
 

Risultati di convergenza dei coefficienti di fattorizzazioni spettrali di matrici semi-infinite di Toeplitz multilivello a blocchi. Nuovi algoritmi asintoticamente e effettivamente veloci per il calcolo delle fattorizzazioni spettrali. Nuovi algoritmi asintoticamente e effettivamente veloci per la risoluzione di sistemi finiti e semi-infiniti di Toeplitz. Nuovi algoritmi asintoticamente veloci per sistemi semi-infiniti multilivello di Toeplitz con perturbazioni.
 

Maggior chiarimento delle relazioni fra operazioni con polinomi di Laurent e matrici di Toeplitz. Nuovi algoritmi asintoticamente e effettivamente veloci per l'inversione di polinomi di Laurent. Maggior chiarimento fra relazioni fra operazioni con polinomi di Laurent e equazioni matriciali. Algoritmi asintoticamente e effettivamente veloci per la risoluzione di equazioni matriciali polinomiali e definite da serie di potenze.
 

Miglior comprensione del problema della fattorizzazione di polinomi in relazione all'uso di matrici con struttura, in termini di condizionamento e di convergenza.
 

Algoritmi piu' efficienti in termini di velocita' e precisione per risolvere classi di problemi di teoria delle code, in particolare problemi caratterizzati da strutture definite per ricorrenza (Tree structures).
 

Fra i risultati attesi e' incluso la creazione di pagine web relative al progetto con puntatori ai vari algoritmi implementati, la costituzione di un insieme di matrici test, la creazione di software specifico per la fattorizzazione ricorsiva di polinomi e per metodi multigrid.