research-article

Distributed-memory DMRG via sparse and dense parallel tensor contractions

Authors:

Edgar Solomonik,

Bryan K. ClarkAuthors Info & Claims

SC '20: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

Article No.: 24, Pages 1 - 14

Published: 09 November 2020 Publication History

Abstract

The density matrix renormalization group (DMRG) algorithm is a powerful tool for solving eigenvalue problems to model quantum systems. DMRG relies on tensor contractions and dense linear algebra to compute properties of condensed matter physics systems. However, its efficient parallel implementation is challenging due to limited concurrency, large memory footprint, and tensor sparsity. We mitigate these problems by implementing two new parallel approaches that handle block sparsity arising in DMRG, via Cyclops, a distributed memory tensor contraction library. We benchmark their performance on two physical systems using the Blue Waters and Stampede2 supercomputers. Our DMRG performance is improved by up to 5.9X in runtime and 99X in processing rate over ITensor, at roughly comparable computational resource use. This enables higher accuracy calculations via larger tensors for quantum state approximation. We demonstrate that despite having limited concurrency, DMRG is weakly scalable with the use of efficient parallel tensor contraction mechanisms.

References

[1]

S. R. White, "Density matrix formulation for quantum renormalization groups," Phys. Rev. Lett., vol. 69, no. 19, pp. 2863--2866, 1992.

[2]

S. R. White, "Density-matrix algorithms for quantum renormalization groups," Phys. Rev. B, vol. 48, no. 14, pp. 10 345--10356, 1993.

[3]

U. Schollwöck, "The density-matrix renormalization group in the age of matrix product states," Ann. Phys. (N. Y)., vol. 326, no. 1, pp. 96--192, 2011.

[4]

E. Stoudenmire and S. R. White, "Real-space parallel density matrix renormalization group," Physical Review B, vol. 87, no. 15, p. 155137, 2013.

[5]

H. Ueda, "Infinite-size density matrix renormalization group with parallel Hida's algorithm," Journal of the Physical Society of Japan, vol. 87, no. 7, p. 074005, 2018.

[6]

M. Dolfi, B. Bauer, S. Keller, A. Kosenkov, T. Ewart, A. Kantian, T. Giamarchi, and M. Troyer, "Matrix product state applications for the alps project," Computer Physics Communications, vol. 185, no. 12, pp. 3430--3440, 2014.

[7]

G. Hager, E. Jeckelmann, H. Fehske, and G. Wellein, "Parallelization strategies for density matrix renormalization group algorithms on shared-memory systems," Journal of Computational Physics, vol. 194, no. 2, pp. 795--808, 2004.

Digital Library

[8]

G. K.-L. Chan, "An algorithm for large scale density matrix renormalization group calculations," The Journal of chemical physics, vol. 120, no. 7, pp. 3172--3178, 2004.

[9]

S. Yamada, M. Okumura, and M. Machida, "Direct extension of density-matrix renormalization group to two-dimensional quantum lattice systems: Studies of parallel algorithm, accuracy, and performance," J. Phys. Soc. Japan, vol. 78, no. 9, pp. 1--5, 2009.

[10]

J. Vance, "Large-Scale Implementation of the Density Matrix Renormalization Group Algorithm," Ph.D. dissertation, SISSA, 2017. [Online]. Available: https://iris.sissa.it/handle/20.500.11767/68070

[11]

M. F. Dolfi, "Dilute systems with the density matrix renormalization group: from continuum to lattice models," Ph.D. dissertation, ETH Zürich, 2019.

[12]

A. Kantian, M. Dolfi, M. Troyer, and T. Giamarchi, "Understanding repulsively mediated superconductivity of correlated electrons via massively parallel density matrix renormalization group," Physical Review B, vol. 100, no. 7, Aug 2019. [Online]. Available

[13]

J. Brabec, J. Brandejs, K. Kowalski, S. Xantheas, Ö. Legeza, and L. Veis, "Massively parallel quantum chemical density matrix renormalization group method," 2020. [Online]. Available: http://arxiv.org/abs/2001.04890

[14]

E. Solomonik, D. Matthews, J. R. Hammond, J. F. Stanton, and J. Demmel, "A massively parallel tensor contraction framework for coupled-cluster computations," Journal of Parallel and Distributed Computing, vol. 74, no. 12, pp. 3176--3190, 2014.

Digital Library

[15]

R. Orús, "A practical introduction to tensor networks: Matrix product states and projected entangled pair states," Ann. Phys. (N. Y)., vol. 349, pp. 117--158, 2014. [Online]. Available

[16]

R. Orús, "Advances on tensor network theory: symmetries, fermions, entanglement, and holography," Eur. Phys. J. B, vol. 87, no. 11, 2014.

[17]

I. V. Oseledets, "Tensor-train decomposition," SIAM Journal on Scientific Computing, vol. 33, no. 5, pp. 2295--2317, 2011.

