Area Scientifico Disciplinare: Scienze Matematiche

Analisi di strutture di matrici: metodi numerici e applicazioni

Matrici con struttura intervengono in molti problemi di matematica pura e applicata, nella ricerca scientifica e tecnologica e in problemi di matematica industriale. Le strutture presenti nel modello matematico traducono in chiave algebrica e formale proprieta' specifiche del problema allo studio. L'evidenziazione, lo studio e l'analisi delle proprieta' di struttura costituisce un passo fondamentale per la costruzione di metodi di risoluzione efficienti di problemi laddove i metodi generali risultano inapplicabili per le elevate dimensioni.
Il progetto ha lo scopo di analizzare le proprieta' algebriche analitiche e computazionali di classi di matrici con struttura al fine di individuare algoritmi di risoluzione efficienti di diversi problemi computazionali. Particolare interesse e' rivolto alle strutture Toeplitz-like Hankel-like e definite da operatori di tipo dislocamento; in particolare matrici di Toeplitz mono e multilivello, ad elementi scalari e a blocchi, finite e infinite. Particolare interesse e' rivolto allo studio di operatori displacement e ad algebre di matrici legate a trasformate veloci, a proprieta' spettrali asintotiche e al disegno di precondizionatori, allo studio di metodi multigrid, alla analisi di strutture derivanti dalla discretizzazione di operatori differenziali, alle proprieta' delle fattorizzazioni spettrali in algebre di Banach pesate.
I problemi computazionali principali riguarderanno la risoluzione di sistemi lineari finiti, semi-infiniti e bi-infiniti, il calcolo di fattorizzazioni matriciali, il calcolo di autovalori, la risoluzione di equazioni matriciali con blocchi strutturati, fattorizzazioni spettrali. I risultati ottenuti saranno applicati alla risoluzione di problemi di teoria delle code, a problemi di algebra computazionale (in particolare alla fattorizzazione di polinomi mono e multi variati), alla risoluzione numerica di equazioni integrali e differenziali, all'analisi di reti neuronali, al restauro di immagini, alla risoluzione di problemi di ottimizzazione non vincolata.
Il progetto intende realizzare software prototipo per confrontare e validare gli algoritmi individuati nella ricerca, affrontare specifici problemi aplicativi quali imaging LBT, e studiare la realizzabilita' di algoritmi multiprecisione per la fattorizzazione ricorsiva di polinomi e per risolutori multigrid.

MATRICI DI TOEPLITZ ; MATRICI CON STRUTTURA ; RANGO DI DISLOCAMENTO ; FATTORIZZAZIONI SPETTRALI ; PRECONDIZIONAMENTO PER MATRICI STRUTTURATE ; RISOLUZIONE NUMERICA DI CATENE DI MARKOV ; RESTAURO DI IMMAGINI ; CALCOLO POLINOMIALE ; MULTIGRID PER MATRICI STRUTTURATE

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, 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 e gli operatori di dislocamento, 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. BINI D.A., B. MEINI. (2001). Approximate displacement rank and applications.

In V. OLSHEVSKY. Structured matrices in mathematics, computer science, and engineering, II. (vol. 281, pp. 215--232). Contemporary Mathematics. PROVIDENCE ,RI: American Mathematical Society (UNITED STATES).
2. BINI D.A., GEMIGNANI L., MEINI B. (2001). Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations. NUMERISCHE MATHEMATIK. vol. 89 (2001), no. 1, pp. 49--82.
3. 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.
4. 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.
5. BINI D.A., B. MEINI. (1996). On the solution of a nonlinear matrix equation arising in queueing problems. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. vol. 17, pp. 906-926.

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.

Da diversi anni lo studio di matrici con struttura si e' rivelato un punto cardine dell'algebra lineare numerica e un mezzo per un'indagine trasversale di varie problematiche in diversi settori dell'analisi numerica, del calcolo scientifico, di matematica applicata.
Infatti, matrici con struttura intervengono in molti problemi di matematica pura e applicata, in molti settori della ricerca scientifica e tecnologica e in problemi di matematica industriale. Le strutture presenti nel modello matematico traducono in chiave algebrica e formale proprieta' specifiche del problema allo studio. L'evidenziazione, lo studio e l'analisi delle proprieta' di struttura costituisce un passo fondamentale per la costruzione di metodi di risoluzione efficienti di problemi laddove i metodi generali risultano inapplicabili per le elevate dimensioni e per l'alta complessita'.

