Ricerca Scientifica 2002

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

Obiettivo della Ricerca

Il progetto e' la continuazione del precedente progetto MIUR 2002-2003. Il suo scopo e' ampliare il range di strumenti strutturati e delle loro applicazioni espandendo e integrando i risultati ottenuti nel 2002-2003 (si veda http://bezout.dm.unipi.it), secondo le seguenti linee:

A- Analisi di proprieta' algebriche analitiche e computazionali di classi di matrici strutturate incontrate in problemi teorici e applicativi, incluse strutture lineari e non lineari. In particolare, strutture displacement, (Toeplitz, Hankel, Cauchy, Bezout, etc), semi-separabili, multi livello (multi indice), matrici con strutture locali, sistemi parametrici.

B- Disegno di algoritmi veloci e numericamente affidabili (stabili e robusti) per risolvere problemi computazionali che coinvolgono matrici strutturate, come minimi quadrati totali, sistemi lineari, autovalori e autovettori. Adattamento a specifiche strutture di tecniche note quali multigrid, PCG, GMRES, iterazioni QR. Uso di strumenti di algebra lineare strutturata per problemi localmente strutturati o senza struttura.

C- Applicazione dei risultati alla risoluzione di problemi computazionali di calcolo scientifico inclusi: trattamento di immagini, problemi inversi non lineari, modelli di code, equazioni matriciali, equazioni differenziali e integrali, scattering inverso, approssimazione di zeri di polinomi, problemi di Computer Aided Geometric Design, modelli del metabolismo umano, motori di ricerca sul web, reti neurali.

D- Implementazione degli algoritmi in versione prototipale, confronti numerici e validazioni.

Diversi gruppi internazionali di ricerca sono molto attivi nel campo. Il gruppo italiano lavora nell'area da molti anni. C'e' una solida base teorica e algoritmica fatta di potenti strumenti e tecniche efficaci sviluppati negli anni da molti ricercatori. Esistono diverse linee di ricerca dove gli interessi si stanno incanalando e sviluppando a livello internazionale. Alcune linee sono gemmate dal progetto MIUR 2002-2003.

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.

Unità di Ricerca

Unità di PISA

Responsabile DARIO ANDREA BINI

Compito

Buona parte di problemi in matematica pura e applicata coinvolge matrici strutturate. L'analisi di proprieta' teoriche e computazionali di queste strutture e' un passo fondamentale nel disegno di algoritmi efficienti, specificamente disegnati per questi problemi, specialmente nei casi molto frequenti in cui metodi di risoluzione generale non possono essere applicati per il loro enorme costo computazionale dovuto alle grandi dimensioni del problema.

Matrici con struttura sono mutuate dalle specifiche proprieta' del problema. Caratteristiche comuni condivise da problemi in aree diverse come la shift invariance, il supporto compatto, la separabilita' delle variabili, si trasformano in strutture che sono comuni a matrici incontrate in campi diversi quali la struttura Toeplitz, le strutture displacement (incluse le matrici di Hankel, Cauchy, Bezout, Frobenius, Pick, Vandermonde), le matrici a banda, le semi-separabili le matrici ad albero ecc. In fatti queste strutture si incontrano in molti problemi diversi in statistica, probabilita', teoria delle code (inclusi problemi di telecomunicazioni, internet, analisi e valutazione di prestazioni, processi stocastici), calcoli con polinomi, algebra computazionale, CAGD, risoluzione numerica di equazioni differenziali e integrali, elaborazione di segnali e immagini digitali, giusto per citarne alcuni.

Spesso, le proprieta' del problema originale si trasformano in strutture che non appaiono evidenti, ad esempio strutture non lineari come la struttura displacement o la struttura semiseparabile dove le matrici appaiono come fossero non strutturate.

L'analisi di strutture e il conseguente disegno di algoritmi specifici per risolvere problemi in algebra lineare numerica ha ricevuto grande attenzione ed ha prodotto importanti avanzamenti nel disegno ed analisi di algoritmi. Da una parte sono stati raggiunti avanzamenti nello studio di proprieta' teoriche di classi di matrici con struttura, dall'altra, il disegno di algoritmi specifici ha permesso la risoluzione efficiente di importanti problemi in diversi campi applicativi. Giusto per citare un esempio, recenti algoritmi per risolvere equazioni matriciali o problemi di teoria delle code modellati da catene di Markov, basati su proprieta' di matrici di Toeplitz e su fattorizzazioni di Wiener-Hopf, si sono rivelati estremamente efficienti e hanno permesso di ridurre il tempo di cpu di un grande fattore mantenendo ottimo comportamento numerico [ALM]. In altri casi gli strumenti delle matrici con struttura hanno permesso di risolvere problemi non strutturati di minimizzazione in modo molto efficiente [D], [DFLZ], [DLZ].

In sintesi, le ricerche di questa unita' sono dettate dalle seguenti linee guida:

1- Le matrici con struttura giocano un ruolo fondamentale in gran parte di modelli matematici e nelle applicazioni.
2- L'analisi di strutture, oltre al suo interesse teorico, e' un passo fondamentale per disegnare algoritmi specifici di risoluzione. I risultati ottenuti in questo modo costituiscono un bagaglio di strumenti utili in molti contesti e costituisce la "structured matrix technology".
3- La structured matrix technology puo' essere usata per risolvere problemi di larga scala, di grande importanza applicativa, che difficilmente potrebbero essere risolti altrimenti con algoritmi generali. Allo stesso tempo, anche per la risoluzione di problemi non strutturati la tecnologia delle matrici strutturate puo' offrire importanti miglioramenti.
4- Il disegno e l'analisi di algoritmi ritagliati su specifiche strutture del problema non e' sufficiente. Cio' deve essere integrato con una rigorosa analisi di robustezza e stabilita' numerica. In certe situazioni dove il mal condizionamento e' una caratteristica intrinseca del problema, l'uso di tecniche di multiprecisione o l'uso di approcci ibridi numerico-simbolici diventano un passo obbligato.

LINEE GENERALI DI RICERCA

L'attivita' di ricerca e' condotta secondo le seguenti linee

-A- Condurre l'analisi di proprieta' algebriche, strutturali, analitiche spettrali e computazionali di classi di matrici strutturate che intervengono in problemi di matematica teorica e applicata (incluse matrici di Toeplitz, Hankel, Bezout, Cauchy, Frobenius, displacement, a banda, semiseparabili, ad albero, matrici con elementi scalari e a blocchi, multilivello).
-B- Sfruttare le proprieta' ottenute da questa analisi per generare metodologie per il disegno e l'analisi di algoritmi efficaci di risoluzione.
-C- Applicare gli algoritmi di risoluzione a problemi provenienti da certe applicazioni e dal calcolo scientifico su grande scala.
-D- Implementare in termini di software prototipo gli algoritmi ottenuti in questa ricerca e svolgere confronti computazionali e validazione numerica.
-E- Condurre una analisi dell'errore e della robustezza, teorica o sperimentale, in modo da selezionare algoritmi affidabili. Per problemi dotati di mal condizionamento intrinseco, disegnare nuove tecniche ibride basate su metodi numerici e simbolici, su multiprecisione e adattivita'.

ARGOMENTI SPECIFICI

Argomenti specifici di questa unita' sono

1- Polynomial computations: Analisi di fattorizzazioni di Wiener-Hopf (deboli) dove entrambi i fattori possono avere zeri unitari. Disegno di polynomial rootfinders basati sulle iterazioni QR applicate a matrici companion generalizzate che mantengano la struttura semiseparabile o quasiseparabile. Disegno di polynomial rootfinders basati sulle iterazioni di Newton, Laguerre, Halley con i teoremi di inclusione tipo Gerschgorin, e il concetto di pseudozero. Usare le rappresentazioni di polinomi nella base di Bernstein assieme alle loro controparti matriciali strutturate in modo da disegnare algoritmi per l'intersezione di curve di Bezier e superfici. Uso di algoritmi ibridi e di strumenti di geometria proiettiva, computer algebra ed analisi numerica per problemi di CAGD. Calcolo di autovalori di matrici tridiagonali [BGT].
2- Equazioni matriciali: lo scopo e' il disegno di algoritmi per risolvere equazioni di matrici basati su fattorizzazioni di Wiener-Hopf e su proprieta' di strutture. Casi di interesse sono la risoluzione dell'equazione algebrica di Riccati e il calcolo di radici p-esime di matrici.
3- Proprieta' strutturali e computazionali di matrici semiseparabili e quasiseparabili, matrici di Toeplitz, algebre trigonometriche. Fra gli obiettivi il disegno di algoritmi per il calcolo di autovalori e calcolo di zeri di polinomi (vedi parte1).
4- Problemi di minimizzazione: disegno ed analisi di algoritmi quasi-Newton per problemi di minimizzazione dove l'Hessiano e' approssimato con matrici strutturate.
5- Applicazione della parte 1) alla risoluzione di problemi di CAGD come l'intersezione di curve e superfici assegnate parametricamente o implicitamente. Applicazione della parte 2) alla risoluzione di catene di Markov che si incontrano in modelli di code. Applicazione della parte 3) al disegno di algoritmi per il calcolo di zeri di polinomi. Applicazione della parte 4) alla risoluzione di problemi di reti neurali.