Digital Library

[18]

Y. Zhang and E. Solomonik, "On stability of tensor networks and canonical forms," 2020.

[19]

H. C. Jiang, H. Yao, and L. Balents, "Spin liquid ground state of the spin-1/2 square J₁-J₂ Heisenberg model," Phys. Rev. B, vol. 86, no. 2, pp. 1--14, 2012.

[20]

L. Wang and A. W. Sandvik, "Critical level crossings and gapless spin liquid in the square-lattice spin-1/2 J₁ - J₂ Heisenberg antiferromagnet," Phys. Rev. Lett., vol. 121, p. 107202, Sep 2018. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.121.107202

[21]

T. Shirakawa, T. Tohyama, J. Kokalj, S. Sota, and S. Yunoki, "Ground-state phase diagram of the triangular lattice Hubbard model by the density-matrix renormalization group method," Phys. Rev. B, vol. 96, no. 20, p. 205130, nov 2017. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevB.96.205130

[22]

A. Szasz, J. Motruk, M. P. Zaletel, and J. E. Moore, "Chiral spin liquid phase of the triangular lattice hubbard model: A density matrix renormalization group study," Phys. Rev. X, vol. 10, p. 021042, May 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevX.10.021042

[23]

J. Rincón, D. J. García, and K. Hallberg, "Improved parallelization techniques for the density matrix renormalization group," Comput. Phys. Commun., vol. 181, no. 8, pp. 1346--1351, 2010. [Online]. Available

[24]

S. Yamada, M. Okumura, T. Imamura, and M. Machida, "Direct extension of the density-matrix renormalization group method toward two-dimensional large quantum lattices and related high-performance computing," Jpn. J. Ind. Appl. Math., vol. 28, no. 1, pp. 141--151, 2011.

[25]

S. Östlund and S. Rommer, "Thermodynamic Limit of Density Matrix Renormalization," Phys. Rev. Lett., vol. 75, no. 19, pp. 3537--3540, nov 1995. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.75.3537

[26]

E. R. Davidson, "The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices," J. Comput. Phys., vol. 17, no. 1, pp. 87--94, jan 1975. [Online]. Available: https://linkinghub.elsevier.com/retrieve/pii/0021999175900650

[27]

http://itensor.org/.

[28]

P. Springer, T. Su, and P. Bientinesi, "HPTT: A High-Performance Tensor Transposition C++ Library," in Proceedings of the 4th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming, ser. ARRAY 2017. New York, NY, USA: ACM, 2017, pp. 56--62. [Online]. Available

Digital Library

[29]

D. Kats and F. R. Manby, "Sparse tensor framework for implementation of general local correlation methods," The Journal of Chemical Physics, vol. 138, no. 14, pp. -, 2013.

[30]

S. Chou, F. Kjolstad, and S. Amarasinghe, "Format abstraction for sparse tensor algebra compilers," Proceedings of the ACM on Programming Languages, vol. 2, October 2018.

[31]

F. Kjolstad, P. Ahrens, S. Kamil, and S. Amarasinghe, "Tensor algebra compilation with workspaces," International Symposium on Code Generation and Optimization, February 2019.

[32]

E. Epifanovsky, M. Wormit, T. Kuś, A. Landau, D. Zuev, K. Khistyaev, P. Manohar, I. Kaliman, A. Dreuw, and A. I. Krylov, "New implementation of high-level correlated methods using a general block-tensor library for high-performance electronic structure calculations," Journal of Computational Chemistry, 2013.

[33]

S. Hirata, "Tensor Contraction Engine: Abstraction and automated parallel implementation of configuration-interaction, coupled-cluster, and many-body perturbation theories," The Journal of Physical Chemistry A, vol. 107, no. 46, pp. 9887--9897, 2003.

[34]

P.-W. Lai, K. Stock, S. Rajbhandari, S. Krishnamoorthy, and P. Sadayappan, "A framework for load balancing of tensor contraction expressions via dynamic task partitioning," in Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, 2013, pp. 1--10.

[35]

J. Nieplocha, R. J. Harrison, and R. J. Littlefield, "Global Arrays: A nonuniform memory access programming model for high-performance computers," The Journal of Supercomputing, vol. 10, pp. 169--189, 1996.

[36]

E. Mutlu, K. Kowalski, and S. Krishnamoorthy, "Toward generalized tensor algebra for ab initio quantum chemistry methods," in Proceedings of the 6th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming. ACM, 2019, pp. 46--56.

[37]

J. A. Calvin, C. A. Lewis, and E. F. Valeev, "Scalable task-based algorithm for multiplication of block-rank-sparse matrices," in Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, 2015, pp. 1--8.

[38]