Per le caratteristiche ricorrenti di molti modelli matematici nelle diverse applicazioni, certe strutture si incontrano piu' frequentemente di altre. In particolare cio' accade per la struttura "Toeplitz". Matrici di Toeplitz, cioe' matrici che hanno elementi costanti lungo le diagonali, si incontrano in un'ampia varieta' di problemi in matematica pura ed applicata ed in ingegneria. La struttura Toeplitz riflette l'invarianza sotto traslazione soddisfatta da certi oggetti matematici che modellizzano il problema (nuclei integrali, operatori differenziali, probabilita' di cambiamento di stato, polinomi e serie di potenze, ecc.) Spesso la struttura Toeplitz si accompagna ad altre strutture, tipo strutture a banda o Hessenberg mutuate dall'azione locale o semi locale degli operatori lineari coinvolti. Altre importanti strutture correlate sono le strutture Hankel, Cauchy, Frobenius, Vandermonde, Sylvester, Bezout, Loewner, semiseparabili ecc.
 

L'interesse alle problematiche legate alle matrici con struttura, gia' presente negli anni '60 [GS] e '70 con i lavori di Trench [Tr] e di Gohberg-Semencul [GoS] sui metodi diretti per matrici di Toeplitz e implicitamente con i metodi per la risoluzione del problema discreto di Poisson sul rettangolo, si e' via via accresciuto negli anni successivi grazie alle ricerche di alcuni gruppi scientifici. Negli ultimi anni un forte interesse a livello internazionale si e' coagulato attorno alle problematiche legate all'analisi di strutture di matrici e un ampia letteratura si e' consolidata sui problemi matematici correlati.
I risultati ottenuti negli ultimi 10 anni nel settore dei ricerca delle matrici con struttra hanno portato a grossi avanzamenti algoritmici con forti riduzioni dei tempi di calcolo nella risoluzione di diversi importanti problemi; una sintesi dei risultati piu' recenti e' riportata in [BTY], [KS], [O].
I problemi computazionali piu' interessanti che coinvolgono forti proprieta' di struttura e in cui sono stati ottenuti importanti risultati computazionali, provengono da diversi settori matematici applicativi e teorici quali ad esempio:
 

--Teoria delle code:
Molti problemi di teoria delle code sono modellizzati da catene di Markov di tipo G/M/1 e M/G/1 in cui la particolare tipologia del problema si riflette in una struttura di Toeplitz a blocchi in forma di Hessenberg delle matrici stocastiche coinvolte [Ne], [LR]. Ulteriori peculiarita' del modello (presenza di buffers, modelli PH1, QBD, Non-Skip-Free ecc.) producono ulteriori strutture (di Kronecker, di Frobenius, tridiagonali a blocchi) [BMR]. Le matrici possono essere finite, semi-infinite, o bi-infinite in relazione alla indicizzazione degli stati. Le accelerazioni nei tempi di calcolo ottenute con algoritmi basati su proprieta' di struttura raggiungono fattori di alcune centinaia [BM3],[BM4],[KS],[M1].
 

--Equazioni differenziali e integrali:
La discretizzazione numerica di equazioni differenziali spesso conduce alla risoluzione di sistemi lineari di grandi dimensioni con matrici strutturate (ad esempio, l'uso delle differenze finite conduce a matrici di Toeplitz qualora l'operatore differenziale sia lineare con coefficienti costanti). Problemi multidimensionali (equazioni alle derivate parziali) conducono a matrici multilivello o multiindice. Domini illimitati conducono a matrici con dimensioni infinite. Operatori con coefficienti non costanti o discretizzazioni non uniformi conducono a matrici con strutture piu' riposte quali strutture Toeplitz-like o localmente Toeplitz [ST]. Analoghe considerazioni valgono per la discretizzazione sul semispazio di una equazione integrale, il cui nucleo sia di tipo convolutorio oppure sia una sua perturbazione in un dominio limitato. I metodi basati sull'analisi di strutture (precondizionamento e multigrid) hanno fortemente ridotto il numero delle iterazioni necessarie a risolvere i sistemi lineari specifici [ST], [FS], [CN].
 

--Elaborazione di immagini:
In molte applicazioni e' richiesta la ricostruzione di un'immagine a partire da dati acquisiti e corrotti dal rumore. Il modello matematico che descrive il processo di acquisizione presenta spesso simmetrie e invarianze che conducono ad un modello discretizzato che coinvolge matrici di Toeplitz o loro approssimazioni [BeBo], [BDB]. Tipicamente cio' avviene quando la PSF (point Spread Function) e' invariante spazialmente. Grossi avanzamenti algoritmici sono stati raggiunti con l'uso dei precondizionatori in algebre stutturate [CN],[KS],[NPPT].
 

--Equazioni matriciali:
Equazioni matriciali si incontrano in un'ampia varieta' di settori di ricerca che include la teoria del controllo, programmazione dinamica, filtraggio stocastico, statistica e teoria delle code [HK] e un'ampia letteratura esiste per classi specifiche di problemi quali le equazioni di Lyapunov, Riccati e Sylvester. La risoluzione di equazioni matriciali e' fortemente collegata alla teoria dei matrix polynomials [GLR] e alle matrici di Toeplitz [BM4]. Alcuni dei piu' efficienti algoritmi introdotti di recente si basano sull'uso dell'algebra lineare numerica strutturata [M2].
 

--Polynomial computations:
Molti problemi relativi a polinomi, quali la fattorizzazione, il calcolo del MCD o del MCM, lo studio della stabilita', il conteggio degli zeri nel cerchio unitario, polinomi ortogonali ecc., sono riconducibili allo svolgimento di operazioni con matrici strutturate (matrici di Bezout, Sylvester, Toeplitz, Hankel) [BP], [BvB], [KvB]. La possibilita' di leggere in chiave polinomiale
operazioni su matrici con struttura e viceversa ha permesso di approfondire maggiormente l'analisi e la realizzazione di algoritmi di risoluzione efficienti [BGM1]. Processi asintotici di ortonormalizzazione, mediante il metodo di Gram-Schmidt, di una successione di funzioni multivariate ottenute per traslazione uniforme di una prefissata funzione, genera un profilo limite.
L'identificazione di tale profilo richiede la fattorizzazione spettrale di una matrice di Toeplitz multi-indice in spazi di Banach con peso [GMRS].
 

L'interesse per le matrici con struttura tipo Toeplitz, finite e infinite, scalari e a blocchi, mono e multi-indice, non e' solo motivato dalle applicazioni. Infatti la specificita' di tali matrici conferisce ad esse ricche proprieta' spettrali algebriche e analitiche che le rende particolarmente interessanti da un punto di vista teorico. Una vasta letteratura, con risultati e filoni di ricerca gia' ben consolidati negli anni, continua ad arricchirsi di risultati rilevanti sia per gli aspetti teorici che computazionali e fornisce una solida base di partenza per il progetto, ci riferiamo in particolare ai libri di Bultheel e Van Barel [BvB], Bini e Pan [BP], Boettcher e Silbermann [BS], Grenander e Szego [GS], Heinig e Rost [HR], Gohberg, Goldberg e Kaashoek [GGK], alle raccolte edite da Bini Tyrtyshnikov e Yalamov [BTY], Kailath e Sayed [KS], Olshevsky [O], ai lavori di rassegna di Chan e Ng [CN], Kravanja e Van Barel [KvB] e ai lavori li' citati.
E' utile ricordare i seguenti aspetti che sono diventati strumenti indispensabili per individuare ed analizzare algoritmi di risoluzione efficienti dei problemi con matrici strutturate di grande dimensione:
 

-- la teoria spettrale di Szego e le proprieta' spettrali asintotiche (vedi [BS] e la letteratura ivi citata);
-- le proprieta' dei complementi di Schur, la teoria degli operatori displacement, le formule di inversione, l'uso delle trasformate discrete e il loro legame con le algebre strutturate (vedi [HR], [BP], i lavori in [KS] e la bibliografia citata);
-- gli algoritmi di tipo "fast" e "superfast" [KS], [GKO], [BP];
-- gli algoritmi concretamente veloci basati su tecniche del gradiente coniugato [CN] e i metodi multigrid [FS], che hanno permesso di raggiungere una efficienza di risoluzione superiore a quella ottenuta con la piu' recente tecnologia dell'hardware;
-- la teoria del precondizionamento, legata all'uso del gradiente coniugato che si e' arricchita negli anni grazie ai contributi di molti gruppi di ricerca (vedi [CN], [CPS], [DB], [DBS], [KS], [TZ], [S1], [S2], [Str]);
-- il legame fra operazioni fra matrici strutturate e operazioni con polinomi e serie di potenze ([BvB], [KvB], [BP], [B], [BGM], [BGM1]) che permette di riformulare le operazioni tra matrici di Toeplitz in altre tra polinomi algebrici;
-- l'analisi delle proprieta' dei sistemi finiti di grandi dimensioni e infiniti, delle fattorizzazioni spettrali nelle algebre di Banach di matrici infinite strutturate, con le connesse problematiche di convergenza [GGK], [BS], settore di ricerca nel quale continuano a realizzarsi rilevanti avanzamenti
 

L'interesse crescente per la ricerca nel settore delle matrici con struttura e' anche evidenziato dai numerosi congressi dedicati a questa area di ricerca che si vanno organizzando da alcuni anni.
Diversi gruppi di ricerca nazionali e internazionali svolgono attivita' in qualche modo correlate allo studio delle matrici con struttura. Alcuni di questi gruppi conducono ricerca sia in collaborazione tra loro, sia in collaborazione con altri gruppi internazionali.
Esiste quindi una solida base di partenza nazionale e internazionale costituita da una ricca letteratura in cui molti membri del presente progetto hanno dato contributi sostanziali. In particolare si ritengono rilevanti i lavori [BZ], [Bo1], [Bo2], [BDF] sullo studio di algebre di matrici, assieme ai risultati sull'uso della "Toeplitz matrix technology" alla risoluzione di problemi di teoria delle code [BM2], [BM3], [BM4], [BMR], [M1], allo studio di algoritmi per sistemi di Toeplitz [BM1], [BTY], alla risoluzione di equazioni matriciali [BM4], [M2].
Un filone che ha prodotto numerosi risultati e' lo studio di relazioni fra matrix computations e polynomial computations [B], [BP],[G1], [G2], [G3], [BGM], [BGM1], in particolare i legami tra classi di matrici Toeplitz-like e la manipolazione numerica e/o simbolica di polinomi e serie formali di potenze.
Progressi significativi sono stati ottenuti, nella direzione dell'analisi delle proprieta' spettrali asintotiche in relazione allo studio del condizionamento e al disegno di precondizionatori [BS], [DB], [DB1], [DBS], [S1], [S2], [S3]. Una analisi sistematica di precondizionatori efficienti per gradiente coniugato e' stata condotta in numerosi lavori (vedi [DB]). Il metodo multigrid algebrico per
Toeplitz e' stato introdotto e sistematicamente analizzato in [FS] e recentemente riesaminato da R. Chan. Progressi significativi nel legame fra precondizionamento in algebre e approssimazione di funzioni sono ottenuti in [S1]. Analisi delle strutture ottenute da operatori differenziali ellittici e' condotta in [ST]. Lo studio di proprieta' spettrali di matrici di Hankel e' condotta in [Fa], [Fa1].
Un'applicazione importante delle metodologie relative alle strutture e' sviluppata in [BDB], [DB] e riguarda la risoluzione di problemi di restauro di immagini dove vengono in particolare analizzate e utilizzate le proprieta' di struttura dei modelli fisici specifici quali il modello di tomografia SPECT e il modello per le immagini all'infrarosso in relazione alla risoluzione di problemi inversi.
Lo studio di matrici infinite, fattorizzazioni spettrali e algebre di Banach ha avuto sviluppi algoritmici interessanti [GMRS], [GMRS1], [MRS], con applicazioni alla risoluzione di sistemi semi-infiniti con perturbazioni, al calcolo di fattorizzazioni spettrali ad equazioni integrali e a problemi di approssimazione di funzioni e a modelli di acustica. In particolare e' stata studiata la fattorizzazione spettrale di matrici di Toeplitz bi-infinite scalari e a blocchi dove sono state ottenute, in modo costruttivo, le condizioni necessarie e sufficienti di esistenza. Sono stati proposti metodi per il calcolo della fattorizzazione spettrale. E' stata dimostrata l'esistenza di un profilo limite nel processo di ortonormalizzazione di Gram-Schmidt applicato a successioni di funzioni ottenute per traslazione intera di una prefissata funzione.
Una certa rilevanza applicativa ha avuto recentemente l'uso delle matrici con struttura in problemi dell'ottimizzazione e delle reti neuronali [DFFZ] e i metodi per problemi di minimi quadrati totali con matrice strutturata [LMV].

[B]D.Bini, Using FFT-based techniques in polynomial and matrix computations: recent advances and applications. Numer.Funct.Anal.Optim. 21,2000
[BBDB]D.Bindi, P.Brianzi, F.Di Benedetto, A Fourier approach to the natural pixel discretization of brain single-photon emission computed tomography. Int. J. Imaging Syst. and Technol. 12,2002, 1-8
[BeBo]M.Bertero,P.Boccacci, Introduction to inverse problems in imaging, Institute of Physics Publishing, Bristol, 1998.
[BD]E.Bozzo,C.Di Fiore, On the use of certain matrix algebras associated with discrete trigonometric transforms in matrix displacement decomposition. SIAM J. Matrix Anal.Appl. 16,1995
[BDB]P.Brianzi,F.Di Benedetto, Exploiting matrix structures in SPECT models", Structured Matrices: Recent Developments In Theory And Computation, D.Bini, E.Tyrtyshnikov, P.Yalamov Eds., Nova Science Pub.Inc., New York,2001
[BF]D.Bini,P.Favati, On a matrix algebra related to the discrete Hartley transform. SIAM J. Matrix Anal.Appl. 14,1993
[BG1]D.Bini,L.Gemignani, Fast fraction-free triangularization of Bezoutians with applications to sub-resultant chain computation. Lin.Alg.Appl. 284(1998).
[BGM]D.Bini,L.Gemignani,B.Meini, Factorization of analytic functions by means of Koenig's theorem and Toeplitz, computations, Numer. Math. 89,2001.
[BGM1]D.Bini,L.Gemignani,B.Meini, Computations with infinite Toeplitz matrices and polynomials, Lin.Alg.Appl. 343,2002.
[BM1]D.Bini,B.Meini, Effective methods for solving banded Toeplitz systems. SIAM J. Matrix Anal. Appl. 20(1999).
[BM2]D.Bini,B.Meini, Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: application to queueing problems. Lin.Alg.Appl. 272(1998).
[BM3]D.Bini,B.Meini, Improved cyclic reduction for solving queueing problems. Numer.Algo. 15(1997).
[BM4]D.Bini,B.Meini, On the solution of a nonlinear matrix equation arising in queueing problems. SIAM J. Matrix Anal.Appl. 17(1996).
[BMR]D.Bini,B.Meini,V. Ramaswami, Analyzing M/G/1 paradigms through QBDs: the role of the block structure in computing the matrix G, in Adv. in Alg. Methods for Stoch. Models, Proc. G. Latouche and P. Taylor eds., Notable Publications, 2000.
[Bo1]E.Bozzo, Algebras in matrix spaces with displacement structure. Lin.Mult. Alg. 42(1997).
[Bo2]E.Bozzo, Algebras of higher dimension for displacement decompositions and computations with Toeplitz plus Hankel matrices. Lin.Alg.Appl.230(1995).
[BP]D.Bini,V.Pan. Polynomial and matrix computations. Vol. 1. Birkhäuser Boston, MA, 1994.
[BS]A.Boettcher,B.Silbermann, Introduction to Large Truncated Toeplitz Matrices, Universitext, 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.Van Barel, Linear algebra, rational approximation and orthogonal polynomials. North-Holland, Amsterdam, 1997.
[BZ]R.Bevilacqua,P.Zellini, Structure of algebras of commutative matrices. Lin.Alg.Appl. 233(1996).
[CN]R.Chan,M.Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev, 38 1996.
[CPS]R.Chan,D.Potts,G.Steidl, Preconditioners for nondefinite Hermitian Toeplitz systems. SIAM J. Matrix Anal. Appl. 22(2000), 647-665
[DB]F.DiBenedetto, Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices, SIAM Sci Comp, 16(1995).
[DB1]F.DiBenedetto, Preconditioning of block Toeplitz matrices by sine transform, SIAM SCiComp., 18, 1997.
[DBS]F.DiBenedetto,S.Serra, A unifying approach to abstract matrix algebra preconditioning, Numer. Math. 82(1999).
[DFFZ]C.DiFiore,S.Fanelli,P.Zellini, Matrix algebras in quasi-Newtonian algorithms for optimal learning in multi-layer perceptrons. Proc. ICONIP '99, Dunedin, New Zeeland, 1999.
[Fa]D.Fasino, Spectral properties of Hankel matrices and numerical solution of finite moment problems, J. Comp. App.Math. 65(1995).
[FT]D.Fasino, P. Tilli, Spectral clustering properties of block multilevel Hankel matrices. Lin.Alg.Appl. 306(2000).
[FS]G.Fiorentino,S.Serra, Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM Sci Comp, 17,1996.
[G1]L.Gemignani, A hybrid approach to the computation of the inertia of a parametric family of Bezoutians with application to some stability problems for bivariate polynomials. Lin.Alg.Appl. 283(1998).
[G2]L.Gemignani, Computing a factor of a polynomial by means of multishift LR algorithms. SIAM J. Matrix Anal.Appl.19(1998).
[G3]L.Gemignani, Schur complements of Bezoutians and the inversion of block Hankel and block Toeplitz matrices. Lin.Alg.Appl. 253(1997).
[G4]L.Gemignani, Computing a Hurwitz factorization of a polynomial. J. Comput. Appl.Math. 126(2000).
[GGK]I.Gohberg,S.Goldberg,M.Kaashoek. Classes of linear operators. Vol. I, 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).
[GLR]I.Gohberg,P.Lancaster,L.Rodman, Matrix polynomials. Academic Press, Inc. New York, 1982.
[GMRS]T.N.T.Goodman,C.A.Micchelli,G.Rodriguez,S.Seatzu. On the limiting profile arising from orthonormalizing shifts of exponentially decaying functions. IMA J. Num.Anal., 18, 1998.
[GMRS1]T.Goodman,C.Micchelli,G.Rodriguez,S.Seatzu. Spectral factorization of Laurent polynomials. Adv. in Comp.Math.,7,1997.
[GoS]I.Gohberg,A.Semencul, The inversion of finite Toeplitz matricesand their continual analogues. Mat.Issled 7,1972.
[GS]U.Grenander,G.Szego, Toeplitz Forms and their Applications. Univ. of California Press, Berkley 1958.
[H]T.Huckle, Iterative methods for ill-conditioned Toeplitz systems, Calcolo 33,1966
[HK]N.Higham, H-M.Kim, Numerical analysis of quadratic matrix equation, IMA J. Num.An. 20, 2000.
[HR]G.Heinig,K.Rost, Algebraic methods for Toeplitz-like matrices and operators. Birkhäuser, Basel, 1984.
[KS]T.Kailath,A.Sayed Eds., Fast Reliable Methods for Matrices with Structure, SIAM Philadelphia 1999.
[KvB]P.Kravanja,M.Van Barel, Computing the zeros of analytic functions. Lecture Notes in Math., 1727. Springer, Berlin, 2000.
[LMV]P.Lemmerling,N.Mastronardi,S.VanHuffel, Fast algorithm for solving the Hankel/Toeplitz structured total least squares problem, Numer.Algo. 23,2000.
[LR]G.Latouche,V.Ramaswami, Introduction to matrix analytic methods in stochastic modeling. SIAM, Philadelphia, 1999.
[MRS]C.vander Mee,G.Rodriguez,S.Seatzu. Spectral factorization of bi-infinite multi-index block Toeplitz matrices. Lin.Alg.App. 343/344, 2001.
[M1]B.Meini An improved FFT-based version of Ramaswami's formula. Comm. Statist. Stochastic Models, 13,1997.
[M2]B.Meini, Efficient computation of the extreme solutions of X+A^*X^{-1}A=Q and X-A^*X^{-1}A=Q. MathComp 2001.
[Ne]M.Neuts, Structured stochastic matrices of M/G/1 type and their applications. Marcel Dekker, Inc., New York, 1989.
[NPPT]J.Nagy,V.Pauca,R.Plemmons,T.Torgersen, Degradation reduction in optics imagery using Toeplitz structure. Calcolo 33,(1996), 269-288
[O]V.Olshevsky Ed., Structured Matrices in Mathematics, Computer Science and Engineering II, Contemp. Math. 281, 2001.
[S1]S.Serra, A Korovkin-type Theory for finite Toeplitz operators via matrix algebras, Num.Math., 82,(1999).
[S2]S.Serra, An ergodic theorem for classes of preconditioned matrices, Lin.Alg. Appl., 282(1998),161-183.
[S3]S.Serra, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Lin.Alg.Appl.,270 1998, 109-129.
[ST]S.Serra,C.Tablino Possio, Spectral and structural analysis of high precision Finite Difference matrices for Elliptic Operators, Linear Alg. Appl., 293(1999), pp. 85-131.
[Str]G.Strang, A proposal for Toeplitz matrix calculations. Stud. Appl. Math. 74(1986), 171-176
[Tr]W.Trench, An algorithm for the inversion of finite Toeplitz matrices, J. Soc.Ind.App.Math. 12,1964.
[TZ]E.Tyrtyshnikov,N.Zamarashkin, Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships, Lin.Alg.App., 270 1998, 15-27.

