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
C) Applicazioni a problemi specifici della Matematica Applicata
D) Stesura di codici software prototipali
|
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
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.
|