The Library

On large-scale diagonalization techniques for the Anderson model of localization

Tools

Schenk, Olaf, Bollhofer, Matthias and Roemer, Rudolf A.. (2006) On large-scale diagonalization techniques for the Anderson model of localization. SIAM Journal on Scientific Computing, Vol.28 (No.3). pp. 963-983. ISSN 1064-8275

Preview

PDF
WRAP_Roemer_On-large-scale-diagonalization.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (6Mb)

Official URL: http://dx.doi.org/10.1137/050637649

Abstract

We propose efficient preconditioning algorithms for an eigenvalue problem arising in quantum physics, namely the computation of a few interior eigenvalues and their associated eigenvectors for large-scale sparse real and symmetric indefinite matrices of the Anderson model of localization. We compare the Lanczos algorithm in the 1987 implementation by Cullum and Willoughby with the shift-and-invert techniques in the implicitly restarted Lanczos method and in the Jacobi–Davidson method. Our preconditioning approaches for the shift-and-invert symmetric indefinite linear system are based on maximum weighted matchings and algebraic multilevel incomplete LDLT factorizations. These techniques can be seen as a complement to the alternative idea of using more complete pivoting techniques for the highly ill-conditioned symmetric indefinite Anderson matrices. We demonstrate the effectiveness and the numerical accuracy of these algorithms. Our numerical examples reveal that recent algebraic multilevel preconditioning solvers can accelerate the computation of a large-scale eigenvalue problem corresponding to the Anderson model of localization by several orders of magnitude.

