PaperlayerView exact revision on arXiv

Source-linked AI summary

Modern Approaches to Exact Diagonalization and Selected Configuration Interaction with the Adaptive Sampling CI Method

Norm M. Tubman, C. Daniel Freeman, Daniel S. Levine, Diptarka Hait, Martin Head-Gordon, K. Birgitta Whaley

arXiv:1807.00821v2physics.comp-phcond-mat.mtrl-sciphysics.chem-phquant-ph

TL;DR

Selected CI needs efficient ways to process large determinant data while retaining accuracy and scalability. This work redesigns ASCI around sorting- and hashing-based algorithms, then benchmarks the resulting methods across molecular systems and basis sets. The updated approach is reported to outperform other selected-CI methods, including HBCI by about an order of magnitude at 0.1 mHa and by more than two orders of magnitude at 0.01 mHa.

  • Problem

    Selected CI requires efficient processing of large data volumes, and existing ASCI implementations needed advances to support simulations with hundreds of orbitals on single workstations.

  • Method

    The paper integrates sorting- and hashing-driven ASCI algorithms for search, Hamiltonian construction, orbital rotations, diagonal matrix elements, residue arrays, and deterministic perturbation theory.

  • Results

    The resulting algorithms are reported to be faster than previously published selected-CI approaches, about an order of magnitude faster than HBCI at 0.1 mHa and more than two orders faster at 0.01 mHa.

  • Takeaways & Limitations

    The benchmarks demonstrate that modern sorting techniques can support efficient, accurate ASCI simulations across a wide range of systems and basis sets.

Abstract

from arXiv · show

Recent advances in selected CI, including the adaptive sampling configuration interaction (ASCI) algorithm and its heat bath extension, have made the ASCI approach competitive with the most accurate techniques available, and hence an increasingly powerful tool in solving quantum Hamiltonians. In this work, we show that a useful paradigm for generating efficient selected CI/exact diagonalization algorithms is driven by fast sorting algorithms, much in the same way iterative diagonalization is based on the paradigm of matrix vector multiplication. We present several new algorithms for all parts of performing a selected CI, which includes new ASCI search, dynamic bit masking, fast orbital rotations, fast diagonal matrix elements, and residue arrays. The algorithms presented here are fast and scalable, and we find that because they are built on fast sorting algorithms they are more efficient than all other approaches we considered. After introducing these techniques we present ASCI results applied to a large range of systems and basis sets in order to demonstrate the types of simulations that can be practically treated at the full-CI level with modern methods and hardware, presenting double- and triple-zeta benchmark data for the G1 dataset. The largest of these calculations is Si$_{2}$H$_{6}$ which is a simulation of 34 electrons in 152 orbitals. We also present some preliminary results for fast deterministic perturbation theory simulations that use hash functions to maintain high efficiency for treating large basis sets.

I. INTRODUCTION

The paper develops sorting-driven algorithms that make ASCI faster and scalable, then benchmarks them across selected-CI calculations. The resulting workflow improves search and Hamiltonian construction while enabling deterministic, accurate simulations and comparisons with stochastic approaches.

  • Motivation: Selected CI methods are attractive for strongly correlated quantum chemistry, while ASCI offers deterministic Hilbert-space search at reduced computational cost.ASCI has been applied to systems where DMRG is less suitable, including systems with large entanglement, two- and three-dimensional structures, large basis sets, and excited states.
  • Motivation: The work addresses selected-CI data-processing bottlenecks with sorting-based algorithms designed for modern CPUs, GPUs, and parallel architectures.The authors identify cache inefficiency and movement of large data volumes to and from the CPU as central computational issues.
  • New algorithms: The updated ASCI workflow combines new search, dynamic bit masking, fast orbital rotations, fast diagonal matrix elements, residue arrays, and alternative bit-string representations.The recommended workflow includes new ASCI search, dynamic bit masking, fast orbital rotations, and deterministic PT2 based on sorting; residue arrays may be preferable for some Hamiltonians.
  • ASCI workflow: The algorithm separates wave-function growth from refinement: growth increases the determinant space and rotates orbitals, while refinement fixes its size and improves quality.This organization avoids diagonalizing a full-size but inaccurate wave function and supports high-accuracy refinement before PT2.
  • Benchmark results: Across benchmarks, accurate deterministic ASCI wave functions use fewer determinants than HBCI and avoid stochastic errors in perturbation theory.For comparable variational energies, C2 and F2 ASCI calculations use 42,000 and 95,000 fewer determinants than HBCI, respectively.
  • Benchmark results: For 0.1 mHa accuracy, ASCI PT2 is 6 times faster for C2 and 11 times faster for F2 than HBCI at 68% likelihood, increasing to 48 and 88 times for energy differences at 95% likelihood.For 0.01 mHa accuracy, the reported ASCI timings are several hundred times faster than HBCI.