COMPITI PRINCIPALI
Per il punto 1) si desidera generalizzare ed estendere le tecniche di shift introdotte in [MR], [BM7] per accelerare la convergenza nella risoluzione di certe equazioni incontrate nelle catene di Markov, in modo da poter trattare casi piu' generali in cui i fattori di Wiener Hopf possono avere zeri di modulo 1.
-- Si desidera anche investigare piu' da vicino l'algoritmo di [BDG] dove l'iterazione QR applicata a matrici nxn di Frobenius e' eseguita con costo O(n) per passo. Qui i problemi piu' rilevanti sono la stabilita' numerica e la robustezza. Anche gli algoritmi di [BGP] per il calcolo degli autovalori di una sottoclasse di matrici quasiseparabili saranno studiati piu' attentamente. Qui lo scopo e' individuare risolutori polinomiali efficienti e studiare possibili generalizzazioni di classi di matrici chiuse sotto l'iterazione QR.
-- Polynomial rootfinders saranno analizzati anche in termini di iterazioni simultanee indipendenti secondo i risultati di [HSS] cercando di sostituire l'iterazione di Newton con iterazioni piu' veloci complementate con risultati di inclusione tipo Gerschgorin per le approssimazioni fornite dall'algoritmo.
-- Polinomi di Bernstein e curve di Bezier saranno pure studiate. Qui lo scopo consiste nell'eseguire operazioni algebriche su polinomi rappresentati nella base di Bernstein senza cambiare rappresentazione nella base delle potenze. Infatti tale trasformazione e' fortemente mal condizionata. Questo scopo richiede che le operazioni algebriche che sono solitamente svolte nella base delle potenze in termini di matrici strutturate (matrici di Bezout e Sylvester) siano svolte nella base di Bernstein. Matrici di Bernstein-Bezout devono essere introdotte e studiate. Occorre inoltre sviluppare algoritmi per le fattorizzazioni LU e QR di tali matrici in modo che o la loro implementazione sia numericamente stabile o che la loro implementazione simbolica non conduca a forte crescita degli interi generati nei passi intermedi. In questo contesto anche il calcolo degli zeri di polinomi rappresentati nella base di Bernstein ha un ruolo importante e sara' studiato. Un altro argomento correlato di interesse e' l'applicazione e l'integrazione di strumenti simbolici e numerici, di algebra computazionale e geometria proiettiva per risolvere problemi di CAGD [FGPT].

