×
Benzi, Michele

Localization in matrix computations: theory and applications. (English) Zbl 1361.65027

Benzi, Michele (ed.) et al., Exploiting hidden structure in matrix computations: algorithms and applications. Cetraro, Italy, June 22–26, 2015. Lecture notes given at the summer course. Cham: Springer; Florence: Fondazione CIME (ISBN 978-3-319-49886-7/pbk; 978-3-319-49887-4/ebook). Lecture Notes in Mathematics 2173. CIME Foundation Subseries, 211-317 (2016).
Summary: Many important problems in mathematics and physics lead to (non-sparse) functions, vectors, or matrices in which the fraction of nonnegligible entries is vanishingly small compared the total number of entries as the size of the system tends to infinity. In other words, the nonnegligible entries tend to be localized, or concentrated, around a small region within the computational domain, with rapid decay away from this region (uniformly as the system size grows). When present, localization opens up the possibility of developing fast approximation algorithms, the complexity of which scales linearly in the size of the problem. While localization already plays an important role in various areas of quantum physics and chemistry, it has received until recently relatively little attention by researchers in numerical linear algebra. In this chapter we survey localization phenomena arising in various fields, and we provide unified theoretical explanations for such phenomena using general results on the decay behavior of matrix functions. We also discuss computational implications for a range of applications.
For the entire collection see [Zbl 1366.65001].

Cited in 18 Documents

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
15A16 Matrix exponential and similar functions of matrices
15A23 Factorization of matrices
65Y20 Complexity and performance of numerical algorithms

Keywords:

matrix exponential; matrix factorization; fast approximation algorithms; complexity; matrix function

Software:

Eigtool; Krylstat; SpAMM; SparseMatrix
Cite Review PDF
Full Text: DOI

References:

[1] M. Abramowitz, I. Stegun, Handbook of Mathematical Functions (Dover, New York, NY, 1965) · Zbl 0171.38503
[2] S. Agmon, Lectures on Exponential Decay of Solutions of Second-Order Elliptic Equations: Bounds on Eigenfunctions of N -Body Schrödinger Operators. Mathematical Notes, vol. 29 (Princeton University Press, Princeton, NJ; University of Tokyo Press, Tokyo, 1982) · Zbl 0503.35001
[3] G. Alléon, M. Benzi, L. Giraud, Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics. Numer. Algorithms 16, 1–15 (1997) · Zbl 0895.65017 · doi:10.1023/A:1019170609950
[4] P.W. Anderson, Absence of diffusion in certain random lattices. Phys. Rev. 109, 1492–1505 (1958) · doi:10.1103/PhysRev.109.1492
[5] M. Arioli, M. Benzi, A finite element method for quantum graphs. Math/CS Technical Report TR-2015-009, Emory University, Oct 2015 · Zbl 1462.65176
[6] E. Aune, D.P. Simpson, J. Eidsvik, Parameter estimation in high dimensional Gaussian distributions. Stat. Comput. 24, 247–263 (2014) · Zbl 1325.62006 · doi:10.1007/s11222-012-9368-y
[7] O. Axelsson, Iterative Solution Methods (Cambridge University Press, Cambridge, 1994) · doi:10.1017/CBO9780511624100
[8] O. Axelsson, B. Polman, On approximate factorization methods for block matrices suitable for vector and parallel processors. Linear Algebra Appl. 77, 3–26 (1986) · Zbl 0587.65013 · doi:10.1016/0024-3795(86)90159-X
[9] R. Baer, M. Head-Gordon, Sparsity of the density matrix in Kohn–Sham density functional theory and an assessment of linear system-size scaling methods. Phys. Rev. Lett. 79, 3962–3965 (1997) · doi:10.1103/PhysRevLett.79.3962
[10] R. Baer, M. Head-Gordon, Chebyshev expansion methods for electronic structure calculations on large molecular systems. J. Chem. Phys. 107, 10003–10013 (1997) · doi:10.1063/1.474158
[11] H. Bağci, J.E. Pasciak, K.Y. Sirenko, A convergence analysis for a sweeping preconditioner for block tridiagonal systems of linear equations. Numer. Linear Algebra Appl. 22, 371–392 (2015) · Zbl 1363.65040 · doi:10.1002/nla.1961
[12] A.G. Baskakov, Wiener’s theorem and the asymptotic estimates of the elements of inverse matrices. Funct. Anal. Appl. 24, 222–224 (1990) · Zbl 0728.47021 · doi:10.1007/BF01077964
[13] A.G. Baskakov, Estimates for the entries of inverse matrices and the spectral analysis of linear operators. Izv. Math. 61, 1113–1135 (1997) · Zbl 0911.47003 · doi:10.1070/IM1997v061n06ABEH000164
[14] R. Bellman, Introduction to Matrix Analysis, 2nd edn. (McGraw-Hill, New York, NY, 1970)
[15] C.M. Bender, S. Boettcher, P.N. Meisinger, PT-symmetric quantum mechanics. J. Math. Phys. 40, 2201–2229 (1999) · Zbl 1057.81512 · doi:10.1063/1.532860
[16] C.M. Bender, D.C. Brody, H.F. Jones, Must a Hamiltonian be Hermitian? Am. J. Phys. 71, 1095–1102 (2003) · Zbl 1219.81125 · doi:10.1119/1.1574043
[17] M. Benzi, Preconditioning techniques for large linear systems: a survey. J. Comp. Phys. 182, 418–477 (2002) · Zbl 1015.65018 · doi:10.1006/jcph.2002.7176
[18] M. Benzi, P. Boito, Quadrature rule-based bounds for functions of adjacency matrices. Linear Algebra Appl. 433, 637–652 (2010) · Zbl 1191.65046 · doi:10.1016/j.laa.2010.03.035
[19] M. Benzi, P. Boito, Decay properties for functions of matrices over C -algebras. Linear Algebra Appl. 456, 174–198 (2014) · Zbl 1314.47020 · doi:10.1016/j.laa.2013.11.027
[20] M. Benzi, G.H. Golub, Bounds for the entries of matrix functions with applications to preconditioning. BIT Numer. Math. 39, 417–438 (1999) · Zbl 0934.65054 · doi:10.1023/A:1022362401426
[21] M. Benzi, N. Razouk, Decay bounds and O(n) algorithms for approximating functions of sparse matrices. Electron. Trans. Numer. Anal. 28, 16–39 (2007) · Zbl 1171.65034
[22] M. Benzi, V. Simoncini, Decay bounds for functions of Hermitian matrices with banded or Kronecker structure. SIAM J. Matrix Anal. Appl. 36, 1263–1282 (2015) · Zbl 1323.15005 · doi:10.1137/151006159
[23] M. Benzi, M. Tuma, A sparse approximate inverse preconditioner for nonsymmetric linear systems. SIAM J. Sci. Comput. 19, 968–994 (1998) · Zbl 0930.65027 · doi:10.1137/S1064827595294691
[24] M. Benzi, M. Tuma, Orderings for factorized approximate inverse preconditioners. SIAM J. Sci. Comput. 21, 1851–1868 (2000) · Zbl 0959.65047 · doi:10.1137/S1064827598339372
[25] M. Benzi, C.D. Meyer, M. Tuma, A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM J. Sci. Comput. 17, 1135–1149 (1996) · Zbl 0856.65019 · doi:10.1137/S1064827594271421
[26] M. Benzi, P. Boito, N. Razouk, Decay properties of spectral projectors with applications to electronic structure. SIAM Rev. 55, 3–64 (2013) · Zbl 1377.65155 · doi:10.1137/100814019
[27] M. Benzi, T. Evans, S. Hamilton, M. Lupo Pasini, S. Slattery, Analysis of Monte Carlo accelerated iterative methods for sparse linear systems. Math/CS Technical Report TR-2016-002, Emory University. Numer. Linear Algebra Appl. 2017, to appear · Zbl 1449.65098
[28] S.K. Berberian, G.H. Orland, On the closure of the numerical range of an operator. Proc. Am. Math. Soc. 18, 499–503 (1967) · Zbl 0173.42104 · doi:10.1090/S0002-9939-1967-0212588-5
[29] L. Bergamaschi, M. Vianello, Efficient computation of the exponential operator for large, sparse, symmetric matrices. Numer. Linear Algebra Appl. 7, 27–45 (2000) · Zbl 0983.65058 · doi:10.1002/(SICI)1099-1506(200001/02)7:1<27::AID-NLA185>3.0.CO;2-4
[30] L. Bergamaschi, M. Caliari, M. Vianello, Efficient approximation of the exponential operator for discrete 2D advection-diffusion problems. Numer. Linear Algebra Appl. 10, 271–289 (2003) · Zbl 1071.65048 · doi:10.1002/nla.288
[31] D.A. Bini, G. Latouche, B. Meini, Numerical Methods for Structured Markov Chains (Oxford University Press, Oxford, 2005) · Zbl 1076.60002 · doi:10.1093/acprof:oso/9780198527688.001.0001
[32] D.A. Bini, S. Dendievel, G. Latouche, B. Meini, Computing the exponential of large block-triangular block-Toeplitz matrices encountered in fluid queues. Linear Algebra Appl. 502, 387–419 (2016) · Zbl 1386.65129 · doi:10.1016/j.laa.2015.03.035
[33] I.A. Blatov, Incomplete factorization methods for systems with sparse matrices. Comput. Math. Math. Phys. 33, 727–741 (1993) · Zbl 0804.65026
[34] I.A. Blatov, On algebras and applications of operators with pseudosparse matrices. Siber. Math. J. 37, 32–52 (1996) · Zbl 0874.65034 · doi:10.1007/BF02104758
[35] I.A. Blatov, A.A. Terteryan, Estimates of the elements of the inverse matrices and pivotal condensation methods of incomplete block factorization. Comput. Math. Math. Phys. 32, 1509–1522 (1992)
[36] N. Bock, M. Challacombe, An optimized sparse approximate matrix multiply for matrices with decay. SIAM J. Sci. Comput. 35, C72–C98 (2013) · Zbl 1264.65062 · doi:10.1137/120870761
[37] N. Bock, M. Challacombe, L.V. Kalé, Solvers for \[ \mathcal{O}(N) \] electronic structure in the strong scaling limit. SIAM J. Sci. Comput. 38, C1–C21 (2016) · Zbl 1336.65054 · doi:10.1137/140974602
[38] L. Bonaventura, Local exponential methods: a domain decomposition approach to exponential time integration of PDEs. arXiv:1505.02248v1, May 2015
[39] F. Bonchi, P. Esfandiar, D.F. Gleich, C. Greif, L.V.S. Lakshmanan, Fast matrix computations for pair-wise and column-wise commute times and Katz scores. Internet Math. 8, 73–112 (2012) · Zbl 1245.05026 · doi:10.1080/15427951.2012.625256
[40] A. Böttcher, S.M. Grudsky, Spectral Properties of Banded Toeplitz Matrices (Society for Industrial and Applied Mathematics, Philadelphia, PA, 2005) · Zbl 1089.47001 · doi:10.1137/1.9780898717853
[41] A. Böttcher, B. Silbermann, Introduction to Large Truncated Toeplitz Matrices (Springer, New York, NY, 1998)
[42] D.R. Bowler, T. Miyazaki, O(N) methods in electronic structure calculations. Rep. Prog. Phys. 75, 036503 (2012) · doi:10.1088/0034-4885/75/3/036503
[43] S. Brooks, E. Lindenstrauss, Non-localization of eigenfunctions on large regular graphs. Isr. J. Math. 193, 1–14 (2013) · Zbl 1317.05110 · doi:10.1007/s11856-012-0096-y
[44] C. Brouder, G. Panati, M. Calandra, C. Mourougane, N. Marzari, Exponential localization of Wannier functions in insulators. Phys. Rev. Lett. 98, 046402 (2007) · doi:10.1103/PhysRevLett.98.046402
[45] S. Bruciapaglia, S. Micheletti, S. Perotto, Compressed solving: a numerical approximation technique for elliptic PDEs based on compressed sensing. Comput. Math. Appl. 70, 1306–1335 (2015) · doi:10.1016/j.camwa.2015.07.015
[46] K. Bryan, T. Lee, Making do with less: an introduction to compressed sensing. SIAM Rev. 55, 547–566 (2013) · Zbl 1306.94009 · doi:10.1137/110837681
[47] C. Canuto, V. Simoncini, M. Verani, On the decay of the inverse of matrices that are sum of Kronecker products. Linear Algebra Appl. 452, 21–39 (2014) · Zbl 1291.65144 · doi:10.1016/j.laa.2014.03.029
[48] C. Canuto, V. Simoncini, M. Verani, Contraction and optimality properties of an adaptive Legendre–Galerkin method: the multi-dimensional case. J. Sci. Comput. 63, 769–798 (2015) · Zbl 1325.65151 · doi:10.1007/s10915-014-9912-3
[49] M. Challacombe, A simplified density matrix minimization for linear scaling self-consistent field theory. J. Chem. Phys. 110, 2332–2342 (1999) · doi:10.1063/1.477969
[50] T. Chan, W.-P. Tang, J. Wan, Wavelet sparse approximate inverse preconditioners. BIT Numer. Math. 37, 644–660 (1997) · Zbl 0891.65048 · doi:10.1007/BF02510244
[51] J. Chandrasekar, D.S. Bernstein, Correlation bounds for discrete-time systems with banded dynamics. Syst. Control Lett. 56, 83–86 (2007) · Zbl 1120.93366 · doi:10.1016/j.sysconle.2006.07.014
[52] E. Chow, A priori sparsity patterns for parallel sparse approximate inverse preconditioners. SIAM J. Sci. Comput. 21, 1804–1822 (2000) · Zbl 0957.65023 · doi:10.1137/S106482759833913X
[53] J.-M. Combes, L. Thomas, Asymptotic behaviour of eigenfunctions for multiparticle Schrödinger operators. Commun. Math. Phys. 34, 251–270 (1973) · Zbl 0271.35062 · doi:10.1007/BF01646473
[54] P. Concus, G.H. Golub, G. Meurant, Block preconditioning for the conjugate gradient method. SIAM J. Sci. Stat. Comput. 6, 220–252 (1985) · Zbl 0556.65022 · doi:10.1137/0906018
[55] M. Cramer, J. Eisert, Correlations, spectral gap and entanglement in harmonic quantum systems on generic lattices. New J. Phys. 8, 71 (2006) · doi:10.1088/1367-2630/8/5/071
[56] M. Cramer, J. Eisert, M.B. Plenio, J. Dreissig, Entanglement-area law for general Bosonic harmonic lattice systems. Phys. Rev. A 73, 012309 (2006) · doi:10.1103/PhysRevA.73.012309
[57] M. Crouzeix, Numerical range and functional calculus in Hilbert space. J. Funct. Anal. 244, 668–690 (2007) · Zbl 1116.47004 · doi:10.1016/j.jfa.2006.10.013
[58] C.K. Chui, M. Hasson, Degree of uniform approximation on disjoint intervals. Pac. J. Math. 105, 291–297 (1983) · Zbl 0508.30037 · doi:10.2140/pjm.1983.105.291
[59] J.J.M. Cuppen, A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math. 36, 177–195 (1981) · Zbl 0431.65022 · doi:10.1007/BF01396757
[60] S. Dahlke, M. Fornasier, K. Gröchenig, Optimal adaptive computations in the Jaffard algebra and localized frames. J. Approx. Theory 162, 153–185 (2010) · Zbl 1184.42029 · doi:10.1016/j.jat.2009.04.001
[61] A. Damle, L. Lin, L. Ying, Compressed representations of Kohn–Sham orbitals via selected columns of the density matrix. J. Chem. Theory Comput. 11, 1463–1469 (2015) · doi:10.1021/ct500985f
[62] A. Damle, L. Lin, L. Ying, Accelerating selected columns of the density matrix computations via approximate column selection. arXiv:1604.06830v1, April 2016
[63] P.J. Davis, Circulant Matrices (Wiley, New York, 1979)
[64] T.A. Davis, Y. Hu, The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1–25 (2011) · Zbl 1365.65123
[65] Y. Dekel, J.R. Lee, N. Linial, Eigenvectors of random graphs: nodal domains. Random Struct. Algorithm 39, 39–58 (2011) · Zbl 1223.05275 · doi:10.1002/rsa.20330
[66] N. Del Buono, L. Lopez, R. Peluso, Computation of the exponential of large sparse skew-symmetric matrices. SIAM J. Sci. Comput. 27, 278–293 (2005) · Zbl 1108.65037 · doi:10.1137/030600758
[67] S. Demko, Inverses of band matrices and local convergence of spline projections. SIAM J. Numer. Anal. 14, 616–619 (1977) · Zbl 0367.65024 · doi:10.1137/0714041
[68] S. Demko, W.F. Moss, P.W. Smith, Decay rates for inverses of band matrices. Math. Comput. 43, 491–499 (1984) · Zbl 0568.15003 · doi:10.1090/S0025-5718-1984-0758197-9
[69] J. des Cloizeaux, Energy bands and projection operators in a crystal: analytic and asymptotic properties. Phys. Rev. 135, A685–A697 (1964) · doi:10.1103/PhysRev.135.A685
[70] I.S. Dhillon, B.S. Parlett, C. Vömel, The design and implementation of the MRRR algorithm. ACM Trans. Math. Softw. 32, 533–560 (2006) · Zbl 1230.65046 · doi:10.1145/1186785.1186788
[71] R. Diestel, Graph Theory (Springer, Berlin, 2000)
[72] I.S. Duff, A.M. Erisman, J.K. Reid, Direct Methods for Sparse Matrices (Oxford University Press, Oxford, 1986) · Zbl 0604.65011
[73] I. Dumitriu, S. Pal, Sparse regular random graphs: spectral density and eigenvectors. Ann. Prob. 40, 2197–2235 (2012) · Zbl 1255.05173 · doi:10.1214/11-AOP673
[74] W.E, J. Lu, The electronic structure of smoothly deformed crystals: Wannier functions and the Cauchy–Born rule. Arch. Ration. Mech. Anal. 199, 407–433 (2011) · Zbl 1253.74025 · doi:10.1007/s00205-010-0339-1
[75] V. Eijkhout, B. Polman, Decay rates of inverses of banded M-matrices that are near to Toeplitz matrices. Linear Algebra Appl. 109, 247–277 (1988) · Zbl 0654.15014 · doi:10.1016/0024-3795(88)90211-X
[76] J. Eisert, M. Cramer, M.B. Plenio, Colloquium: area laws for the entanglement entropy. Rev. Modern Phys. 82, 277–306 (2010) · Zbl 1205.81035 · doi:10.1103/RevModPhys.82.277
[77] S.W. Ellacott, Computation of Faber series with application to numerical polynomial approximation in the complex plane. Math. Comput. 40, 575–587 (1983) · Zbl 0512.65018 · doi:10.1090/S0025-5718-1983-0689474-7
[78] E. Estrada, The Structure of Complex Networks: Theory and Applications (Oxford University Press, Oxford, 2012)
[79] E. Estrada, N. Hatano, Communicability in complex networks. Phys. Rev. E 77, 036111 (2008) · Zbl 1284.05253 · doi:10.1103/PhysRevE.77.036111
[80] E. Estrada, D.J. Higham, Network properties revealed by matrix functions. SIAM Rev. 52, 696–714 (2010) · Zbl 1214.05077 · doi:10.1137/090761070
[81] E. Estrada, N. Hatano, M. Benzi, The physics of communicability in complex networks. Phys. Rep. 514, 89–119 (2012) · doi:10.1016/j.physrep.2012.01.006
[82] I. Faria, Permanental roots and the star degree of a graph. Linear Algebra Appl. 64, 255–265 (1985) · Zbl 0559.05041 · doi:10.1016/0024-3795(85)90281-2
[83] N.J. Ford, D.V. Savostyanov, N.L. Zamarashkin, On the decay of the elements of inverse triangular Toeplitz matrices. SIAM J. Matrix Anal. Appl. 35, 1288–1302 (2014) · Zbl 1317.15027 · doi:10.1137/130931734
[84] R. Freund, On polynomial approximations to f a (z)=(z - a)-1 with complex a and some applications to certain non-Hermitian matrices. Approx. Theory Appl. 5, 15–31 (1989) · Zbl 0693.41009
[85] I.M. Gelfand, Normierte Ringe. Mat. Sb. 9, 3–23 (1941)
[86] I.M. Gelfand, M.A. Neumark, On the imbedding of normed rings in the ring of operators in Hilbert space. Mat. Sb. 12, 197–213 (1943) · Zbl 0060.27006
[87] I.M. Gelfand, D.A. Raikov, G.E. Shilov, Commutative Normed Rings (Chelsea Publishing Co., Bronx/New York, 1964)
[88] P.-L. Giscard, K. Lui, S.J. Thwaite, D. Jaksch, An exact formulation of the time-ordered exponential using path-sums. J. Math. Phys. 56, 053503 (2015) · Zbl 1316.15010 · doi:10.1063/1.4920925
[89] D.F. Gleich, PageRank beyond the Web. SIAM Rev. 57, 321–363 (2015) · Zbl 1336.05122 · doi:10.1137/140976649
[90] D.F. Gleich, K. Kloster, Sublinear column-wise actions of the matrix exponential on social networks. Internet Math. 11, 352–384 (2015) · doi:10.1080/15427951.2014.971203
[91] S. Goedecker, Linear scaling electronic structure methods. Rev. Mod. Phys. 71, 1085–1123 (1999) · doi:10.1103/RevModPhys.71.1085
[92] S. Goedecker, O.V. Ivanov, Frequency localization properties of the density matrix and its resulting hypersparsity in a wavelet representation. Phys. Rev. B 59, 7270–7273 (1999) · doi:10.1103/PhysRevB.59.7270
[93] K.-I. Goh, B. Khang, D. Kim, Spectra and eigenvectors of scale-free networks. Phys. Rev. E 64, 051903 (2001) · doi:10.1103/PhysRevE.64.051903
[94] G.H. Golub, G. Meurant, Matrices, Moments and Quadrature with Applications (Princeton University Press, Princeton, NJ, 2010)
[95] G.H. Golub, C.F. Van Loan, Matrix Computations, 4th edn. (Johns Hopkins University Press, Baltimore/London, 2013) · Zbl 1268.65037
[96] K. Gröchenig, A. Klotz, Noncommutative approximation: inverse-closed subalgebras and off-diagonal decay of matrices. Constr. Approx. 32, 429–466 (2010) · Zbl 1210.41010 · doi:10.1007/s00365-010-9101-z
[97] K. Gröchenig, M. Leinert, Symmetry and inverse-closedness of matrix algebras and functional calculus for infinite matrices. Trans. Am. Math. Soc. 358, 2695–2711 (2006) · Zbl 1105.46032 · doi:10.1090/S0002-9947-06-03841-4
[98] K. Gröchenig, Z. Rzeszotnik, T. Strohmer, Convergence analysis of the finite section method and Banach algebras of matrices. Integr. Equ. Oper. Theory 67, 183–202 (2010) · Zbl 1197.65053 · doi:10.1007/s00020-010-1775-x
[99] M. Grote, T. Huckle, Parallel preconditioning with sparse approximate inverses. SIAM J. Sci. Comput. 18, 838–853 (1997) · Zbl 0872.65031 · doi:10.1137/S1064827594276552
[100] J. Gutiérrez-Gutiérrez, P.M. Crespo, A. Böttcher, Functions of the banded Hermitian block Toeplitz matrices in signal processing. Linear Algebra Appl. 422, 788–807 (2007) · Zbl 1115.47059 · doi:10.1016/j.laa.2006.12.008
[101] S. Güttel, L. Knizhnerman, A black-box rational Arnoldi variant for Cauchy–Stieltjes matrix functions. BIT Numer. Math. 53, 595–616 (2013) · Zbl 1276.65026 · doi:10.1007/s10543-013-0420-x
[102] A. Haber, M. Verhaegen, Subspace identification of large-scale interconnected systems. IEEE Trans. Automat. Control 59, 2754–2759 (2014) · Zbl 1360.93181 · doi:10.1109/TAC.2014.2310375
[103] A. Haber, M. Verhaegen, Sparse solution of the Lyapunov equation for large-scale interconnected systems. Automatica 73, 256–268 (2016) · Zbl 1371.93029 · doi:10.1016/j.automatica.2016.06.002
[104] M. Hasson, The degree of approximation by polynomials on some disjoint intervals in the complex plane. J. Approx. Theory 144, 119–132 (2007) · Zbl 1107.30030 · doi:10.1016/j.jat.2006.05.003
[105] L. He, D. Vanderbilt, Exponential decay properties of Wannier functions and related quantities. Phys. Rev. Lett. 86, 5341–5344 (2001) · doi:10.1103/PhysRevLett.86.5341
[106] V.E. Henson, G. Sanders, Locally supported eigenvectors of matrices associated with connected and unweighted power-law graphs. Electron. Trans. Numer. Anal. 39, 353–378 (2012) · Zbl 1286.05089
[107] N.J. Higham, Matrix Functions. Theory and Computation (Society for Industrial and Applied Mathematics, Philadelphia, PA, 2008) · Zbl 1167.15001 · doi:10.1137/1.9780898717778
[108] N.J. Higham, D.S. Mackey, N. Mackey, F. Tisseur, Functions preserving matrix groups and iterations for the matrix square root. SIAM J. Matrix Anal. Appl. 26, 1178–1192 (2005) · Zbl 1066.65033
[109] M. Hochbruck, Ch. Lubich, On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 34, 1911–1925 (1997) · Zbl 0888.65032 · doi:10.1137/S0036142995280572
[110] P. Hohenberg, W. Kohn, Inhomogeneous electron gas. Phys. Rev. 136, B864–871 (1964) · doi:10.1103/PhysRev.136.B864
[111] R.A. Horn, C.R. Johnson, Topics in Matrix Analysis (Cambridge University Press, Cambridge, 1994) · Zbl 0801.15001
[112] R.A. Horn, C.R. Johnson, Matrix Analysis, 2nd edn. (Cambridge University Press, Cambridge, 2013) · Zbl 1267.15001
[113] T. Huckle, Approximate sparsity patterns for the inverse of a matrix and preconditioning. Appl. Numer. Math. 30, 291–303 (1999) · Zbl 0927.65045 · doi:10.1016/S0168-9274(98)00117-2
[114] M. Hutchinson, A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Commun. Stat. Simul. Comput. 18, 1059–1076 (1989) · Zbl 0695.62113 · doi:10.1080/03610918908812806
[115] A. Iserles,How large is the exponential of a banded matrix? N. Z. J. Math. 29, 177–192 (2000) · Zbl 0968.22016
[116] S. Ismail-Beigi, T.A. Arias, Locality of the density matrix in metals, semiconductors, and insulators. Phys. Rev. Lett. 82, 2127–2130 (1999) · doi:10.1103/PhysRevLett.82.2127
[117] S. Jaffard, Propriétés des matrices ”bien localisées” près de leur diagonale et quelques applications. Ann. Inst. Henri Poincarè 7, 461–476 (1990)
[118] J. Janas, S. Naboko, G. Stolz, Decay bounds on eigenfunctions and the singular spectrum of unbounded Jacobi matrices. Intern. Math. Res. Notices 4, 736–764 (2009) · Zbl 1175.47029
[119] R. Kadison, Diagonalizing matrices. Am. J. Math. 106, 1451–1468 (1984) · Zbl 0585.46048 · doi:10.2307/2374400
[120] R. Kadison, J. Ringrose, Fundamentals of the Theory of Operator Algebras. Elementary Theory, vol. I (Academic Press, Orlando, FL, 1983) · Zbl 0518.46046
[121] W. Kohn, Analytic properties of Bloch waves and Wannier functions. Phys. Rev. 115, 809–821 (1959) · Zbl 0086.45101 · doi:10.1103/PhysRev.115.809
[122] W. Kohn, Density functional and density matrix method scaling linearly with the number of atoms. Phys. Rev. Lett. 76, 3168–3171 (1996) · doi:10.1103/PhysRevLett.76.3168
[123] W. Kohn, Nobel lecture: electronic structure of matter–wave functions and density functionals. Rev. Mod. Phys. 71, 1253–1266 (1999) · doi:10.1103/RevModPhys.71.1253
[124] W. Kohn, L.J. Sham, Self-consistent equations including exchange and correlation effects. Phys. Rev. Lett. 140, A1133–1138 (1965)
[125] L.Y. Kolotilina, A.Y. Yeremin, Factorized sparse approximate inverse preconditioning I. Theory. SIAM J. Matrix Anal. Appl. 14, 45–58 (1993) · Zbl 0767.65037 · doi:10.1137/0614004
[126] A. Koskela, E. Jarlebring, The infinite Arnoldi exponential integrator for linear inhomogeneous ODEs. arXiv:1502.01613v2, Feb 2015
[127] I. Kryshtal, T. Strohmer, T. Wertz, Localization of matrix factorizations. Found. Comput. Math. 15, 931–951 (2015) · Zbl 1341.15012 · doi:10.1007/s10208-014-9196-x
[128] R. Lai, J. Lu, Localized density matrix minimization and linear-scaling algorithms. J. Comput. Phys. 315, 194–210 (2016) · Zbl 1349.82007 · doi:10.1016/j.jcp.2016.02.076
[129] C.S. Lam, Decomposition of time-ordered products and path-ordered exponentials. J. Math. Phys. 39, 5543–5558 (1998) · Zbl 0986.81066 · doi:10.1063/1.532550
[130] A.N. Langville, C.D. Meyer Google’s PageRank and Beyond: The Science of Search Engine Rankings (Princeton University Press, Princeton, NJ, 2006) · Zbl 1104.68042
[131] A.J. Laub, Matrix Analysis for Scientists and Engineers (Society for Industrial and Applied Mathematics, Philadelphia, PA, 2005) · Zbl 1077.15001 · doi:10.1137/1.9780898717907
[132] C. Le Bris, Computational chemistry from the perspective of numerical analysis. Acta Numer. 14, 363–444 (2005) · Zbl 1119.65390 · doi:10.1017/S096249290400025X
[133] X.-P. Li, R.W. Nunes, D. Vanderbilt, Density-matrix electronic structure method with linear system-size scaling. Phys. Rev. B 47, 10891–10894 (1993) · doi:10.1103/PhysRevB.47.10891
[134] W. Liang, C. Saravanan, Y. Shao, R. Baer, A. T. Bell, M. Head-Gordon, Improved Fermi operator expansion methods for fast electronic structure calculations. J. Chem. Phys. 119, 4117–4124 (2003) · doi:10.1063/1.1590632
[135] L. Lin, Localized spectrum slicing. Math. Comput. (2016, to appear). DOI:10.1090/mcom/3166 · Zbl 1364.65085 · doi:10.1090/mcom/3166
[136] L. Lin, J. Lu, Sharp decay estimates of discretized Green’s functions for Schrödinger type operators. Sci. China Math. 59, 1561–1578 (2016) · Zbl 1354.65218 · doi:10.1007/s11425-016-0311-4
[137] F.-R. Lin, M.K. Ng, W.-K. Ching, Factorized banded inverse preconditioners for matrices with Toeplitz structure. SIAM J. Sci. Comput. 26, 1852–1870 (2005) · Zbl 1080.65036 · doi:10.1137/030601272
[138] L. Lin, J. Lu, L. Ying, R. Car, E. Weinan, Multipole representation of the Fermi operator with application to the electronic structure analysis of metallic systems. Phys. Rev. B 79, 115133 (2009) · Zbl 1182.65072 · doi:10.1103/PhysRevB.79.115133
[139] M. Lindner, Infinite Matrices and Their Finite Sections (Birkhäuser, Basel, 2006)
[140] X. Liu, G. Strang, S. Ott, Localized eigenvectors from widely spaced matrix modifications. SIAM J. Discrete Math. 16, 479–498 (2003) · Zbl 1037.15009 · doi:10.1137/S0895480102409048
[141] L. Lopez, A. Pugliese, Decay behaviour of functions of skew-symmetric matrices, in Proceedings of HERCMA 2005, 7th Hellenic-European Conference on Computer Mathematics and Applications, 22–24 Sept 2005, Athens, ed. By E.A. Lipitakis, Electronic Editions (LEA, Athens, 2005)
[142] T. Malas, L. Gürel, Schur complement preconditioners for surface integral-equation formulations of dielectric problems solved with the multilevel multipole algorithm. SIAM J. Sci. Comput. 33, 2440–2467 (2011) · Zbl 1232.65007 · doi:10.1137/090780808
[143] A.I. Markushevich, Theory of Functions of a Complex Variable, vol. III (Prentice-Hall, Englewood Cliffs, NJ, 1967) · Zbl 0148.05201
[144] O.A. Marques, B.N. Parlett, C. Vömel, Computation of eigenpair subsets with the MRRR algorithm. Numer. Linear Algebra Appl. 13, 643–653 (2006) · Zbl 1174.65369 · doi:10.1002/nla.493
[145] R.M. Martin, Electronic Structure. Basic Theory and Practical Methods (Cambridge University Press, Cambridge, 2004) · doi:10.1017/CBO9780511805769
[146] P.E. Maslen, C. Ochsenfeld, C.A. White, M.S. Lee, M. Head-Gordon, Locality and sparsity of ab initio one-particle density matrices and localized orbitals. J. Phys. Chem. A 102, 2215–2222 (1998) · doi:10.1021/jp972919j
[147] N. Mastronardi, M.K. Ng, E.E. Tyrtyshnikov, Decay in functions of multi-band matrices. SIAM J. Matrix Anal. Appl. 31, 2721–2737 (2010) · Zbl 1228.65070 · doi:10.1137/090758374
[148] G. Meinardus, Approximation of Functions: Theory and Numerical Methods. Springer Tracts in Natural Philosophy, vol. 13 (Springer, New York, 1967) · doi:10.1007/978-3-642-85643-3
[149] P.N. McGraw, M. Menzinger, Laplacian spectra as a diagnostic tool for network structure and dynamics. Phys. Rev. E 77, 031102 (2008) · doi:10.1103/PhysRevE.77.031102
[150] N. Merkle, Completely monotone functions–a digest. arXiv:1211.0900v1, Nov 2012
[151] G. Meurant, A review of the inverse of symmetric tridiagonal and block tridiagonal matrices. SIAM J. Matrix Anal. Appl. 13, 707–728 (1992) · Zbl 0754.65029 · doi:10.1137/0613045
[152] N. Moiseyev, Non-Hermitian Quantum Mechanics (Cambridge University Press, Cambridge, 2011) · Zbl 1230.81004 · doi:10.1017/CBO9780511976186
[153] L. Molinari, Identities and exponential bounds for transfer matrices. J. Phys. A: Math. Theor. 46, 254004 (2013) · Zbl 1271.82010 · doi:10.1088/1751-8113/46/25/254004
[154] R. Nabben, Decay rates of the inverse of nonsymmetric tridiagonal and band matrices. SIAM J. Matrix Anal. Appl. 20, 820–837 (1999) · Zbl 0931.15001 · doi:10.1137/S0895479897317259
[155] Y. Nakatsukasa, Eigenvalue perturbation bounds for Hermitian block tridiagonal matrices. Appl. Numer. Math. 62, 67–78 (2012) · Zbl 1234.15005 · doi:10.1016/j.apnum.2011.09.010
[156] Y. Nakatsukasa, N. Saito, E. Woei, Mysteries around the graph Laplacian eigenvalue 4. Linear Algebra Appl. 438, 3231–3246 (2013) · Zbl 1262.05102 · doi:10.1016/j.laa.2012.12.012
[157] H. Nassar, K. Kloster, D.F. Gleich, Strong localization in personalized PageRank vectors, in Algorithms and Models for the Web Graph, ed. by D.F. Gleich et al. Lecture Notes in Computer Science, vol. 9479 (Springer, New York, 2015), pp. 190–202 · Zbl 1342.05170 · doi:10.1007/978-3-319-26784-5_15
[158] G. Nenciu, Existence of the exponentially localised Wannier functions. Commun. Math. Phys. 91, 81–85 (1983) · Zbl 0545.47012 · doi:10.1007/BF01206052
[159] A.M.N. Niklasson, Density matrix methods in linear scaling electronic structure theory, in Linear-Scaling Techniques in Computational Chemistry and Physics, ed. by R. Zaleśny et al. (Springer, New York, 2011), pp. 439–473 · doi:10.1007/978-90-481-2853-2_16
[160] J. Pan, R. Ke, M.K. Ng, H.-W. Sun, Preconditioning techniques for diagonal-times-Toeplitz matrices in fractional diffusion equations. SIAM. J. Sci. Comput. 36, A2698–A2719 (2014) · Zbl 1314.65112 · doi:10.1137/130931795
[161] B.N. Parlett, Invariant subspaces for tightly clustered eigenvalues of tridiagonals. BIT Numer. Math. 36, 542–562 (1996) · Zbl 0856.15009 · doi:10.1007/BF01731933
[162] B.N. Parlett, A result complementary to Geršgorin’s circle theorem. Linear Algebra Appl. 432, 20–27 (2009) · Zbl 1176.15025 · doi:10.1016/j.laa.2009.01.030
[163] B.N. Parlett, I.S. Dhillon, Relatively robust representations of symmetric tridiagonals. Linear Algebra Appl. 309, 121–151 (2000) · Zbl 0948.65026 · doi:10.1016/S0024-3795(99)00262-1
[164] M.S. Paterson, L.J. Stockmeyer, On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2, 60–66 (1973) · Zbl 0262.65033 · doi:10.1137/0202007
[165] E. Prodan, Nearsightedness of electronic matter in one dimension. Phys. Rev. B 73, 085108 (2006) · doi:10.1103/PhysRevB.73.085108
[166] E. Prodan, W. Kohn, Nearsightedness of electronic matter. Proc. Nat. Acad. Sci., 102, 11635–11638 (2005) · doi:10.1073/pnas.0505436102
[167] E. Prodan, S.R. Garcia, M. Putinar, Norm estimates of complex symmetric operators applied to quantum systems. J. Phys. A: Math. Gen. 39, 389–400 (2006) · Zbl 1088.81045 · doi:10.1088/0305-4470/39/2/009
[168] N. Razouk, Localization phenomena in matrix functions: theory and algorithms, Ph.D. Thesis, Emory University, 2008
[169] L. Reichel, G. Rodriguez, T. Tang, New block quadrature rules for the approximation of matrix functions. Linear Algebra Appl. 502, 299–326 (2016) · Zbl 1338.65122 · doi:10.1016/j.laa.2015.07.007
[170] S. Roch, Finite Sections of Band-Dominated Operators, vol. 191, no. 895 (Memoirs of the American Mathematical Society, Providence, RI, 2008) · Zbl 1167.47015
[171] G. Rodriguez, S. Seatzu, D. Theis, An algorithm for solving Toeplitz systems by embedding in infinite systems. Oper. Theory Adv. Appl. 160, 383–401 (2005) · Zbl 1084.65031
[172] E.H. Rubensson, E. Rudberg, P. Salek, Methods for Hartree–Fock and density functional theory electronic structure calculations with linearly scaling processor time and memory usage, in Linear-Scaling Techniques in Computational Chemistry and Physics, ed. by R. Zaleśny et al. (Springer, New York, NY, 2011), pp. 269–300
[173] W. Rudin, Functional Analysis (McGraw-Hill, New York, NY, 1973)
[174] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edn. (Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003) · doi:10.1137/1.9780898718003
[175] Y. Saad, J.R. Chelikowsky, S.M. Shontz, Numerical methods for electronic structure calculations of materials. SIAM Rev. 52, 3–54 (2010) · Zbl 1185.82004 · doi:10.1137/060651653
[176] N. Schuch, J.I. Cirac, M.M. Wolf, Quantum states on harmonic lattices. Commun. Math. Phys. 267, 65–92 (2006) · Zbl 1110.82015 · doi:10.1007/s00220-006-0049-6
[177] M. Shao, On the finite section method for computing exponentials of doubly-infinite skew-Hermitian matrices. Linear Algebra Appl. 451, 65–96 (2014) · Zbl 1291.65145 · doi:10.1016/j.laa.2014.03.021
[178] D.I. Shuman, B. Ricaud, P. Vandergheynst, Vertex-frequency analysis on graphs. Appl. Comput. Harmon. Anal. 40, 260–291 (2016) · Zbl 1403.94031 · doi:10.1016/j.acha.2015.02.005
[179] C. Siefert, E. de Sturler, Probing methods for saddle-point problems. Electron. Trans. Numer. Anal. 22, 163–183 (2006) · Zbl 1112.65029
[180] B. Simon, Semiclassical analysis of low lying eigenvalues. I. Nondegenerate minima: asymptotic expansions. Ann. Inst. H. Poincaré Sect. A 38, 295–308 (1983)
[181] V. Simoncini, Computational methods for linear matrix equations. SIAM Rev. 58, 377–441 (2016) · Zbl 1386.65124 · doi:10.1137/130912839
[182] D.T. Smith, Exponential decay of resolvents and discrete eigenfunctions of banded infinite matrices. J. Approx. Theory 66, 83–97 (1991) · Zbl 0731.15006 · doi:10.1016/0021-9045(91)90058-I
[183] G. Stolz, An introduction to the mathematics of Anderson localization, in Entropy and the Quantum II, ed. by R. Sims, D. Ueltschi. Contemporary Mathematics, vol. 552 (American Mathematical Society, Providence, RI, 2011), pp. 71–108 · Zbl 1244.82031
[184] G. Strang, S. MacNamara, Functions of difference matrices are Toeplitz plus Hankel. SIAM Rev. 56, 525–546 (2014) · Zbl 1304.65195 · doi:10.1137/120897572
[185] T. Strohmer, Four short stories about Toeplitz matrix calculations. Linear Algebra Appl. 343/344, 321–344 (2002) · Zbl 0999.65026 · doi:10.1016/S0024-3795(01)00243-9
[186] Q. Sun, Wiener’s lemma for infinite matrices with polynomial off-diagonal decay. C. R. Acad. Sci. Paris Ser. I 340, 567–570 (2005) · Zbl 1069.42018 · doi:10.1016/j.crma.2005.03.002
[187] P. Suryanarayana, On spectral quadrature for linear-scaling density functional theory. Chem. Phys. Lett. 584, 182–187 (2013) · doi:10.1016/j.cplett.2013.08.035
[188] H. Tal-Ezer, Polynomial approximation of functions of matrices and applications. J. Sci. Comput. 4, 25–60 (1989) · Zbl 0684.65040 · doi:10.1007/BF01061265
[189] L.V. Tran, V.H. Vu, K. Wang, Sparse random graphs: eigenvalues and eigenvectors. Random Struct. Algorithm. 42, 110–134 (2013) · Zbl 1257.05089 · doi:10.1002/rsa.20406
[190] L.N. Trefethen, Numerical computation of the Schwarz–Christoffel transformation. SIAM J. Sci. Stat. Comput. 1, 82–102 (1980) · Zbl 0451.30004 · doi:10.1137/0901004
[191] L.N. Trefethen, D. Bau, Numerical Linear Algebra (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997) · doi:10.1137/1.9780898719574
[192] L.N. Trefethen, M. Embree, Spectra and Pseudospectra. The Behavior of Nonnormal Matrices and Operators (Princeton University Press, Princeton, NJ, 2005) · Zbl 1085.15009
[193] L.N. Trefethen, M. Contedini, M. Embree, Spectra, pseudospectra, and localization for random bidiagonal matrices. Commun. Pure Appl. Math. 54, 595–623 (2001) · Zbl 1025.15034 · doi:10.1002/cpa.4
[194] C.V.M. van der Mee, G. Rodriguez, S. Seatzu, LDU factorization results for bi-infinite and semi-infinite scalar and block Toeplitz matrices. Calcolo 33, 307–335 (1998) · Zbl 0904.65035 · doi:10.1007/BF02576007
[195] C.V.M. van der Mee, G. Rodriguez, S. Seatzu, Block Cholesky factorization of infinite matrices and orthonormalization of vectors of functions, in Advances in Computational Mathematics (Guangzhou, 1997). Lecture Notes in Pure and Applied Mathematics (Dekker, New York, 1999), pp. 423–455 · Zbl 0931.65028
[196] R.S. Varga, Nonnegatively posed problems and completely monotonic functions. Linear Algebra Appl. 1, 329–347 (1968) · Zbl 0162.46802 · doi:10.1016/0024-3795(68)90013-X
[197] P.S. Vassilevski, On some ways of approximating inverses of band matrices in connection with deriving preconditioners based on incomplete block factorizations. Computing 43, 277–296 (1990) · Zbl 0691.65017 · doi:10.1007/BF02242922
[198] C. Vömel, B. N. Parlett, Detecting localization in an invariant subspace. SIAM J. Sci. Comput. 33, 3447–3467 (2011) · Zbl 1232.15011 · doi:10.1137/09077624X
[199] H. Wang, Q. Ye, Error bounds for the Krylov subspace methods for computations of matrix exponentials. Tech. Rep., Department of Mathematics, University of Kentucky, Lexington, KY, 2016 · Zbl 1365.65136
[200] H.F. Weinberger, A First Course in Partial Differential Equations (Wiley, New York, 1965) · Zbl 0127.04805
[201] D.V. Widder, The Laplace Transform (Princeton University Press, Princeton, 1946) · Zbl 0060.24801
[202] W. Yang, Direct calculation of electron density in density-functional theory. Phys. Rev. Lett. 66, 1438–1441 (1991) · Zbl 0788.34049 · doi:10.1103/PhysRevLett.66.1438
[203] Q. Ye, Error bounds for the Lanczos method for approximating matrix exponentials. SIAM J. Numer. Anal. 51, 68–87 (2013) · Zbl 1276.65027 · doi:10.1137/11085935X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.