III. THEORETICAL BACKGROUND: SELECTED CI ALGORITHMS

Selected CI iteratively builds a compact determinant space by pruning and ranking candidate determinants, then improves the wave function through repeated updates and perturbative energy estimates.

  • Selected CI diagonalizes a determinant space designed to capture as many important degrees of freedom as possible.
  • Each iteration prunes the search space and ranks determinants to construct an improved wave function ψk+1.
  • The ranking estimate uses Hamiltonian couplings, current coefficients, and the eigenstate energy to predict important new determinants.
  • The selected coefficient estimates Ai define determinant ranks and are related to first-order perturbation estimates for CI coefficients.
  • The resulting iterative procedure targets dominant wave-function contributions, while Epstein-Nesbet PT2 supplies a perturbative energy correction.

1. Introduction to the Computational Challenge

Selected CI searches and Hamiltonian construction become difficult because determinant connections grow rapidly with wave-function size, making straightforward enumeration and lookup expensive.

  • Equations for determinant ranking and PT2 involve all singly and doubly connected determinants, whose number can become extremely large.
  • The straightforward search generates connected determinants and scans the wave function to find nonzero Hamiltonian couplings.
  • The straightforward approach scales as O((Ntdets ∗ Nocc ∗ Nvirt)^2), with Ntdets searches dominating fixed-orbital asymptotics.
  • Hamiltonian construction faces a similar connection-finding problem, motivating new algorithms for both search and matrix construction.

2. CIPSI

CIPSI searches by generating and ranking the full connected determinant space, whereas ASCI-style pruning reduces the search burden while preserving accuracy.

  • CIPSI generates all singly and doubly connected determinants, ranks them using Eq. 2, and retains the top Ntdets for the next wave function.
  • Generic selected-CI search stores determinant bit strings with ranking values before gathering the leading contributors for ψk+1.
  • Original ASCI search prunes connected determinants using coefficient information, while heat-bath search also uses Hamiltonian matrix elements.
  • Pruning is reported to improve computational efficiency without significant accuracy loss, while unpruned search is costly in CIPSI applications.

3. ASCI

ASCI improves selected-CI search by combining pruning and ranking through sorting, targeting the data-movement and cache-efficiency bottlenecks of modern hardware.

  • Search and pruning: ASCI prunes candidate connections using determinant coefficients, retaining only connections from the top Ncdets determinants for ranking.Each iteration uses core and target spaces of sizes Ncdets and Ntdets.
  • Search and pruning: The new search is sufficiently fast that ASCI does not require the less accurate HBCI ranking approximation.The new ASCI search retains accuracy close to the original ASCI search.
  • Sorting-based implementation: Sorting groups connected determinants so ranking expressions can be evaluated in a single pass over the sorted array.This approach can also process partial arrays when memory is limited.
  • Sorting-based implementation: Selected-CI cache inefficiency motivates sorting because practical sorting algorithms are designed for cache-efficient data access.The authors identify moving necessary data to the CPU as a dominant bottleneck.
  • Sorting-based implementation: Sorting-based selected-CI algorithms support parallelization, including implementations using multiple CPU cores and GPUs.The reported tests include nearly linear scaling to 8 cores for IPS4O and GPU timings that include data transfers.

B. Hamiltonian construction

