L’approssimazione di funzioni di matrici si è rivelata un argomento molto va- sto: in questo elaborato abbiamo proposto approcci e metodi utilizzabili in molte occasioni, ma è chiaro che una altrettanto grande varietà di casi è rima- sta fuori dalla trattazione, a causa della non applicabilità di metodi o teoremi necessari per procedere.
Ogni risultato esposto si presta in modo naturale a poter essere generaliz- zato, con lo scopo di riuscire ad approssimare f (A) per una classe più ampia di matrici e funzioni.
Presentiamo qui di seguito alcuni problemi che sono rimasti aperti a eventuali trattazioni future.
1. Ipotesi di decadimento più deboli
Tra i risultati ottenuti in questo lavoro, il decadimento esponenziale è stato senza alcun dubbio uno dei più significativi, in quanto da quest’ultimo sono derivate le ottimizzazioni e l’effettiva convenienza degli algoritmi.
4.2. PROBLEMI APERTI 91
I risultati riguardanti questa proprietà hanno richiesto però ipotesi abbastanza forti sulla matrice A e sulla mappa f . Nel caso più generale (teorema 2.3.9) devono essere soddisfatte le seguenti proprietà:
• f definita su un dominio Ω ⊂ C compatto connesso e analitica su un suo particolare sottodominio.
• A diagonalizzabile e tale che σ(A) ⊂ Ω.
Notiamo che esse sono soltanto condizioni sufficienti: se il decadimento espo- nenziale venisse dimostrato utilizzando ipotesi più deboli (ad esempio rimuo- vendo la diagonalizzabilità di A), si riuscirebbe ad ampliare la portata di questo risultato, con conseguenti vantaggi computazionali in termini di efficienza e di un notevole risparmio di memoria.
2. Altri tipi di struttura
In questo elaborato ci siamo soffermati quasi esclusivamente su matrici dotate di una certa banda, provando risultati legati a questo caso specifico e imple- mentando metodi che sfruttassero tale struttura. Abbiamo inoltre visto come approssimare la banda su matrici con decadimento esponenziale.
Simili studi e analisi possono essere applicati a matrici che presentano strutture di tipo differente. Vediamone due esempi:
• Matrici sparse. Numericamente si è osservato che, se una matrice A di grandi dimensioni presenta soltanto pochi elementi aij non nulli, per
alcune mappe f la matrice f (A) presenta una curiosa proprietà: le sue entrate più significative sono concentrate vicino alle posizioni in cui si trovavano gli aij 6= 0, con un rapido decadimento man mano che ci si
allontana da tali posizioni (questo fenomeno si è notato in alcune appli- cazioni alla fisica, per maggiori dettagli consultare [18]).
Per matrici sparse diagonalizzabili, il teorema 2.3.9 ci garantisce un de- cadimento basato sul grafo associato: questo può essere un utile punto di partenza per analizzare nello specifico le matrici sparse e l’approssi- mazione delle loro valutazioni.
• Matrici con struttura di Kronecker. In un articolo di Benzi e Si- moncini (vedi [5]) è stato analizzato il problema di calcolare funzioni di matrici dotate di una particolare struttura detta somma di Kronecker, ossia che sono nella forma A = M1⊕ M2 = M1 ⊗ I + I ⊗ M2 ∈ C2n×2n,
con M1, M2 ∈ Cn×n quadrate. Si possono dimostrare curiose proprietà
su alcune funzioni nel momento in cui abbiano come argomenti matrici di questo tipo, ad esempio che exp(M1 ⊕ M2) = exp(M1) ⊗ exp(M2),
92 CAPITOLO 4. CONCLUSIONE
oppure che per seno e coseno valgono le formule di addizione, in cui gli argomenti sono M1 e M2 e le operazioni di somma e prodotto sono quel-
le di Kronecker (per dimostrazioni e approfondimenti, consultare [16] ai capitoli 10, 12).
Nel lavoro di Benzi e Simoncini vengono trovati bound di decadimento per f (A), derivati da quelli di f (M1) ed f (M2), nel caso in cui le funzio-
ni abbiano la proprietà di essere completamente monotone: per ulteriori dettagli si veda [4].
Ovviamente questi sono solo due esempi di possibili strutture, ma in generale è possibile indagare su quando si verifichi il decadimento esponenziale analiz- zando anche ulteriori tipi di matrici, qui non presentati.
3. Differenti tipologie di dominio
I requisiti dei teoremi sul decadimento e le implementazioni effettive dei metodi hanno sempre avuto la condizione che il dominio della mappa f fosse un’ellisse simmetrica rispetto all’asse reale.
In realtà questa ipotesi può essere rimossa, prendendo come dominio Ω un sottoinsieme di C che sia non vuoto, compatto e connesso. In questo nuovo contesto si avrebbero ad ogni modo alcune complicazioni a livello computazio- nale: ad esempio i polinomi di Faber non soddisferebbero più una relazione a tre termini e la mappa ψ (l’inversa della mappa di Riemann) avrebbe bisogno di ulteriore lavoro per essere determinata o approssimata (si veda [26]).
Il dominio Ω può essere anche scelto come unione di insiemi compatti e connessi (è utile farlo se lo spettro di A risulta essere concentrato in zone del piano complesso distanti fra loro). Questo caso può essere trattato in modo simile, ma sono necessari alcuni accorgimenti (per altri dettagli si consulti [25]).
4. Applicazione di nuovi metodi
Tutti e tre i metodi di approssimazione per funzioni di matrici che abbiamo fin qui sviluppato si basano su un unico approccio al problema, ossia la ri- cerca di un opportuno polinomio che rappresenti al meglio la funzione in un determinato dominio.
Pur non avendoli qui trattati esplicitamente, esistono alcuni metodi del tutto differenti, che usano i sottospazi di Krylov o alcune loro varianti [5]. Grazie a tali metodi si riesce a fornire nuovi efficienti bound di decadimen- to, nonché a ideare algoritmi specifici per approssimare il prodotto f (A) · b, con b ∈ Cn. Per ulteriori dettagli riguardanti quest’analisi si può consultare [4].
Bibliografia
[1] R. BAER, M. HEAD-GORDON, Chebyshev expansion methods for elec- tronic structure calculations on large molecular systems, J. Chem. Phys., 107 (1997)
[2] M. BENZI, G. H. GOLUB, Bounds for the entries of matrix functions with applications to preconditioning, BIT, 39 (1999)
[3] M. BENZI, N. RAZOUK, Decay bounds and O(n) algorithms for appro- ximating functions of sparse matrices, Electr. Trans. Numer. Anal., 28 (2007)
[4] M. BENZI, V. SIMONCINI, Approximation of functions of large matrices with Kronecker structure arXiv:1503.026 (2015)
[5] M. BENZI, V. SIMONCINI, Decay bounds for functions of matrices with banded or Kronecker structure, arXiv:1501.07376 (2015)
[6] L. BERGAMASCHI, M. CALIARI, M. VIANELLO, Efficient approxi- mation of the exponential operator for discrete 2D advection-diffusion problems, Numer. Linear Algebra Appl., 10 (2003)
[7] R. BEVILACQUA, D. BINI, M. CAPOVANI, O. MENCHI, Metodi Numerici, Zanichelli, 1992
[8] D. BINI , M. CAPOVANI, O. MENCHI Metodi Numerici per l’Algebra Lineare, Zanichelli, Bologna 1988
[9] C. BOLLIGER, D. KRESSNER, Linear scaling electronic structure methods, Rev. Mod. Phys., 71 (1999)
[10] H. CARTAN, Elementary Theory of Analytic Functions of One or Seve- ral Complex Variables, Republication of the Second edition, Unabridged Dover, 1995
94 BIBLIOGRAFIA
[11] C. DE BOOR, Dichotomies for band matrices, SIAMJ. Numer. Anal., v. 17, 1980
[12] S. DEMKO, W. F. MOSS, P. W. SMITH, Decay rates for inverses of band matrices, Math. Comp., 43 (1984)
[13] S. W. ELLACOTT, Computation of Faber series with application to nu- merical polynomial approximation in the complex plane, Math. Comp. , 40 (1983)
[14] A. FROMMER, V. SIMONCINI, Stopping criteria for rational ma- trix functions of Hermitian and symmetric matrices, Tech. Report, Dipartimento di Matematica, Università di Bologna, 2007.
[15] K.O. GEDDES, J.C. MASON, Polynomial Approximation by Projection on the Unit Circle, SIAM J. Numer. Anal. 12, No. 1 (1975)
[16] N. J. HIGHAM, Functions of matrices - Theory and Computation, L. Hogben, ed., Handbook of Linear Algebra, Chapman and Hall/CRC, Boca Raton, FL, 2006
[17] R. A. HORN, C. R. JOHNSON, Topics in Matrix Analysis, Cambridge University Press, 1991
[18] W. KOHN, Density functional and density matrix method scaling linearly with the number of atoms, Phys. Rev. Lett., 76 (1996)
[19] J. N. LYNESS, G. SANDE, Algorithm 413: Evaluation of normalised Taylor coefficients of an analytic function, Comm. ACM, v. 14, 1971
[20] A. I. MARKUSHEVICH, Theory of Functions of a Complex Variable, Vol. III, Prentice-Hall, Englewood Cliffs, NJ, 1967
[21] G. MEINARDUS, Approximation of functions: Theory and Numerical Methods, Springer-Verlag, New York, 1967
[22] I. MORET, P. NOVATI, The computation of functions of matrices by truncated Faber series, Numer. Funct. Anal. Optim., 22 (2001)
[23] V.I. SMIRNOV, N.A. LEBEDOV, Functions of a Complex Variable, London ILIFFE Books Ltd. (1968)
[24] G. STARKE, R. S. VARGA, A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations, Numerische Mathematik, 64 (1993)
BIBLIOGRAFIA 95
[25] H. TAL-EZER, Polynomial approximation of functions of matrices and applications, J. Sci. Comput., 4 (1989)
[26] L. N. TREFETHEN, Numerical computation of the Schwarz–Christoffel transformation, SIAMJ. Sci. Stat. Comput., 1 (1980)