Per il punto 2) si continua lo studio avviato in [BM], [BGM1], [BGM2], [BG2] sulla risoluzione di equazioni matriciali. Importanti avanzamenti in questo campo sono stati raggiunti in [HMR],[BM7] nel contesto delle catene di Markov per mezzo della tecnica di shift. Si intende estendere questa tecnica a equazioni matriciali di tipo piu' generale.
-- Si intende applicare l'algoritmo della riduzione ciclica di G. Golub, adattato a catene di Markov da [BM3],[BM4] e analizzato in [BGM1],[BGM2] per risolvere equazioni algebriche di Riccati. Anche il calcolo della radice principale p-esima di una matrice sara' affrontato in termini di inversione di serie di Laurent, fattorizzazioni di Wiener-Hopf, e iterazioni di Newton, dove verranno utilizzati anche i metodi di [M4] e [Ia].
-- Altri tipi di equazioni provenienti da catene di Markov che modellano problemi di code saranno considerate.

Per il punto 3) poniamo l'attenzione sulle proprieta' delle matrici semiseparabili e quasiseparabili con l'intento di estendere gli algoritmi di [BDG], [BGP] per implementare l'iterazione QR a costo lineare a classi piu' generali di matrici. Per quanto riguarda matrici di Toeplitz e algebre trigonometriche l'interesse e' rivolto all'analisi del metodo multigrid algebrico.

Per la parte 4) si continua lo studio di [D], [DFLZ], [DLZ] con l'analisi di condizioni sufficienti che garantiscono la convergenza dei metodi di minimizzazione quasi-Newton dove la matrice Hessiana e' sostituita da matrici nell'algebra di Hartley [BF] o con altre matrici strutturate. Le condizioni riguarderanno la limitatezza di certi operatori che intervengono nel processo di minimizzazione eil condizionamento delle matrici strutturate. Verranno studiati anche metodi adattivi dove l'Hessiano e' aggiornato ad ogni passo. Un'altro problema trattato sara' il disegno di algoritmi veloci per i "total least squares" per matrici con struttura e applicazioni a problemi di blind image deblurring.

Per la parte 5) rivolgeremo gli algoritmi individuati alle applicazioni di principale interesse. In particolare i risultati di 1) sulle matrici di Bernstein-Bezout, sui polinomi di Bernstein e sugli algoritmi ibridi saranno applicati per risolvere problemi di CAGD. Si applicheranno i risultati di 2) per risolvere problemi di code dove la risoluzione di equazioni matriciali diventa il compito computazionalmente piu' pesante; considereremo modelli di code correlati all'equazione algebrica di Riccati. Per quanto riguarda le applicazioni alle catene di Markov e ai modelli di code, programmiamo di organizzare a Pisa nel Giugno 2005 la quinta edizione del congresso internazionale "Matrix Analytic Methods and Stochastic Models (MAM5)" che verra' finanziato dal presente progetto. Si intende inoltre completare la stesura del libro "Numerical Solution of Structured Markov Chains" per la Oxford University Press. Si applicano i risultati di 4) alla risoluzione di problemi di reti neurali che modellizzano problemi di apprendimento e a problemi di blind image deblurring.

Parte della ricerca ai punti 3) e 4) e' svolta in collaborazione con l'Unita' di Genova.