The paper develops sorting-based alternatives for constructing sparse selected-CI Hamiltonians, replacing inefficient large-scale searches with residue arrays and dynamic bit masking.

  • Motivation: Selected-CI Hamiltonian construction must identify non-zero matrix elements because the retained determinant set does not contain all active-space determinants.The resulting matrix elements must be ordered by row for sparse diagonalization.
  • Baseline methods: The double-loop and singles/doubles approaches become inefficient when the numbers of determinants, electrons, or orbitals are large.The double-loop operation count scales as O(N_tdets^2).
  • Residue trees: Residue trees group determinants by residues formed by removing two electrons, allowing connected determinant pairs to be found through shared residue nodes.Each residue-tree node stores a residue and the determinants that generate it.
  • Residue trees: For Cr2 with 48 electrons and Ntdets=300,000, the residue count is on the order of 200 million.This scale motivated replacing residue trees with sorting-based residue arrays.
  • Residue arrays: Residue arrays store each residue and its generating determinant in an unsorted array, then sort by residue so equal residues become adjacent.The grouped array directly generates all non-zero Hamiltonian matrix elements.
  • Algorithm comparison: In the Cr2 ASCI test, residue arrays were second only to dynamic bit masking for finding non-zero Hamiltonian matrix elements.Both methods are sorting-based alternatives compared with double loops and residue trees.
  • Dynamic bit masking: Dynamic bit masking exploits the fact that determinants connected by at most double excitations differ in at most four orbitals.Reduced bit strings are created by masking or deleting selected orbitals, then used to identify candidate connections.
  • Algorithm comparison: Table VI compares double loop, residue tree, residue array, and dynamic bit masking timings for ASCI and denser singles-and-doubles determinant sets.The denser test is a worse-case scenario for dynamic bit masking because it benefits from Hamiltonian sparsity.

3. Hamiltonian Construction: Algorithm comparisons

Benchmarking on an all-electron Cr2 SVP simulation shows that the new sorting-based Hamiltonian-construction algorithms outperform the tested non-sorting alternatives.

  • Algorithm comparisons: In all-electron Cr2 SVP tests, residue arrays and dynamic bit masking were both sorting-based methods, while search trees and hash tables were generally not competitive.The authors note that newer hash-table advances still warrant further investigation.

4. Orbital rotations and calculating the 2RDM

The implementation accelerates orbital optimization and ASCI search while retaining the accuracy of the original search more closely than approximate HBCI ranking.

  • Orbital rotations: In SCI, single-particle orbitals can affect convergence with respect to Ntdets, motivating orbital optimization with the one-particle density matrix.The initial implementation rotated orbitals after complete ASCI runs.
  • Orbital rotations: The current implementation rotates to natural orbitals after each growth-phase iteration and immediately rediagonalizes the Hamiltonian.Rediagonalization accounts for changes in wave-function expansion coefficients caused by orbital rotation.
  • New ASCI search: The new ASCI search generates and sorts candidate contributions, then uses the sorted data to approximate the ranking expression.Pruning can be performed before sorting, including integral-driven and coefficient-driven variants.
  • New ASCI search: Partial sorting and accumulation allow the search to operate under memory limits by combining identical determinants and retaining large terms incrementally.This procedure applies a restricted sum containing only connections that satisfy the pruning criteria.
  • Search accuracy: The new ASCI search is close in accuracy to the original search and removes the need for the HBCI ranking approximation.The approximation is described as less accurate because it ignores denominator and phase information.
  • Search efficiency: The implementation accelerates diagonal matrix-element calculations, which are required in the denominator of the ASCI ranking expression and can significantly slow the algorithm.Table VII reports timings for Hamiltonian build, diagonalization, and search across molecules.

D. Other algorithmic improvements

The method accelerates selected-CI search and Hamiltonian construction with sorting-based data handling and fast diagonal-element evaluation. These changes reduce memory pressure and reuse reference-determinant information across many connections.

  • Other algorithmic improvements: The resulting sorting and cache-efficient techniques improve selected-CI data movement and manipulation as determinant data structures grow.The approach targets bit strings whose size increases with the number of orbitals.
  • Search and pruning based on fast sorting algorithms: The search generates single and double excitations, assigns each connected determinant a ranking value, and gathers top contributors for the next iteration.The procedure supports determinant-driven or coefficient-driven generation of double connections.
  • Search and pruning based on fast sorting algorithms: Sorting determinants by bit string groups repeated connections so their contributions can be summed efficiently.When memory is limited, partial sorting by ranking value retains only top elements before continuing the search.
  • Fast diagonal matrix elements: Fast diagonal elements compute Hii from a known reference element Href by evaluating only the changed terms.Precomputed partial contributions are reused for many connections from each reference determinant, making the initial overhead negligible.

2. Bit string representation