Fase 1

Durata:	24 mesi		Costo previsto:	185.600 Euro

Descrizione:

Diverse collaborazioni sono gia' in atto fra le diverse Unita', di seguito denotate con U1, U2, U3, come indicato al punto 2.1. 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.
 

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 veloci 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. L'accesso ai computers sara' svolto mediante accounting.
 

Per quanto riguarda i costi del progetto sono previste alcune spese specifiche per un totale di circa 46000 euro che sono: il costo di due assegni di ricerca per un totale di 33000 euro che rafforzeranno le unita' U1 e U2, il costo di una struttura hardware a disposizione di tutte le unita' per un costo di circa 15000 euro(U1) e il contributo per il costo dell'organizzazione di un congresso internazionale, l'IWOTA (International Workshop in Operator Theory and Applications), Giugno 2003 (U3) di circa 8000 euro.
 

Per quanto riguarda le attivita' di ricerca, verranno perseguiti gli obiettivi riportati nel punto 2.1, cui fa riferimento il programma che segue.
 

Per quanto riguarda il capitolo:
A- Aspetti teorici
L'Unita' U1 si occupera' dell'analisi di algebre di matrici di tipo Hartley e di generalizzazioni a classi piu' ampie (A1) con l'analisi delle associate formule di inversione (formule di dislocamento), al fine di preparare strumenti computazionali per il disegno di nuovi precondizionatori, in particolare specifici per problemi di ottimizzazione. L'Unita' U1 si occupera' inoltre dello studio delle proprieta' delle fattorizzazioni spettrali di matrici semi-infinite di Toeplitz mono e multi-livello con elementi scalari e a blocchi, al fine di preparare strumenti per il disegno di algoritmi numerici per il trattamento di matrici infinite di Toeplitz e di polinomi di Laurent (A5). Verranno studiate le proprieta' del rango approssimato di dislocamento. L'Unita' 1 si occupera' inoltre dello studio di fattorizzazioni QR di matrici di Cauchy con attenzione a problemi di ortogonalizzazione di funzioni razionali (A6).
L'Unita' U2 si occupera' dello studio di proprieta' astratte dei precondizionatori superottimali in algebre (A1), in particolare le proprieta' di monotonia dell'operatore superottimale, con l'intento di preparare strumenti teorici per il disegno di efficaci precondizionatori dotati anche di caratteristiche regolarizzanti. Svolgera' inoltre analisi di proprieta' spettrali di successioni di matrici di Toeplitz con l'intento di estendere formule distribuzionali al caso multilivello a blocchi, e di estendere il concetto di matrice localmente Toeplitz al caso multilivello (A2); verra' studiato il condizionamento asintotico di matrici con struttura di dislocamento in funzione dei parametri che le definicono (A3). Oltre agli aspetti analitici astratti questo tipo di ricerca ambisce alla messa a punto di nuove metodologie numeriche per il disegno di algoritmi efficienti per problemi con struttura e a favorire sinergie fra settori quali l'Operator Theory e l'algebra lineare asintotica. L'Unita' 2 si occupera' inoltre dello studio di fattorizzazioni QR di matrici di Cauchy con attenzione a problemi di ortogonalizzazione di funzioni razionali (A6).
L'unita' U3 si occupera' principalmente di proprieta' di matrici di Toeplitz infinite, in particolare del problema del calcolo di fattorizzazioni spettrali di matrici di Toeplitz in algebre di Banach con peso con l'intento di ottenere, per matrici multilivello e a blocchi, risultati analoghi validi nel caso scalare con studio asintotico dei coefficienti della fattorizzazione (A5). L'obiettivo e' anche quello di produrre nuovi strumenti per il disegno di algoritmi veloci per sistemi infiniti o di grandi dimensioni, incluso il precondizionamento e di produrre sinergie fra i settori dell'Operator Theory e dell'algebra lineare asintotica (A4) L'unità U3 si propone di sviluppare sia il background teorico necessario sia le tecniche di calcolo efficienti per la risoluzione numerica di equazioni integrali di tipo strutturate nel piano e nel semispazio e di loro perturbazioni. Lo sviluppo della teoria ha come obiettivo primario l'estensione alle equazioni integrali della metodologia sviluppata per i sistemi semi-infiniti.
 