[BG2] D.Bini,L.Gemignani, Solving quadratic matrix equations and factoring polynomials: new fixed point iterations based on Schur complements of Toeplitz matrices. To appear in Numer. Lin. Alg. Appl. 2004.
[BGFM] D.Bini, G.Fiorentino,,L.Gemignani,B.Meini, Effective fast algorithms for polynomial spectral factorization , Numer. Algo., 2003.
[BGP] D.Bini,L.Gemignani,V.Pan $QR$-like algorithms for generalized semiseparable matrices T.R. 1470, Dept. of Math., University of Pisa, 2003.
[BGT] D.Bini L.Gemignani F.Tisseur. The Ehrlich-Aberth method for the nonsymmetric tridiagonal eigenvalue problem. TR 428, Univ. of Manchester, England 2003
[BM7] D.Bini,B.Meini, Non-Skip-Free M/G/1-type Markov chains and Laurent matrix power series, Proc. "Numerical Solution of Markov Chains", Urbana, September 2003.
[FGPT] E.Fortuna, P.Gianni, P.Parenti, C.Traverso, Algorithms to compute the topology of orientable real algebraic surfaces, J. Symb. Comp., 36,2003
[HMR] C.He, B.Meini, N.Rhee, A shifted cyclic reduction algorithm for QBDs, SIMAX,23 2001/02.
[HSS] J.Hubbard,D.Schleicher,S.Sutherland, How to find all roots of complex polynomials by Newton's method. Invent. Math. 146 (2001).
[ALM] G.Anastasi, L.Lenzini, B.Meini, Performance evaluation of a worst case model of the MetaRing MAC protocol with global fairness. Performance Evaluation, 29:127--151, 1997.

Unità di GENOVA

Responsabile FABIO DI BENEDETTO

Compito

Il programma si sviluppa su due direzioni che erano i temi principali del progetto 2002-2003:
A) Proprietà teoriche e computazionali di matrici strutturate;
B) Strutture matriciali in problemi applicativi.
I problemi aperti in algebra lineare strutturata considerati in A) sono naturale continuazione di ricerche condotte nel progetto precedente, con un'attenzione particolare rivolta a strutture meno studiate (matrici shiftate, semiseparabili, nuove algebre di seni, "ingrassamenti spettrali" di algebre di tipo circolante/trigonometrico): le prime tre sono state oggetto di studio nella letteratura più recente e nelle applicazioni, mentre l'ultima è una nuova proposta a metà strada fra il precondizionamento di tipo circolante e le inverse approssimate sparse.
Le principali applicazioni in B) risultano ancora l'approssimazione, i problemi inversi e le PDE. Oltre alla continuazione di ricerche precedenti, qui verranno anche studiati nuovi problemi e/o tecniche innovative, spesso basate su strumenti avanzati sviluppati di recente nell'ambito delle strutture.
Rispetto al progetto 2002-03, la differenza sta nel diverso peso dato ai temi A) e B): verranno privilegiate le applicazioni reali. Di seguito sono descritti in dettaglio i punti specifici del programma.