Item Type:	Journal Article
Subjects:	Q Science > QC Physics
Divisions:	Faculty of Science > Centre for Scientific Computing Faculty of Science > Physics
Library of Congress Subject Headings (LCSH):	Eigenvalues, Anderson model
Journal or Publication Title:	SIAM Journal on Scientific Computing
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	1064-8275
Date:	19 June 2006
Volume:	Vol.28
Number:	No.3
Page Range:	pp. 963-983
Identification Number:	10.1137/050637649
Status:	Peer Reviewed
Access rights to Published version:	Open Access
Funder:	Swiss Commission for Technology and Innovation (CTI), Engineering and Physical Sciences Research Council (EPSRC)
Grant number:	7036 ENS-ES (CTI), EP/C007042/1 (EPSRC)
Related URLs:	Related item in WRAP Related item in WRAP
References:	[1] P. R. Amestoy, T. A. Davis, and I. S. Duff, An approximate minimum degree ordering algorithm, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 886–905. [2] P. W. Anderson, Absence of diffusion in certain random lattices, Phys. Rev., 109 (1958), pp. 1492–1505. [3] H. Aoki, Fractal dimensionality of wave functions at the mobility edge: Quantum fractal in the Landau levels, Phys. Rev. B, 33 (1986), pp. 7310–7313. [4] P. Arbenz and R. Geus, Multilevel preconditioned iterative eigensolvers for Maxwell eigenvalue problems, Appl. Numer. Math., 54 (2005), pp. 107–121. [5] M. Benzi, Preconditioning techniques for large linear systems: A survey, J. Comput. Phys., 182 (2002), pp. 418–477. [6] M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), pp. 1–137. [7] M. Benzi, J. C. Haws, and M. T˚uma, Preconditioning highly indefinite and nonsymmetric matrices, SIAM J. Sci. Comput., 22 (2000), pp. 1333–1353. [8] M. Bollh¨ofer and Y. Saad, Multilevel preconditioners constructed from inverse-based ILUs, SIAM J. Sci. Comput., 27 (2006), pp. 1627–1650. [9] M. Bollh¨ofer and O. Schenk, ILUPACK Volume 2.0—Preconditioning Software Package for Symmetrically Structured Problems, http://www.math.tu-berlin.de/ilupack/ (2005). [10] T. Brandes, B. Huckestein, and L. Schweitzer, Critical dynamics and multifractal exponents at the Anderson transition in 3d disordered systems, Ann. Phys. (Leipzig), 5 (1996), pp. 633–651. [11] J. R. Bunch, Partial pivoting strategies for symmetric matrices, SIAM J. Numer. Anal., 11 (1974), pp. 521–528. [12] J. R. Bunch and L. Kaufman, Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp., 31 (1977), pp. 163–179. [13] P. Cain, F. Milde, R. A. R¨omer, and M. Schreiber, Use of cluster computing for the Anderson model of localization, Comput. Phys. Comm., 147 (2002), pp. 246–250. [14] P. Cain, R. A. R¨omer, and M. Schreiber, Phase diagram of the three-dimensional Anderson model of localization with random hopping, Ann. Phys. (Leipzig), 8 (1999), pp. SI33–SI38. [15] A. K. Cline, C. B. Moler, G. W. Stewart, and J. H. Wilkinson, An estimate for the condition number of a matrix, SIAM J. Numer. Anal., 16 (1979), pp. 368–375. [16] J. Cullum and R. A. Willoughby, Lanczos Algorithms for Large Symmetric Eigenvalue Computations, Volume 1: Theory, Birkh¨auser Boston, Boston, MA, 1985. [17] J. Cullum and R. A. Willoughby, Lanczos Algorithms for Large Symmetric Eigenvalue Computations, Volume 2: Programs, Birkh¨auser Boston, Boston, MA, 1985. Available online at http://www.netlib.org/lanczos/. [18] P. Dayal, M. Troyer, and R. Villiger, The Iterative Eigensolver Template Library, ETH Z¨urich, Z¨urich, Switzerland, 2004. Available online at http://www.comp-phys.org:16080/ software/ietl/. [19] J. W. Demmel, S. C. Eisenstat, J. R. Gilbert, X. S. Li, and J. W. H. Liu, A supernodal approach to sparse partial pivoting, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 720–755. [20] D. Dodson and J. G. Lewis, Issues relating to extension of the basic linear algebra subprograms, ACM SIGNUM Newslett., 20 (1985), pp. 19–22. [21] J. J. Dongarra, J. Du Croz, S. Hammarling, and R. J. Hanson, A proposal for an extended set of Fortran basic linear algebra subprograms, ACM SIGNUM Newslett., 20 (1985), pp. 2–18. [22] I. S. Duff and J. R. Gilbert, Symmetric weighted matching for indefinite systems, talk presented at the Householder Symposium XV, 2002. [23] I. S. Duff and J. Koster, The design and use of algorithms for permuting large entries to the diagonal of sparse matrices, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 889–901. [24] I. S. Duff and S. Pralet, Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite Problems, Technical Report TR/PA/04/59, CERFACS, Toulouse, France, 2004. [25] I. S. Duff and J. K. Reid, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software, 9 (1983), pp. 302–325. [26] A. Eilmes, R. A. R¨omer, and M. Schreiber, The two-dimensional Anderson model of localization with random hopping, Eur. Phys. J. B, 1 (1998), pp. 29–38. [27] U. Elsner, V. Mehrmann, F. Milde, R. A. R¨omer, and M. Schreiber, The Anderson model of localization: A challenge for modern eigenvalue methods, SIAM J. Sci. Comput., 20 (1999), pp. 2089–2102. 982 O. SCHENK, M. BOLLH¨OFER, AND R. A. R¨OMER [28] R. D. Fokkema, G. L. G. Sleijpen, and H. A. Van der Vorst, Jacobi–Davidson style QR and QZ algorithms for the reduction of matrix pencils, SIAM J. Sci. Comput., 20 (1998), pp. 94–125. [29] R. Freund and F. Jarre, A QMR-based interior-point algorithm for solving linear programs, Math. Programming Ser. B, 76 (1997), pp. 183–210. [30] R. Freund and N. Nachtigal, Software for simplified Lanczos and QMR algorithms, Appl. Numer. Math., 19 (1995), pp. 319–341. [31] A. George and E. Ng, An implementation of Gaussian elimination with partial pivoting for sparse systems, SIAM J. Sci. Statist. Comput., 6 (1985), pp. 390–409. [32] R. Geus, JDBSYM Version 0.14, http://www.inf.ethz.ch/personal/geus/software.html (2006). [33] R. Geus, The Jacobi–Davidson Algorithm for Solving Large Sparse Symmetric Eigenvalue Problems with Application to the Design of Accelerator Cavities, Ph.D. thesis, Computer Science Department, ETH Z¨urich, Z¨urich, Switzerland, 2002. Available online at http:// www.inf.ethz.ch/personal/geus/publications/diss-online.pdf. [34] J. R. Gilbert and E. Ng, Predicting structure in nonsymmetric sparse matrix factorizations, in Graph Theory and Sparse Matrix Computation, J. A. George, J. R. Gilbert, and J. W. H. Liu, eds., Springer, New York, 1993, pp. 107–139. [35] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996. [36] U. Grimm, R. A. R¨omer, and G. Schliecker, Electronic states in topologically disordered systems, Ann. Phys. (Leipzig), 7 (1998), pp. 389–393. [37] A. Gupta and L. Ying, A Fast Maximum-Weight-Bipartite-Matching Algorithm for Reducing Pivoting in Sparse Gaussian Elimination, Tech. Report RC 21576 (97320), IBM T. J. Watson Research Center, Yorktown Heights, NY, 1999. [38] M. Hagemann and O. Schenk, Weighted matchings for preconditioning symmetric indefinite linear systems, SIAM J. Sci. Comput., 28 (2006), pp. 403–420. [39] G. Karypis and V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., 20 (1998), pp. 359–392. [40] B. Kramer, A. Broderix, A. MacKinnon, and M. Schreiber, The Anderson transition: New numerical results for the critical exponents, Phys. A, 167 (1990), pp. 163–174. [41] B. Kramer and A. MacKinnon, Localization: Theory and experiment, Rep. Progr. Phys., 56 (1993), pp. 1469–1564. [42] R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK Users’ Guide: Solution of Large- Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, SIAM, Philadelphia, 1998. Available online at http://www.caam.rice.edu/software/ARPACK/. [43] N. Li, Y. Saad, and E. Chow, Crout versions of ILU for general sparse matrices, SIAM J. Sci. Comput., 25 (2003), pp. 716–728. [44] Q. Li, S. Katsoprinakis, E. N. Economou, and C. M. Soukoulis, Scaling properties in highly anisotropic systems, Phys. Rev. B, 56 (1997), pp. R4297–R4300, [45] X. S. Li and J. W. Demmel, SuperLU DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Trans. Math. Software, 29 (2003), pp. 110– 140. [46] F. Milde, R. A. R¨omer, and M. Schreiber, Multifractal analysis of the metal-insulator transition in anisotropic systems, Phys. Rev. B, 55 (1997), pp. 9463–9469. [47] F. Milde, R. A. R¨omer, and M. Schreiber, Energy-level statistics at the metal-insulator transition in anisotropic systems, Phys. Rev. B, 61 (2000), pp. 6028–6035. [48] Y. Notay, Inner Iterations in Eigenvalue Solvers, Technical Report GANMN 05-01, Universit´e Libre de Bruxelles, Brussels, Belgium, 2005. [49] M. Olschowka and A. Neumaier, A new pivoting strategy for Gaussian elimination, Linear Algebra Appl., 240 (1996), pp. 131–151. [50] C. C. Paige and M. A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12 (1975), pp. 617–629. [51] B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, NJ, 1980. [52] I. Plyushchay, R. A. R¨omer, and M. Schreiber, Three-dimensional Anderson model of localization with binary random potential, Phys. Rev. B, 68 (2003), 064201. [53] D. Porath, G. Cuniberti, and R. Di Felice, Charge transport in DNA-based devices, in Long-Range Charge Transfer in DNA II, Topics in Current Chemistry 237, G. B. Schuster, ed., Springer, New York, 2004, p. 183. [54] R. A. R¨omer and M. Schreiber, Numerical investigations of scaling at the Anderson transition, in The Anderson Transition and Its Ramifications—Localisation, Quantum Interference, and Interactions, T. Brandes and S. Kettemann, eds., Springer, Berlin, 2003, pp. 3–19. LARGE-SCALE DIAGONALIZATION TECHNIQUES 983 [55] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003. [56] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856–869. [57] O. Schenk and K. G¨artner, On Fast Factorization Pivoting Methods for Symmetric Indefinite Systems, Technical report, Computer Science Department, University of Basel, Basel, Switzerland, 2004. Electron. Trans. Numer. Anal., submitted. [58] O. Schenk and K. G¨artner, Solving unsymmetric sparse systems of linear equations with PARDISO, J. Future Generation Computer Systems, 20 (2004), pp. 475–487. [59] O. Schenk, S. R¨ollin, and A. Gupta, The effects of unsymmetric matrix permutations and scalings in semiconductor device and circuit simulation, IEEE Trans. Computer-Aided Design Integrated Circuits Systems, 23 (2004), pp. 400–411. [60] M. Schreiber and M. Ottomeier, Localization of electronic states in 2D disordered systems, J. Phys.: Condens. Matter, 4 (1992), pp. 1959–1971. [61] G. L. G. Sleijpen and H. A. Van der Vorst, A Jacobi–Davidson iteration for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 401–425. [62] D. C. Sorensen, Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 357–385. [63] C. M. Soukoulis and E. N. Economou, Off-diagonal disorder in one-dimensional systems, Phys. Rev. B, 24 (1981), pp. 5698–5702. [64] C. M. Soukoulis and E. N. Economou, Fractal character of eigenstates in disordered systems, Phys. Rev. Lett., 52 (1984), pp. 565–568. [65] A. Stathopoulos, Nearly Optimal Preconditioned Methods for Hermitian Eigenproblems under Limited Memory. Part I: Seeking One Eigenvalue, Technical Report WM-CS-2005-03, College of William & Mary, Williamsburg, VA, 2005.
URI:	http://wrap.warwick.ac.uk/id/eprint/346