Per gli aspetti teorici si prevedono collaborazioni strette fra le Unita' U1 e U3 (punto A5); U2 e U3 (punto A4); U1 e U2 (punto A6).
 

Per quanto riguarda il capitolo
B- Metodologie numeriche
L'Unita' di U1 si occupera' principalmente del disegno e analisi di metodi per la risoluzione di sistemi infiniti di Toeplitz multilivello e/o a blocchi, per il calcolo di fattorizzazioni spettrali (B3), e per la manipolazione di polinomi di Laurent a elementi scalari e a blocchi, mono e multivariati,in particolare gli algoritmi per fattorizzare polinomi e serie di potenze (B5), algoritmi basati su tecniche di evaluation/interpolation e sul metodo di Wilson. Un'altro punto riguarda la risoluzione di equazioni matriciali per le quali verranno studiati algoritmi basati sulle proprieta' dei polinomi di Laurent e delle matrici di Toeplitz (B4). Verranno inoltre studiati metodi per la fattorizzazione QR di matrici con struttura basati sulle polynomial computations (B6). Altri argomenti di ricerca riguardano l'uso del rango approssimato di dislocamento per l'inversione di matrici, lo studio di precondizionatori basati sulla fattorizzazione di matrici infinite (B1) e l'analisi di metodi multigrid (B2). L'Unita' U1 applichera' i risultati dell'analisi di algebre al disegno di nuovi precondizionatori per matrici di Toeplitz (B1). In particolare la tecnica di precondizionamento ottimale (T.Chan) verra' studiata da un punto di vista generale, in termini di sottoinsiemi di classi piu' ampie di matrici che includono algebre di matrici non diagonalizzabili. Verranno applicate le proprieta' di algebre di matrici alla implementazione di metodi di ottimizzazione non vincolata e al disegno di algoritmi per il total least squares problem.
L'Unita' U2 utilizzera' i risultati dell'analisi teorica svolta per il disegno e l'analisi di precondizionatori per matrici multilivello, per matrici localmente Toeplitz, per lo studio di precondizionatori regolarizzanti quali il precondizionatore superottimale (B1), con forti interessi applicativi ai problemi di restauro di immagini. Verranno analizzati gli aspetti algoritmici e numerici del metodo multigrid su algebre di matrici (B2), verranno studiati metodi numerici per il calcolo di fattorizzazioni QR di matrici strutturate (B6).
L'Unita' U3 Applichera' gli strumenti di cui al punto A5 allo studio di precondizionatori per sistemi finiti (B1) basati su fattorizzazioni spettrali; applichera' inoltre i risultati dello studio di proprieta' astratte di matrici infinite al disegno analisi e confronto di algoritmi per calcolare fattorizzazioni spettrali (B3). In particolare, saranno studiati i metodi, basati sulla teoria dei polinomi matriciali, e il band extension method.
 