A1) Aspetti teorici
a) Algebra lineare asintotica
Applicazione dei risultati finora ottenuti alla convergenza dei metodi iterativi. In particolare, considerando un approccio statistico all'analisi dell'errore nel caso di matrici che mostrano una distribuzione asintotica degli autovalori, siamo interessati nello studiare il ruolo della funzione di distribuzione: siamo convinti che il suo andamento determina l'evolversi dell'errore come il raggio spettrale lo è (asintoticamente) nel caso deterministico.
Il quadro concernente proprietà spettrali asintotiche di matrici strutturate di tipo Toeplitz e Localmente Toeplitz (include discretizzazioni di PDE a coefficienti variabili e su domini irregolari) è abbastanza chiaro: rimane da indagare il comportamento estremale fine (condizionamento asintotico) nel caso multidimensionale seguendo l'approccio di Bottcher e Grudsky. In un ambito più generale (anche non strutturato) e per via del forte interesse nello studio della convergenza di metodi tipo Krylov, studieremo come dedurre il clustering degli autovalori (debole o forte) da un clustering dei valori singolari per il quali sono già a disposizione molti strumenti.
b) Relazioni tra strutture
La relazione esistente tra matrici diagonali+semiseparabili e matrici razionali di Krylov, scoperta in [28], è una controparte "razionale" della ben nota relazione tra matrici tridiagonali e matrici di Krylov classiche. Vogliamo proseguire lo studio di tale relazione, sia per analizzare le proprietà di convergenza delle note varianti razionali dell'iterazione di Krylov, sia per le possibili implicazioni allo studio teorico e computazionale di insiemi di funzioni razionali ortogonali.
A2) Metodologie numeriche
a) Matrici parametriche
Una successione di sistemi lineari è detta parametrica se può essere rappresentata come {Aj xj = bj} dove Aj=A+vj Ej e vj è un parametro scalare; questa descrizione estende il caso più comune di matrici shiftate. Si intende analizzare fattorizzazioni incomplete aggiornate per sistemi lineari parametrici con
i) A nonsimmetrica definita positiva e Ej=I (caso shiftato)
ii) A simmetrica (definita e indefinita) e Ej a banda,
casi che sono strategici nelle rispettive applicazioni. Ad esempio, tecniche del tipo shift-invert, potenze inverse e Jacobi-Davidson sono usate per il calcolo di alcuni (di solito pochi) autovalori e autovettori di problemi hermitiani di grandi dimensioni e sparsi. Si sottolinea che il nucleo di questi algoritmi richiede la soluzione efficiente di numerosi sistemi lineari di grandi dimensioni (e generalmente indefiniti) in forma shiftata. Si prevede di seguire due percorsi per la soluzione dei problemi di cui sopra:
(i) precondizionatori basati su fattorizzazioni aggiornate incomplete indefinite ad-hoc usate con un opportuno metodo di proiezione di Krylov;
(ii) soluzione dei sistemi shiftati mediante metodi di proiezione e precondizionatori multilivello con algoritmi di riordinamento per trasformare il problema di partenza in uno più diagonale dominante.
Un'altra applicazione riguarda la soluzione del problema ai minimi quadrati totali basato sul quoziente di Rayleigh. In questo approccio, la soluzione del problema si riduce alla soluzione di successioni di sistemi simmetrici shiftati e definiti positivi. In [14] Björck e altri hanno proposto di risolvere questi sistemi lineari mediante gradiente coniugato precondizionato con la fattorizzazione (completa) di Choleski della matrice delle equazioni normali. Ci si propone di sintetizzare e analizzare metodi iterativi che generino una successione di sistemi lineari meglio condizionati, usando tecniche basate sulle fattorizzazioni incomplete e inverse approssimate aggiornate.
b) Strutture semiseparabili
Matrici con struttura semiseparabile generalizzata hanno recentemente ottenuto molto interesse come strumenti computazionali per la risoluzione numerica di problemi agli autovalori. La ricerca in questo campo può aprire nuove prospettive per la sintesi di algoritmi efficienti per problemi agli autovalori per matrici speciali, quali matrici di tipo companion generalizzate o matrici di Hessenberg quasi-unitarie.
Inoltre, vogliamo analizzare la possibilità di specificare il termine diagonale nella riduzione di una matrice simmetrica in forma diagonale+semiseparabile, allo scopo di renderne più efficiente il calcolo degli autovalori.
c) Strutture multilivello
Siamo interessati all'analisi e sintesi di algoritmi veloci ad hoc per la risoluzione di sistemi lineari strutturati multilivello (analisi di precondizionatori per il gradiente coniugato, delle relative proprietà di clustering ed equivalenza spettrale, e studio di metodi multigrid con enfasi alla scelta della coppia proiettore/smoother). Più in dettaglio ci interesseremo ai seguenti temi:
- Precondizionamento di strutture multilivello Toeplitz cercando di generalizzare al caso in più variabili i risultati di ottimalità presenti in [40].
- Proposta di un "ingrassamento" di algebre considerando matrici della forma U T U* dove T è una matrice con un certo profilo di sparsità e per la quale la risoluzione di un sistema lineare associato abbia complessità limitata dal costo di moltiplicare U o U* per un vettore (tipicamente O(n log n) operazioni aritmetiche). Vogliamo indagare se questa nuova proposta, che arricchisce sensibilmente le algebre classiche in cui T è solo diagonale, sia sufficiente ad individuare precondizionatori ottimali nel caso multilivello e con malcondizionamento polinomiale (cosa impossibile per T diagonale).
- Estensione della dimostrazione di ottimalità del multigrid in [2] al caso multilivello ed applicazioni a problemi di ricostruzioni di immagini (si veda B2-a) ed alle PDE (con particolare attenzione ai sistemi strutturati e densi provenienti dai metodi Sinc-Galerkin applicati a PDE ellittiche).
B1) Prosecuzione di ricerche precedenti
a) Approssimazione razionale
Vogliamo proseguire alcune ricerche intraprese su problemi di interpolazione o approssimazione con funzioni razionali, con particolare riguardo all'analisi del condizionamento strutturato e al posizionamento ottimale dei poli.
b) Problemi inversi di imaging
Applicazione di algoritmi per la stima automatica del numero di iterazioni, che rappresenta un parametro di regolarizzazione nei metodi iterativi per problemi mal posti, ed è quindi un argomento cruciale nell'ambito della risoluzione di problemi inversi. Estensione dei precondizionatori regolarizzanti al caso della ricostruzione di immagini non negative e all'interno di problematiche legate al sistema di ottica adattiva di cui è fornito l'interferometro LBT.
Analisi e sintesi di nuovi algoritmi efficienti per sistemi lineari generati da algoritmi di regolarizzazione alla Tikhonov. Restringeremmo la nostra attenzione a termini regolarizzanti rappresentanti l'operatore identità o la derivata prima o seconda. Le relative equazioni normali sono in forma parametrica, e potrebbe essere necessario risolvere l'equazione sopra per numerosi valori del parametro di Tikhonov. Gli algoritmi proposti sono basati su nuovi metodi iterativi che usano fattorizzazioni incomplete aggiornate generalizzando i risultati in [3] (che si possono applicare direttamente se il termine di penalizzazione è la semplice norma della soluzione).
Infine, una vasta mole di calcolo è necessaria per ottimizzare noti algoritmi di ricostruzione (quale OS-EM per immagini multiple). Ad esempio, il problema LBT richiede di trattare immagini ad alto range dinamico (giovani stelle binarie, pianeti extrasolari). In tali casi si indagherà in due direzioni: la scelta di un funzionale adatto a catturare particolari caratteristiche e un sofisticato denoising a posteriori che preservi forti gradienti e strutture deboli.
c) PDE
Analisi delle caratteristiche di convergenza del GMRES precondizionato per la soluzione dei sistemi lineari che discretizzano l'equazione di convezione-diffusione con coefficiente di diffusione variabile. Il precondizionatore è basato sulla parte diffusiva dell'operatore corrispondente e si considererà principalmente una discretizzazione del tipo differenze finite in un dominio rettangolare d-dimensionale. Prevediamo di dimostrare l'esistenza di un cluster proprio di autovalori per la matrice precondizionata e quindi la convergenza superlineare delle iterazioni dell'algoritmo precondizionato. Una analisi preliminare ha dimostrato che la struttura del cluster non è influenzata dalla finezza della griglia ma il numero degli outlier nello spettro della matrice precondizionata cresce linearmente col parametro di viscosità. Le stesse tecniche saranno applicate a un modello del metabolismo umano basato su equazioni di convezione-diffusione-reazione dipendenti dal tempo, messe a punto al MIMS center di Cleveland.
B2) Tecniche innovative
a) Multigrid regolarizzante
Nel recuperare il "vero" oggetto da quello sfocato ed affetto da rumore si dovrà tener conto di tecniche regolarizzanti allo scopo di aggirare il problema della cattiva positura del problema. A tale scopo esistono diverse procedure di regolarizzazione quali Tikhonov, Riley, metodi iterativi come CG, CGNE, Landweber etc (si veda [25]). Si vuole indagare la possibilità di utilizzare una tecnica multigrid (basata sulla tecnica algebrica in [2,47]) che, per la sua naturale struttura a più livelli, dovrebbe ben adattarsi al problema in esame. I nostri obiettivi sono i seguenti:
- ottenere la stessa precisione nella ricostruzione dei migliori metodi regolarizzanti (come Landweber o CGNE) ma con un enorme risparmio computazionale;
- adattare la tecnica ad ogni tipo di condizioni al contorno (si veda il punto seguente) grazie alla estrema versatilità del metodo algebrico in [2] rispetto a varie strutture considerate.
b) Condizioni al contorno
Concentreremo i nostri sforzi sulle condizioni al contorno (CC) anti-riflettenti con due obiettivi:
- un'analisi accurata dell'algebra di matrici (non canonica, cioè costituita da elementi eterogenei) che origina dalle condizioni al contorno anti-riflettenti;
- lo studio del ruolo del rumore e, più precisamente, di come usare un metodo regolarizzante (la cui necessità nasce dalla presenza del rumore e dalla cattiva positura del problema) in connessione con le CC anti-riflettenti: ci piacerebbe suggerire modifiche delle classiche tecniche regolarizzanti (basate su equazioni normali o su metodi alla Tikhonov) in modo da sfruttare computazionalmente la struttura di algebra che emerge dalle CC considerate.
Resta comunque inteso l'obiettivo di avere una precisione maggiore rispetto a tecniche regolarizzanti applicate con le altre condizioni al contorno.
c) Denoising e determinazione di contorni tramite wavelet
Le immagini astronomiche sono particolarmente rumorose, richiedendo in molti casi tecniche di denoising. Ci si propone di studiare tre casi pratici: immagini "chopped e nodded" (nel vicino infrarosso), misurazioni di PSF usate in metodi classici di restauro, ricostruzioni sovra-iterate. Per tali indagini saranno usati metodi di riduzione basati su wavelet, in modo da ottimizzare il parametro di soglia per ogni problema.
È inoltre ben noto che l'approccio wavelet nella ricostruzione di immagini può risultare molto efficace in particolare nell'individuare i contorni di un'immagine. Vorremmo indagare nelle due seguenti direzioni:
- individuare relazioni tra i classici metodi wavelet per il deblurring di immagini (sfocate ed affette da rumore) e metodi multigrid (si veda B2-a) per il deblurring di immagini (sfocate ed affette da rumore);
- incorporare le più precise CC anti-riflettenti (si veda B2-b) nell'ambito wavelet allo scopo di migliorare la precisione complessiva dell'immagine ricostruita.
B3) Nuove applicazioni
a) Problemi inversi non lineari
L'approccio iterativo "Quasi-Newton" a due livelli precedentemente applicato ad un problema di Remote Sensing, come descritto nella Base di Partenza, ha rivelato la fattibilità dell'uso di matrici strutturate nel nuovo contesto applicativo dei problemi inversi non lineari. Sviluppi futuri prevedono l'applicazione della stessa tecnica ad un problema di determinazione di permittività dielettrica da Non-Linear Inverse Scattering.
b) Motori di ricerca web
In questa applicazione la struttura che definisce il problema è indicata dalle parole chiave "sparsità" e "struttura a blocchi": si aggiunge per ragioni modellistiche una matrice densa di rango 1 moltiplicata per 1-c, con 0<c<1 [36]. Se c è ben separato da 1, il calcolo del vettore positivo PageRank(c) (vettore stazionario sinistro) è effettuabile in modo sufficientemente veloce tramite il classico metodo delle potenze poiché il secondo autovalore ha modulo al più c.
Comunque, se c è vicino a 1, allora il calcolo diviene troppo lento anche per le enormi dimensioni della matrice di WEB. Il nostro obiettivo è di esprimere PageRank(c) come una espansione razionale di PageRank(1) in modo da applicare alla fine una tecnica di estrapolazione vettoriale.
c) Problemi di identificazione
Problemi inversi non standard agli autovalori per matrici tridiagonali, o con altre strutture ad essa correlate (tra le quali anche strutture di tipo diagonale+semiseparabile), sono stati recentemente individuati in alcuni problemi di identificazione di parametri provenienti dall'ingegneria civile.
In tali applicazioni tipicamente si cerca di identificare piccoli danni molto localizzati su travi, barre multistrato o altre strutture di tipo composito, o di ricostruirne proprietà costitutive, a partire da misure di risposta in frequenza o delle frequenze di risonanza.
Scopo della ricerca proposta è quello di fornire risultati teorici (criteri di identificabilità, analisi perturbative) e pratici (costruzione di algoritmi numerici) per l'identificazione di matrici con strutture assegnate a partire da misure di tipo spettrale.

