RICERCA ITALIANA     

Metodi numerici per l'algebra lineare strutturata e applicazioni

Università di Pisa

Abstract

MOTIVAZIONI
Ampia parte di problemi del mondo reale e del Calcolo Scientifico e' ricondotta a risolvere problemi di algebra lineare. Le grandi dimensioni e la complessita' dei modelli matematici si traduce in una grande massa di dati e nell'alta complessita' di risoluzione dei relativi problemi computazionali. Metodi generali di risoluzione non sono in pratica applicabili per il loro grande costo, ed e' quindi necessario ricorrere a metodi appositamente progettati sulle caratteristiche del problema.

Queste specificita', tradotte nel linguaggio dell'algebra lineare, sono descritte da struttura e sparsita' delle matrici coinvolte nel modello. Molte strutture sono evidenti e ricorrenti in diversi contesti e applicazioni (le matrici a banda esprimono la proprieta' di localita', le matrici di Toeplitz esprimono la proprieta' di invarianza per traslazione). Altre strutture sono piu' riposte e difficilmente individuabili come molte strutture non lineari.
L'analisi e l'uso delle proprieta' di struttura diventa un passo fondamentale per il disegno di algoritmi di risoluzione efficienti. Un esempio paradigmatico e' il problema del PageRank di Google.

L'analisi di matrici con struttura e il disegno di algoritmi specifici per problemi di algebra lineare numerica ha ricevuto grande attenzione negli anni e ha condotto a grandi avanzamenti. Da un lato sono stati raggiunti avanzamenti teorici nello studio di proprieta' astratte delle piu' frequenti strutture, dall'altro il disegno di algoritmi ad hoc ha permesso di risolvere problemi significativi in diversi campi applicativi.

IL PROGETTO
Il progetto e' la continuazione dei precedenti progetti COFIN 2002 e PRIN 2004 (http://bezout.dm.unipi.it), scopi del progetto sono

- Svolgere ricerca di base su classi di matrici con struttura per lo sviluppo di strumenti matematici atti alla progettazione e analisi di nuovi metodi di risoluzione efficienti per importanti problemi computazionali

- Sviluppare e analizzare nuovi algoritmi efficienti per importanti problemi computazionali, in particolare quelli di interesse applicativo

- Elaborare modelli provenienti dalle applicazioni per estrarre nuovi problemi e nuove classi di matrici che alimentino la ricerca di base.

- Implementare alcuni algoritmi piu' rilevanti.

I principali argomenti e problemi riguarderanno

A-Problemi computazionali: equazioni matriciali, catene di Markov strutturate, problemi di autovalori, sistemi di grandi dimensioni, problemi computazionali per polinomi, algebra lineare per equazioni differenziali strutturate e per equazioni integrali a nucleo strutturato, problemi di minimo non vincolato.

B- Strumenti teorici: Metodologie multigrid, di regolarizzazione, di precondizionamento e di estrapolazione; metodologie iterative, matrici a struttura di rango, matrici Toeplitz-like e Cauchy-like, proprieta' spettrali.

C- Applicazioni: modelli di code nell'ingegneria, problemi del Web (PageRank), problemi inversi (imaging, scattering, remote sensing), modelli di equazioni integrali (fibre ottiche, cristalli fotonici, telerilevamento); applicazioni modellate da PDE (modelli per il prezzo di opzioni, problemi di convezione-diffusione, e trasporto-diffusione-reazione, modelli di crescita tumorale); problemi modellati da autovalori.

D- Sviluppo di software: implementazione e validazione degli algoritmi, creazione di Toolbox Matlab e di un pacchetto software per la risoluzione di modelli di code.
<br />
STATO DELL'ARTE:
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 dai precedenti progetti COFIN 2002 e PRIN 2004. <<<

Coordinatore Scientifico del Programma di Ricerca

Dario Andrea Bini Università degli Studi di PISA

Obiettivo del Programma di Ricerca