Per le metodologie numeriche si prevedono collaborazioni strette fra le tre unita' sul punto B1, inoltre fra le unita' U1 e U3 sul punto B3, e fra U1 e U2 sul punto B6.

Per quanto riguarda il capitolo:
C- Applicazioni specifiche
L'Unita' U1 applichera' i risultati ottenuti alla risoluzione numerica di catene di Markov che nascono da problemi di teoria delle code. I modelli considerati verranno anche studiati al fine di mettere maggiormente in rilievo le proprieta' intrinseche di struttura (C4). La stessa unita' si occupera' di applicare i risultati ottenuti nella ricerca a problemi di ottimizzazione non vincolata e allo studio di reti neuronali e alla risoluzione di problemi totali di minimi quadrati(C6). Verranno studiate proprietà di convergenza "ad hoc" del processo di apprendimento su reti neuronali supervisionate (perceptroni multistrato e reti ricorrenti), assieme a nuovi algoritmi particolarmente efficienti per la minimizzazione della funzione di errore della rete. Verranno applicate le proprieta' di matrici di Cauchy alla risoluzione di problemi di interpolazione razionale (C5).
L'Unita' U2 verifichera' gli strumenti computazionali e i nuovi algoritmi su problemi derivanti dal trattamento numerico di equazioni differenziali alle derivate parziali con differenze finite, elementi finiti e collocazione (C3), su problemi di restauro di immagini (C1), in particolare verranno analizzati il modello LBT (Large Binocular Telescope), il modello SPECT (Single Photo Emission Computed Tomography) e i modelli all'infrarosso. Tali modelli verranno anche analizzati al fine di mettere maggiormente in rilievo le proprieta' intrineche di struttura. Applichera' inoltre i risultati teorici all'approssimazione positiva di funzioni continue e positive e alla quadratura numerica di funzioni multivariate e allinterpolazione razionale (C5).
L'Unita' U3 si interessera' ad applicazioni relative alla risoluzione numerica di equazioni integrali e differenziali alle derivate parziali (C2,C3), in particolare a problemi di acustica, scattering inverso, propagazione di onde in guide d'onda.
Per quanto riguarda le applicazioni, ci sono interazioni specifiche fra le unita' U1 e U2 al punto C5, ma possibili interazioni possono nascere fra l'unita' U2 e le altre Unita' nello studio di precondizionatori regolarizzanti e sui problemi di immagini.
 