Tutte le ricerche previste richiedono una validazione numerica e lo sviluppo di software prototipale specifico. L'unità necessita dunque di giovani ricercatori, ai quali sarà dedicata una cospicua parte del finanziamento: assegni, borse o contratti temporanei sono previsti durante il biennio del progetto.
L'unità comprende membri di sedi diverse, e una stretta collaborazione è necessaria anche con aiuti esterni: M.Benzi, Atlanta-USA (punto A2-a), D.Calvetti e G.Seidel, Ohio-USA (punto B1-c), G.Golub, Stanford-USA (punti A1-a, A2-a, B1-c), A.Morassi, Udine (punto B3-c), D.Noutsos e P.Vassalos, Ioannina-Grecia (punti A1-a, A2-c), M.Pastorino, DIBE Genova (punto B3-a), M.Tasche, Rostock-Germania (punto B2-c) e membri di altre unità del progetto (punto A2-b). Pertanto i fondi copriranno diverse spese di missione per meeting e conferenze.

Unità di CAGLIARI

Responsabile SEBASTIANO SEATZU

Compito

L'unità di Cagliari, conformemente con quanto concordato con le altre unità, svolgerà ricerche sulle seguenti tematiche:

1) sviluppo di metodi innovativi per la risoluzione di sistemi lineari con matrici malcondizionate e di sistemi lineari con matrici multiindice;
2) sviluppo di precondizionatori per la risoluzione di sistemi lineari con matrici multiindice;
3) generazione di famiglie di matrici test di tipo multiindice, con identificazione del profilo asintotico del numero di condizione;
4) risoluzione numerica di equazioni integrali con nuclei strutturati multivariati, con applicazioni in acustica e nel telerilevamento;
5) sviluppo di software prototipale specializzato per matrici strutturate.