Premessa sull'idea base.
La modellizzazione di problemi del mondo reale conduce a problemi matematici che generalmente comportano il trattamento di matrici di grosse dimensioni che sono dotate di alta specificita' intesa in termini di struttura o di sparsita'. La specificita' di tali matrici e' la traduzione in termini algebrici delle caratteristiche peculiari del problema modellizzato. Un esempio significativo a riguardo e' la classe delle matrici di Toeplitz, con le sue generalizzazioni, che si incontra ogniqualvolta intervengono proprieta' di invarianza sotto traslazione (si vedano i modelli di code nell'ingegneria delle telecomunicazioni, la discretizzazione di operatori differenziali, i problemi di image deblurring con PSF spazialmente invarianti, i problemi di correlazione statistica, i problemi di polynomial computations e di computer algebra, ecc.). Un altro importante esempio e' costituito dai problemi del Web, come ad esempio la matrice di Google il cui autovettore dominante determina l'importanza delle pagine Web (PageRank), che e' costituita da una matrice fortemente sparsa piu' una correzione parametrica di rango 1 ed ha dimensione di quasi 9 miliardi.

L'individuazione l'analisi e l'uso delle strutture e' un passo fondamentale per disegnare algoritmi ad hoc altamente efficienti specialmente nei casi in cui per le alte dimensioni del problema gli algoritmi generali impiegerebbero tempi biblici per la risoluzione.
Come esempio paradigmatico e' utile osservare che il problema del PageRank di Google richiederebbe milioni di anni di tempo di CPU se fosse affrontato con metodi generali, mentre puo' essere risolto in poche ore con metodi basati sulle specificita' della matrice.

La ricerca internazionale, attiva da anni in questo settore, ha sviluppato una ricca e articolata base di strumenti per la costruzione di metodi di risoluzione efficienti per problemi di natura anche molto diversa. Oltre a costituire una struttura unificante per le ricerche nell'algebra lineare numerica strutturata, questo insieme di strumenti e' un importante bagaglio culturale che ha permesso di risolvere in modo molto efficiente importanti problemi computazionali.

Obiettivi.
Il programma di ricerca riguarda lo sviluppo e lo studio di strumenti di algebra lineare numerica per classi di matrici con struttura al fine dell'analisi e sintesi di algoritmi specifici dotati di alta efficienza per la risoluzione di problemi computazionali anche di particolare interesse applicativo. Sono rilevanti le seguenti linee principali:
-L1- utilizzare i numerosi strumenti per problemi di algebra lineare numerica strutturata disponibili in letteratura per poter affrontare in termini computazionali problemi di grande interesse provenienti dalle applicazioni;
-L2- proseguire la ricerca di base su classi di matrici con struttura note in letteratura per sviluppare strumenti matematici atti alla progettazione ed analisi di nuovi metodi di risoluzione efficienti;
-L3- sviluppare nuovi algoritmi di risoluzione e condurre una loro analisi, implementazione e validazione numerica;
-L4- elaborare alcuni dei modelli provenienti dalle applicazioni, che appaiono piu' interessanti, per estrarre nuovi problemi e nuove classi di matrici con struttura che alimentino la ricerca di base.

Temi specifici di ricerca
I temi specifici di ricerca trattati includono:

A-Problemi computazionali:
-1- Risoluzione di equazioni matriciali (Riccati, unilaterali, polinomiali, power series,ecc.)
-2- Risoluzione di catene di Markov strutturate
-3- Problemi di autovalori per matrici a struttura di rango (semiseparabili, quasi separabili ecc.)
-4- Risoluzione di equazioni integrali a nucleo strutturato (convolutivo, anticonvolutivo, misto.
-5- Risoluzione di equazioni differenziali caratterizzate da strutture.
-6- Problemi di autovalori e sistemi strutturati di grandi dimensioni.
-7- Problemi di minimo non vincolato.
-8- Problemi computazionali per polinomi

B-Strumenti teorici e ricerca di base:
-1- Metodologie multigrid;
-2- metodologie di regolarizzazione;
-3- metodologie di precondizionamento;
-4- metodologie di estrapolazione;
-5- metodologie iterative;
-6- matrici a struttura di rango;
-7- matrici Toeplitz-like e Cauchy-like
-8- proprieta' spettrali di successioni di matrici

C-Applicazioni:
Le applicazioni che motiveranno la ricerca o che saranno oggetto di applicazione degli strumenti sviluppati includono:
-1- modelli di code nell'ingegneria delle telecomunicazioni;
-2- probelmi del Web (Page ranking, information retrieval);
-3- problemi inversi: problemi lineari di imaging e regolarizzazione, problemi non lineari, scattering inverso in diagnostica medica, tomografia ad impedenza elettrica, problemi di folding inverso per l'analisi di proteine, remote sensing atmosferico, analisi non-distruttiva di materiali;
-4- applicazioni modellate da equazioni integrali: trasmissione dei segnali tramite fibre ottiche, design ottimale dei cristalli fotonici, la propagazione del moto ondoso nelle superfici di liquidi di grandi dimensioni, telerilevamento e problemi di scattering inverso in acustica, equazioni di Marchenko, equazione di Schroedinger, equazione di Korteweg-De Vries;
-5- applicazioni modellate da equazioni differenziali: modelli multidimensionali per il prezzo di opzioni con salti, problemi di convezione-diffusione, problemi di tipo trasporto-diffusione-reazione, modelli chemotattici di crescita tumorale;
-6- Applicazioni modellate da problemi di autovalori: oltre ai problemi del Web, si considerano wireless communications, identificazione di parametri in meccanica strutturale.

D-Sviluppo di software:
Obiettivo del programma di ricerca e' anche l'implementazione di software. In particolare:
-1- creazione di un pacchetto software per la risoluzione di modelli di code del tipo M/G/1, G/M/1, Non-Skip-Free, Quasi-Birth-Death, sia in versione Toolbox di Matlab che in versione Fortran 95 con interfaccia grafico in C.
-2- completamento di un toolbox Matlab "object oriented" per il calcolo con matrici strutturate, recentemente sviluppato da Rodriguez e Redivo Zaglia. Il toolbox, denominato SMT e attualmente in fase di rilascio, consente di utilizzare matrici circolanti e di Toeplitz in modo trasparente per l'utente con l'implementazione degli algoritmi veloci piu' avanzati disponibili al momento.
-3- implementazione, in termini prototipali in linguaggi di programmazione avanzati o in ambiente Matlab o Mathematica, dei metodi sviluppati e analizzati nel progetto. <<<

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

Molti problemi in matematica pura e applicata coinvolgono classi di matrici con struttura frequentemente incontrate in contesti diversi. Le strutture di matrici sono la traduzione algebrica delle proprieta' specifiche dei problemi che modellano. Proprieta' generali quali l'invarianza per shift, il supporto compatto, la separabilita' di variabili, condivise da numerosi problemi in aree diverse, si traducono in strutture di matrici che sono pervasive come le matrici di Toeplitz, matrici a banda, e semi separabili.

L'analisi delle proprieta' di struttura di classi di matrici e' un passo fondamentale per il progetto e l'analisi di algoritmi di alta efficienza per la risoluzione di problemi specifici di particolare interesse computazionale e applicativo. Questa linea di pensiero, comune ai ricercatori di questo progetto, e' ampiamente condivisa da numerosi gruppi internazionali e ha generato negli ultimi vent'anni un solido ed ampio bagaglio di risultati e di strumenti teorici e computazionali di sicuro riferimento.

Larga parte dei ricercatori afferenti a questo progetto hanno contribuito con le loro ricerche, svolte anche nei precedenti progetti di ricerca MIUR 2002 e PRIN 2004, a formare ed ampliare questo bagaglio culturale. Essi vantano una prolungata esperienza di ricerca nei campi dell'analisi spettrale e computazionale di ampie classi di matrici strutturate, della regolarizzazione di problemi inversi che intervengono in molteplici applicazioni, nello studio teorico e computazionale di ampie classi di matrici con struttura fra cui le Toeplitz, le matrici a struttura di rango (semiseparabili), le matrici companion-like (di Bezout e Sylvester); hanno dato ampi contributi metodologici con le tecniche di precondizionamento e di multigrid; hanno dato contributi algoritmici e applicativi in problemi di image processing, di modelli di code in ingegneria, in computer algebra e nella risoluzione di equazioni matriciali.

L'interesse per matrici con struttura, gia' vivo negli anni '30 con i lavori di Gantmacher e Krein sulle proprieta' delle matrici a banda e delle loro inverse [VvBGM] e negli anni '60 [GS] e '70 [Tr], [GoS] con i metodi diretti per sistemi di Toeplitz e implicitamente con i risolutori veloci di Poisson [BGN], e' cresciuto di importanza negli anni per il lavoro di diversi gruppi internazionali di ricerca. Si e' consolidata un'ampia letteratura su diversi problemi matematici correlati e sono state organizzati numerosi congressi internazionali dedicati a matrici con struttura, algoritmi e applicazioni, con la pubblicazione di proceedings e di nuovi libri di ricerca.

La base teorica ed algoritmica su cui s'innesta il progetto e' molto ampia e ricca di strumenti e risultati.
Ricordiamo a grandi linee i principali riferimenti bibliografici generali, alcuni di essi sono pietre miliari del settore. I libri di Iohvidov [I] e di Heinigh e Rost [HR] su strutture Toeplitz e Hankel, il libro di Bultheel e Van Barel [BvB] sulle relazioni fra strutture e polinomi ortogonali, il libro di Bini e Pan [BP] sulle relazioni fra operazioni con matrici strutturate polinomi, i libri di Grenander e Szego [GS], Boettcher e Silbermann [BS] sulle proprieta' spettrali di matrici di Toeplitz, i libri di Gohberg, Goldberg e Kaashoek [GGK] e di Gohberg, Lancaster e Rodman [GLR] e la serie "Operator Theory and Applications:" della Birkhauser, su questioni piu' astratte. Il libro [DvdV] di Dewilde e van der Veen collegato a matrici semiseparabili, i libri editi da Kailath e Sayed [KS1], da Bini, Tyrtyshnikov e Yalamov [BTY], e da Olshevsky [O1,O2] che contengono avanzamenti recenti nel settore e il lavoro di rassegna di Chan e Ng [CN] sul precondizionamento di Toeplitz. Fra i libri piu' recenti si ricordano quello di Bini Latouche e Meini [BLM] che raccoglie i risultati piu' avanzati sulla risoluzione di catene di Markov con struttura, il libro di M.Ng [N] su metodi iterativi per sistemi di Toeplitz, il libro di Boettcher e Grudsky [BG] su proprieta' di matrici a banda di Toeplitz. Si ricordano inoltre i recenti numeri speciali di riviste dedicati a matrici con struttura, in particolare [B1] su matrici a struttura di rango, [B2] e [BHT] su strutture in generale, [O3] su matrici infinite, e [KvdMS] con i proceedings IWOTA 2003.

Diamo una descrizione della base di partenza piu' indirizzata ai temi specifici di ricerca del progetto. Per maggior dettagli si rimanda ai modelli B delle singole unita' di ricerca.

Displacement operators e spettro asintotico
La teoria dei displacement operators di Kailath et al [KS2] e l'ampia letteratura originatasi attorno costituisce una base solida e importante. Richiamiamo i risultati di distribuzione spettrale asintotica iniziati nel lavoro pioneristico di Szego [GS,BS] e culminati nel lavoro di Tyrtyshnikov [TZ] sul comportamento globale dello spettro di successioni di Toeplitz. In letteratura si trovano estensioni a funzioni generatrici a valori matriciali e a sequenze che nascono nella teoria del precondizionamento[S1] come pure alcune applicazioni alla approssimazione e alla quadratura[S2]. Un'altra importante estensione riguarda le matrici localmente Toeplitz cioe' strutture che sono di Toeplitz solo "localmente" [Ti] e includono in particolare le matrici che discretizzano operatori differenziali con condizioni al bordo[ST1,ST2].

Precondizionamento
Proprieta' spettrali asintotiche giocano un ruolo importante nel disegno di precondizionatori per gradiente coniugato. Le matrici circolanti associate alla trasformata discreta di Fourier che Strang [St] propose nel 1986, sono state affiancate da piu' generali algebre trigonometriche. Un trattamento sistematico del precondizionamento e' stato fatto da molti ricercatori fra cui T.Chan, R.Chan, S.Serra, F. DiBenedetto, G.Fiorentino, E.Tyrtyshnikov, T. Huckle, Potts, Steidl, Nagy, Plemmons nel caso mono e multi livello. Altre algebre trigonometriche sono state studiate da Kailath, Olshevsky, Bini, Favati, Zellini.
Contributi sulle matrici multi-livello di Toeplitz sono dati dal gruppo di van der Mee, Rodriguez, Seatzu. Proprieta' del precondizionamento nel caso multi-livello e del clustering degli autovalori sono nei lavori [SCT,NSV,S3]. Precondizionatori con matrici di Toeplitz a banda, dati da R.Chan, Di Benedetto, Fiorentino e Serra Capizzano [CN], conducono a metodi ottimali e superlineari [S4] per sistemi definiti positivi con condizionamento polinomiale, o solo ottimali per il caso non definito [HST,S5].
Le stesse idee sono state sfruttate in seguito nelle algebre matriciali da vari autori [CPS,DB]. Il problema è così ricondotto al caso a banda, per il quale esistono risolutori ottimali iterativi (il multigrid [FS] studiato in seguito dai gruppi di ricerca guidati da R.Chan e Huckle) e diretti [BM1] di costo lineare.

[FS] G.Fiorentino, S.Serra C., Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions. SIAM J. Sci. Comp. 17(1996)
[NSV] D.Noutsos, S.Serra C., P.Vassalos, Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate. Theoret.Comp.Sci. 315(2004)
[S4] S.Serra C., Optimal, quasi-optimal and superlinear preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems. Math.Comp. 66(1997)
[S5] S.Serra C., Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions. SIAM J.Matr.Anal.Appl. 17(1996)
[ST2] S.Serra C., C.Tablino P., Superlinear preconditioners for Finite Differences linear systems. SIAM J.Matr.Anal.Appl. 25(2003)

Polynomial computations
Matrici strutturate hanno un ruolo importante in problemi computazionali con polinomi, in particolare le matrici di Cauchy, Companion, Vandermonde, localmente Toeplitz e semiseparabili. Citiamo il libro [BP] e l'ampia letteratura, che include le fattorizzazioni di Wiener-Hopf, con i contributi di Bini, Boettcher, Gemignani, Goodman, Meini, C.Micchelli, G.Rodriguez, Seatzu, Spitkovsky, Winkler, [BG,BGW,BB,BMS,GMRS]

[BG] D.Bini, L.Gemignani, Bernstein-Bezoutian matrices. Theoret. Comput.Sci. 315 (2004)

Matrici semiseparabili
Esistono gruppi molto attivi in quest'area. Ricordiamo oltre al libro [DvdV] e i lavori classici di Gohberg, Kailath, Koltracht, Olshevsky, e gli sviluppi piu' recenti di Chandrasekaran, Dewilde, Eidelman, Fasino, Gemignani, Gohberg, Gu, Mastronardi, Pan, Van Barel, Vandebril, Tyrtyshnikov [CDGPSVW,CG,EG1,EG2,EGO,GKK,BDG,BGP,DvB,G1,G2,T] e le applicazioni mostrate in [BGT,BDG,BGP]. Risultati di recente pubblicazione ne hanno evidenziato legami inattesi con iterazioni razionali di tipo Krylov, funzioni razionali ortogonali, e pencils di matrici tridiagonali [F,vBFGM].

[BDG] D. Bini, F. Daddi, L. Gemignani, On the shifted QR iteration applied to companion matrices. ETNA 18(2004)
[BGP] D.Bini, L.Gemignani, V.Pan, Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations. Numer.Math., 100(2005)
[DvB] S.Delvaux, M.Van Barel, Structures preserved by the QR-algorithm. J. Comput.Appl.Math. 187 (2006)
[EG1] Y. Eidelman and I. Gohberg, Inversion formulas and linear complexity algorithm for diagonal plus semiseparable matrices, Comput.Math.App., 33 (1997)
[EG2] Y.Eidelman, I.Gohberg, On generators of quasiseparable finite block matrices. Calcolo 42 (2005)
[G2] L.Gemignani, Quasiseparable structures of companion pencils under the QZ-algorithm. Calcolo 42 (2005)


Equazioni matriciali
Metodi per la risoluzione di importanti classi di equazioni matriciali si trovano nel libro [Ne] e per i risultati piu' recenti, basati su proprieta' di classi di matrici strutturate, nei libri [BLM,LR] e in [BMS,BGM,HMR,Guo1,HK,BM,Me]. In particolare si ricordano i metodi di riduzione ciclica [BM2] e le strategie di shift [HMR]. Recenti risultati sulle equazioni di Riccati si trovano in [BMR] e [BILM], [Guo2]

[BILM] D.Bini, B.Iannazzo, G.Latouche, B.Meini, On the solution of algebraic Riccati equations arising in fluid queues. Lin.Alg.App. 413 (2006)
[BM2] D. Bini, B.Meini, On the solution of a nonlinear matrix equation arising in queueing problems. SIAM J. Matrix Anal.App. 17 (1996)
[Guo2] C.-H.Guo, Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for M-matrices. SIAM J. Matrix Anal.App. 23 (2001)
[Me] B.Meini, Efficient computation of the extreme solutions of $X+Asp *Xsp {-1}A=Q$ and $X-Asp *Xsp {-1}A=Q$. Math.Comp. 71(2002)
[BMR] P.Bubak, C.van der Mee, A.Ran, Approximation of Solutions of Riccati Equations, SIAM J. on Control and Optim. 44(2005).


Equazioni integrali
I risultati della teoria degli operatori lineari, di maggiore interesse per il progetto, si trovano nella collana Operator Theory Advances and Applications ed in particolare in [BS,BS1,GGK,KMS].

Risultati classici di specifico interesse sulle equazioni integrali sono contenuti in [PS]. Quelli più utili, dovuti a G. Mastroianni e collaboratori sono [JM,FLM,LM,MM1,MM2,MRT].

[BS1] A. Boettcher and B. Silbermann. Analysis of Toeplitz operators. Springer, New York, 1990.
[PS] S.Proessdorf, B.Silbermann. Numerical analysis for integral and related operator equations. Vol. 52 of O.T., Birkhauser, 1991.
[FLM] C.Frammartino, C.Laurita, G.Mastroianni, On the numerical solution of Fredholm integral equations on unbounded intervals. J. Comput.Appl.Math. 158 (2003)
[LM] C.Laurita, G.Mastroianni, Condition numbers in numerical methods for Fredholm integral equations of second kind. J. Int.Eq.Appl., 14 (2002)
[MM1] G.Mastroianni, G.Monegato, Numerical resolution of Mellin-type equations via Wiener-Hopf equation. vol 136 of O.T. Birkauser 2002.
[MM2] G.Mastroianni, G.Monegato, Truncated quadrature rules over (0,infty) and Nyström type methods. SIAM J. Num.Anal. 41(2003)
[MRT] G.Mastroianni, M.Russo, W.Themistoclakis, The boundedness of a Cauchy integral operator in weighted Besov type spaces with uniform norms. Int.Eq.Oper.Theory, 42(2002)

Equazioni differenziali
La struttura di Toeplitz a banda è l'ingrediente principale per una tecnica di precondizionamento superlineare [ST1,ST2,ST3] per discretizzazioni a Differenze Finite, Elementi Finiti o Collocazione di equazioni differenziali ellittiche al contorno con coefficienti non costanti.
La discretizzazione alle differenze finite di problemi di evoluzione con formule multistep lineari ai valori al bordo determina matrici non simmetriche di grandi dimensioni con struttura a blocchi. Vari precondizionatori sono introdotti in [Be,BN,BGST,SBG].

In [EBMPR] è trattata un'equazione integro-differenziale non lineare che proviene da un problema di scattering inverso, mediante tecniche di algebra lineare numerica strutturata.

[ST2] S.Serra C., C.Tablino P., Finite Element matrix-sequences: the case of rectangular domains. Numer. Alg. 28(2001), 309-327
[ST3] S.Serra C., C.Tablino P., Superlinear preconditioners for Finite Differences linear systems. SIAM J. Matr. Anal. Appl. 25(2003), 152-164
[Be] D.Bertaccini, A circulant preconditioner for the systems of LMF-based ODE codes. SIAM J. Sci. Comp. 22(2000), 767-786
[BN] D.Bertaccini, M.Ng, Band-Toeplitz Preconditioned GMRES Iterations for time-dependent PDEs. BIT 43(2003), 901-914
[EBMPR] C.Estatico, G.Bozza, A.Massa, M.Pastorino, A.Randazzo, A two steps inexact-Newton method for electromagnetic imaging of dielectric structures from real data. Inverse Problems 21(2005), 81-94.

Regolarizzazione
Il precondizionamento in algebre matriciali è stato applicato con successo alla ricostruzione di immagini mediante una famiglia parametrica di precondizionatori specifici, regolarizzanti [E].
Le ricostruzioni ottenute con un metodo di base possono poi essere migliorate grazie a due strumenti avanzati: le condizioni al contorno classiche [BeBo], antiriflettenti [S3] e le wavelet [CCSS].

[E] C.Estatico, A class of filtering superoptimal preconditioners for highly ill conditioned linear systems. BIT 42(2002), 753-778
[CCSS] R.Chan, et Al., Wavelet deblurring algorithms for spatially varying blur from high-resolution image reconstruction. Lin.Alg.Appl. 366(2003)

Catene di Markov
Metodi numerici per catene di Markov e' un settore in cui la tecnologia delle matrici strutturate ha prodotto grandi avanzamenti. Si fa riferimento ai libri [Ne], [LR] per la descrizione dei problemi e dei modelli, e per i piu' recenti avanzamenti, al libro [BLM] ai proceedings [BLM1] al lavoro [BMS].
<br />
Problemi del Web
Recentemente sono state proposte diverse tecniche numeriche per accelerare il calcolo del Page Rank fatta generalmente utilizzando il metodo delle potenze [LM]. Varie tecniche sono proposte in [KHG03], [KHMG03a], [KHMG03b]. Studi sulla dipendenza del parametro della matrice di Google sono fatti in [S4] e in [BRS]. Metodologie utilizzabili sono descritte in [FLM02]

[LM] A.Langville, C.Meyer, A survey of eigenvector methods for Web information retrieval. SIAM Rev. 47 (2005)
[KHG03]S.D.Kamvar, T.H.Haveliwala, G.H.Golub, Adaptive methods for the computation of Page Rank, Proc. Int. Conference on the Numer. Solution of Markov Chains, 2003.
[KHG03a]S.D.Kamvar, T.H.Haveliwala, C.Manning, G.H.Golub, Extrapolation methods for accelerating Page Rank compuattions. Proc. 12th Int. WWW Conference 2003.
[KHMG03b]S.D.Kamvar, T.H.Haveliwala, C.Manning, G.H.Golub, Exploiting the block structure of the Web for computing Page Rank, T.R., Stanford University 2003.
[FLM02] P.Favati, G.Lotti, O.Menchi, F.Romani, Railway computation for infinite linear systems. Intern. J. of Parallel Prog. 30:419-439, 2002
[S4] S.Serra C., Jordan canonical form of the Google matrix: a potential contribution to the PageRank computation. SIAM J. Matrix Anal.Appl. 27(2005) <<<