The paper evaluates compact determinant representations and hashing to reduce the cost of manipulating large bit strings. These alternatives trade representation length and sorting efficiency against possible collisions or limited applicability.

  • Motivation: Large bit strings slow comparisons, copying, communication, and cache use because they require more memory and exceed native 64-bit operations.These costs become important for large basis-set calculations.
  • Alternative representations: Standard representations use 2N_orbs bits, whereas electron representations require approximately N_elec log N_orb bits.The electron representation stores occupied orbital indices instead of occupancy for every orbital.
  • Alternative representations: Difference representations encode orbitals excited from Hartree–Fock, orbitals excited into, and the excitation count.This can be compact when determinants differ from the Hartree–Fock reference by few excitations.
  • Hash representations: Hash functions compress large determinant bit strings into fixed-length integers to accelerate sorting in sparse determinant spaces.The authors propose assessing whether 128-bit or larger strings can be reduced to 64 bits without excessive collisions.
  • Perturbation theory: Perturbation theory is presented as a post-processing step that improves the ASCI energy after important determinants have been selected.The paper notes that deterministic perturbation theory can in many cases be faster than stochastic approaches for chemical accuracy.

V. RESULTS

The benchmarks apply ASCI to 55 G1 molecules in cc-pVDZ and cc-pVTZ bases, comparing variational and perturbative energies with coupled-cluster references. Most systems reach chemical accuracy, while convergence and comparison quality vary across molecules and basis sets.

  • G1 benchmark setup: 55 G1 molecules were benchmarked with ASCI in both cc-pVDZ and cc-pVTZ basis sets.The calculations report variational and perturbative energies and compare the best perturbative results with CCSD(T).
  • G1 benchmark results: Nearly all cc-pVDZ molecules converge within chemical accuracy, and many cc-pVTZ molecules are also converged.The authors suggest cc-pVQZ convergence for all G1 molecules using modest computational resources.
  • Comparison with coupled cluster: ASCI+PT2 energies outperform comparable CCSD(T) results for CN even with only 10^3 variational determinants.The PT2 contribution is identified as essential for this enhanced accuracy.
  • Comparison with coupled cluster: The largest difference between ASCI and CCSD(T) energies in the reported comparisons is 4.2 mHa for the CN radical.For many molecules, the difference is less than 1 mHa.
  • Computational scope: The largest cc-pVTZ calculation was Si2H6 with 300,000 determinants, requiring additional computational time for convergence.For most other systems, PT2 corrections were obtained with at least 3*10^5 determinants within the resource limit.
  • Benchmark limitations: CCSD(T) energies sometimes lie below ASCI results in the cc-pVDZ comparison, so larger determinant calculations are needed to assess the significance.This qualification is stated as an issue for further investigation.

VI. CONCLUSIONS

The paper integrates sorting-driven algorithms and related representations into an updated ASCI method, then demonstrates speed and accuracy across benchmark systems. The results support broader selected-CI simulations, including large and previously difficult applications.

  • Algorithmic contributions: The updated ASCI algorithm combines new search, dynamic bit masking, orbital rotation, diagonal-element, residue-array, and bit-string techniques.Alternative representations are intended for particular Hamiltonian types.
  • Algorithmic contributions: Modern sorting enables efficient CPU and GPU implementations and can be combined with hashing for very large basis sets.The paper presents sorting as a central design principle for current computing architectures.
  • Performance results: ASCI is about an order of magnitude faster than HBCI at 0.1 mHa accuracy and more than two orders faster at 0.01 mHa.These comparisons use initial C2 and F2 benchmarks.
  • Scope and implications: The G1 ground-state calculations demonstrate convergence behavior and accuracy across a wide range of systems.The authors state that many previously intractable applications are within reach.
  • Accuracy results: ASCI and DMRG show excellent agreement for extrapolated Cr2 SVP ground-state energies.The comparison uses highly converged ASCI wave functions and extrapolations.

Appendix A: Hartree-Fock energies for G1 set molecules

This appendix reports the restricted Hartree–Fock determinant energies used to initialize the ASCI calculations and notes stability checks of the SCF solutions.

  • Restricted Hartree–Fock determinant energies used to initialize the ASCI calculations are reported in Tables XIV and XV.
  • The reported Hartree–Fock determinants provide the starting states for the ASCI calculations.
  • Stability analysis checked that all SCF solutions were local minima.
Loading 1807.00821v2…