Per quanto riguarda il capitolo
D- Software
Tutte le unita' sono coinvolte per quanto riguarda la costruzione di un insieme di problemi test per gli algoritmi analizzati nel progetto (D2) e per la creazione di software prototipale e validazione numerica degli algoritmi (D1). In particolare, l'Unita' U1 si prende carico della creazione di una pagina web con link al software e ai test effettuati e ai risultati raggiunti (D3) e della realizzazione di una implementazione software della fattorizzazione ricorsiva di polinomi (D4). L'Unita' U2 si interessera' alla creazione di software specifico per i metodi multigrid (D5).
 

Quadro riepilogativo delle Unita' coinvolte nei vari argomenti
A1: U1, U2, U3
A2: U2
A3: U2
A4: U2, U3
A5: U1, U3
A6: U1, U2
B1: U1, U2, U3
B2: U1, U2
B3: U1, U3
B4: U1
B5: U1
B6: U1, U2
C1: U2
C2: U3,
C3: U2, U3
C4: U1
C5: U1, U2
C6: U1
D1: U1, U2, U3
D2: U1, U2, U3
D3: U1
D4: U1
D5: U2
Quadro riepilogativo degli argomenti trattati dalle varie unita'
U1: A1,A2,A6,..........B1,B2,B3,B4,B5,B6,...C4,C5,C6,...D1,D2,D3,D4
U2: A1,A2,A3,A4,A6,....B1,B2,B6,...... ... .C1,C3,C5,...D1,D2,D5
U3: A4,A5,....... ......B1,B3................C2,C3,......D1,D2

Risultati parziali attesi:

Si ritiene che i risultati teorici che verranno ottenuti al punto A permetteranno di ottenere avanzamenti algoritmici concreti fra questi:

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 (C6).
 

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.

Unita' di ricerca impegnate:
 

Unità nº 1

Unità nº 2

Unità nº 3

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.