1) Per quanto riguarda il primo tema di ricerca, l'unita' di Cagliari si propone di sviluppare metodologie di calcolo per sistemi lineari strutturati mal condizionati mediante l'applicazione di algoritmi veloci, basati sulla struttura di displacement, a metodi di regolarizzazione alla Tikhonov. Tali metodologie dovrebbero consentire, nei casi estremamente frequenti in cui la stessa matrice di regolarizzazione sia strutturata, di operare su sistemi lineari caratterizzati da diversi tipi di struttura di displacement, quali ad esempio quelle di Toeplitz, Hankel o di Cauchy, di particolare interesse nella risoluzione numerica di equazioni integrali con nucleo strutturato. Ci si propone altresì di studiare la risoluzione di sistemi malcondizionati mediante metodi iterativi precondizionati, operanti in spazi di Krylov, quali ad esempio il GMRES, il metodo del gradiente coniugato e il metodo di Lanczos. Più precisamente si pensa di utilizzare i metodi di precondizionamento, di cui al punto 2, come precondizionatori in vari metodi iterativi ed in particolare nel metodo GMRES.
Una seconda parte delle ricerche riguarderanno la estensione del metodo di proiezione, in algebre di Wiener con peso, alla risoluzione di sistemi lineari con matrici multi-indice strutturate. Tale metodo, ben noto per la risoluzione dei sistemi lineari di Toeplitz, nell'algebra di Wiener, è facilmente estendibile alle algebre di Wiener con peso, purchè si resti nell'ambito dei sistemi monoindice, oppure in quello delle matrici multi-indice definite positive ad elementi scalari [17,2]. Esso non è invece facilmente estendibile al caso multi-indice, per sistemi con matrice di Toeplitz non definita oppure a blocchi definita positiva. Tale estensione sarebbe molto utile in quanto consentirebbe di caratterizzare il comportamento asintotico dell'errore, in funzione del decadimento degli elementi della matrice, rispetto a quelli diagonali e del vettore dei termini noti.
L'Unità locale si propone altresì di studiare la risoluzione di sistemi lineari, le cui matrici presentano strutture non convenzionali, derivanti da problemi di tipo astronomico quali la propagazione della luce polarizzata in ambienti planetari, settore nel quale esistono significative competenze locali [25].

2) Come è ben noto [10,11,39], esistono vari metodi di tipo ottimale, dal punto di vista della complessità di calcolo, per la risoluzione di sistemi lineari di tipo mono-indice. Esistono invece soltanto risultati parziali per la generazione di precondizionatori, a bassa complessità di calcolo, nel caso di matrici multiindice [39]. Ricerche in atto nell'Unità di Cagliari, appaiono in grado di formulare, in modo uniforme, la generazione di precondizionatori per matrici mono e multi-indice. Le ricerche attualmente tendono alla ottimizzazione della complessità di calcolo, indipendentemente dal numero delle componenti degli indici. Ci si propone di sperimentarne l'efficacia del metodo nella risoluzione, di una vasta classe di sistemi lineari, mediante metodi iterativi precondizionati. Lo sviluppo di un'ampia classe di matrici test, previsto al punto 3), dovrebbe consentire di validare adeguatamente il metodo. Sono inoltre previste ricerche per la generazione ricorsiva di precondizionatori da applicare iterativamente, in particolare al metodo GMRES. Più esplicitamente l'idea base è la seguente: una volta costruito il precondizionatore per la matrice al passo k, il precondizionatore al passo successivo viene ottenuto dal precedente con la semplice valutazione di 2 elementi aggiuntivi.

3) In [28] è stato sviluppato un metodo generale e di semplice applicazione per la generazione di matrici test biinfinite e definite positive. In [35] tale metodo è stato ulteriormente migliorato e generalizzato al caso multi-indice, limitatamente alle matrici bi-infinite. Ci si propone ora di adattare il metodo alla generazione di matrici semi-infinite, con l'obiettivo di identificare l'andamento asintotico del numero di condizione di una vasta classe di matrici multi-indice rispetto al loro ordine. Tale risultato dovrebbe consentire di disporre di una classe di matrici sufficientemente ampia, per le quali sia noto l'andamento asintotico del numero di condizione. Questo allo scopo di poter confrontare l'efficacia dei nuovi metodi proposti, rispetto a quelli più utilizzati. L'unità di Cagliari, in particolare, è interessata alla valutazione dell'efficacia dei precondizionatori proposti, con riferimento ai metodi del gradiente coniugato e al metodo GMRES.

4) Poiché i sistemi lineari con matrici strutturate multiindice rappresentano l'analogo discreto delle equazioni integrali con nuclei strutturati in più variabili, esiste tra le due problematiche una naturale e profonda connessione potenzialmente molto proficua, ma attualmente non adeguatamente valorizzata. Fondamentalmente questo dipende dal fatto che la teoria degli operatori è stata finora sviluppata dagli analisti funzionali e la teoria delle matrici strutturate dagli analisti numerici. Poiché nell'Unità locale esistono ambedue i tipi di competenza, si ritiene di poter sviluppare metodologie innovative nella risoluzione numerica delle equazioni integrali multivariate con nuclei strutturati. Dal punto di vista teorico bisogna sviluppare discretizzazioni degli operatori integrali che conducano a matrici strutturate multiindice e studiare la convergenza della soluzione del sistema discretizzato alla soluzione dell'equazione integrale. Dal punto di vista numerico dovrebbe risultare molto utile il metodo di calcolo per sistemi infiniti di tipo multi-indice proposto in [34]. Un campo di applicazione importante, anche se relativo al caso monoindice, nel quale esistono significativi contributi dell'unità locale [1,29], è rappresentato dallo scattering inverso in acustica e in meccanica quantistica. L'unità locale, in collaborazione con studiosi dell'Università di Cagliari e Napoli, esperti nei settore del telerilevamento, si propone di applicare i risultati teorici e numerici sulle equazioni integrali e sui sistemi lineari multi-indice alla risoluzione di problemi tipici di tale settore.

5) A fronte di una grande interesse, in ambito scientifico come il quello applicativo, per gli argomenti correlati alle matrici strutturate ed al loro trattamento, non risulta esistere una libreria software specializzata che implementi i piu' recenti algoritmi specificamente sviluppati per tale classe di matrici. Poichè esistono sia vari algoritmi e programmi di interesse applicativo, sviluppati dall'Unità locale, sia una reale competenza nella scrittura e valutazione di software specialistico (*), ci si propone di sviluppare un toolbox specializzato per matrici strutturate per l'ambiente Matlab, uno dei piu' diffusi strumenti software per il calcolo e la visualizzazione scientifica. Le caratteristiche su cui si porra' particolare cura ed attenzione saranno: la facilita' d'uso, l'integrazione con l'ambiente Matlab e con le sue routine di calcolo intrinseche e l'ottimizzazione dei tempi di elaborazione e occupazione di memoria. Come primo obiettivo si intende focalizzare l'attenzione su alcune tipologie di matrici strutturate e sugli algoritmi di base per la risoluzione di sistemi lineari, sia con metodi iterativi precondizionati che con metodi diretti basati sulla displacement structure. L'obiettivo finale e' quello di costruire un software flessibile e facilmente estedibile, anche nel caso multiindice, ai nuovi algoritmi di calcolo.

(*) G. Rodriguez ha sviluppato i codici di calcolo proposti in [35-38]
e M. Redivo Zaglia è software editor della rivista Numerical Algorithms.