C. Peng, J. A. Calvin, F. Pavosevic, J. Zhang, and E. F. Valeev, "Massively parallel implementation of explicitly correlated coupled-cluster singles and doubles using Tiled Array framework," The Journal of Physical Chemistry A, vol. 120, no. 51, pp. 10231--10244, 2016.

[39]

I. Sivkov, P. Seewald, A. Lazzaro, and J. Hutter, "Dbcsr: A blocked sparse tensor algebra library," arXiv preprint arXiv:1910.13555, 2019.

[40]

L. S. Blackford, J. Choi, A. Cleary, E. D'Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet et al., ScaLAPACK users' guide. Siam, 1997, vol. 4.

[41]

L. G. Valiant, "A bridging model for parallel computation," Communications of the ACM, vol. 33, no. 8, pp. 103--111, 1990.

Digital Library

[42]

D. B. Skillicorn, J. Hill, and W. F. McColl, "Questions and answers about BSP," Scientific Programming, vol. 6, no. 3, pp. 249--274, 1997.

[43]

E. Solomonik, M. Besta, F. Vella, and T. Hoefler, "Scaling betweenness centrality using communication-efficient sparse matrix multiplication," in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, ser. SC '17. New York, NY, USA: ACM, 2017, pp. 47:1--47:14.

[44]

S. S. Gong, W. Zhu, D. N. Sheng, O. I. Motrunich, and M. P. Fisher, "Plaquette ordered phase and quantum phase diagram in the spin-1/2 square J₁-J₂ Heisenberg model," Phys. Rev. Lett., vol. 113, no. 2, pp. 1--5, 2014.

[45]

R. Haghshenas and D. N. Sheng, "U(1)-symmetric infinite projected entangled-pair states study of the spin-1/2 square J₁-J₂ Heisenberg model," Phys. Rev. B, vol. 97, no. 17, pp. 1--10, 2018.

[46]

W. Y. Liu, S. Dong, C. Wang, Y. Han, H. An, G. C. Guo, and L. He, "Gapless spin liquid ground state of the spin-1/2 J₁-J₂ Heisenberg model on square lattices," Phys. Rev. B, vol. 98, no. 24, pp. 1--5, 2018.

[47]

D. Poilblanc and M. Mambrini, "Quantum critical phase with infinite projected entangled paired states," Phys. Rev. B, vol. 96, p. 014414, Jul 2017. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevB.96.014414

Cited By

Xie ZLiu JLi JLi DDehnavi MKulkarni MKrishnamoorthy S(2023)MerchandiserProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577497(204-217)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577497
Liu JLi DGioiosa RLi JZhou HMoreira JMueller FEtsion Y(2021)AthenaProceedings of the ACM International Conference on Supercomputing10.1145/3447818.3460355(190-202)Online publication date: 3-Jun-2021
https://dl.acm.org/doi/10.1145/3447818.3460355

Recommendations

CoNST: Code Generator for Sparse Tensor Networks
Sparse tensor networks represent contractions over multiple sparse tensors. Tensor contractions are higher-order analogs of matrix multiplication. Tensor networks arise commonly in many domains of scientific computing and data science. Such networks are ...
Distributed-memory tensor completion for generalized loss functions in python using new sparse tensor kernels
Abstract
Tensor computations are increasingly prevalent numerical techniques in data science, but pose unique challenges for high-performance implementation. We provide novel algorithms and systems infrastructure which enable efficient parallel ...
Highlights
- Novel algorithms that use second information for generalized tensor completion.
Distributed-Memory Randomized Algorithms for Sparse Tensor CP Decomposition
SPAA '24: Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures

Candecomp / PARAFAC (CP) decomposition, a generalization of the matrix singular value decomposition to higher-dimensional tensors, is a popular tool for analyzing multidimensional sparse data. On tensors with billions of nonzero entries, computing a CP ...

Comments

Information & Contributors

Information

Published In

SC '20: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

November 2020

1454 pages

ISBN:9781728199986

General Chair:
Christine Cuicchi,
Program Chairs:
Irene Qualters,
William Kramer

Sponsors

SIGHPC: ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing

In-Cooperation

IEEE CS

Publisher

IEEE Press

Publication History

Published: 09 November 2020

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SC '20

Sponsor:

SIGHPC

SC '20: The International Conference for High Performance Computing, Networking, Storage and Analysis

November 9 - 19, 2020

Georgia, Atlanta

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
130
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)2

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xie ZLiu JLi JLi DDehnavi MKulkarni MKrishnamoorthy S(2023)MerchandiserProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577497(204-217)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577497
Liu JLi DGioiosa RLi JZhou HMoreira JMueller FEtsion Y(2021)AthenaProceedings of the ACM International Conference on Supercomputing10.1145/3447818.3460355(190-202)Online publication date: 3-Jun-2021
https://dl.acm.org/doi/10.1145/3447818.3460355

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents