O(N) methods in electronic structure calculations

Abstract

Linear scaling methods, or O(N) methods, have computational and memory requirements which scale linearly with the number of atoms in the system, N, in contrast to standard approaches which scale with the cube of the number of atoms. These methods, which rely on the short-ranged nature of electronic structure, will allow accurate, ab initio simulations of systems of unprecedented size. The theory behind the locality of electronic structure is described and related to physical properties of systems to be modelled, along with a survey of recent developments in real-space methods which are important for efficient use of high performance computers. The linear scaling methods proposed to date can be divided into seven different areas, and the applicability, efficiency and advantages of the methods proposed in these areas is then discussed. The applications of linear scaling methods, as well as the implementations available as computer programs, are considered. Finally, the prospects for and the challenges facing linear scaling methods are discussed.

85 pages, 15 figures, 488 references. Resubmitted to Rep. Prog. Phys (small changes)

References in corpus (99)

• The SIESTA method for ab initio order-N materials simulation
• Efficient index handling of multidimensional periodic boundary conditions
• Maximally-localized generalized Wannier functions for composite energy bands
• A Higher-Accuracy van der Waals Density Functional
• Maximally-localized Wannier functions for entangled energy bands
• A real-space grid implementation of the Projector Augmented Wave method
• Efficient implementation of a van der Waals density functional: Application to double-wall carbon nanotubes
• Interatomic potentials from first-principles calculations: the force-matching method
• Numerical atomic orbitals for linear scaling
• Linear-scaling ab-initio calculations for large and complex systems
• Nearsightedness of Electronic Matter
• Electron Localization in the Insulating State
• Real-Space Mesh Techniques in Density Functional Theory
• Projection of plane-wave calculations into atomic orbitals
• Exponential localization of Wannier functions in insulators
• Daubechies wavelets as a basis set for density functional pseudopotential calculations
• Maximally-localized Wannier functions for disordered systems: application to amorphous silicon
• Polarization and localization in insulators: generating function approach
• Systematic generation of finite-range atomic basis sets for linear-scaling calculations
• Total energy global optimizations using non orthogonal localized orbitals
• Multiresolution analysis of electronic structure: semicardinal and wavelet bases
• A Self-Consistent First-Principles Technique Having Linear Scaling
• Generalization of the density-matrix method to a non-orthogonal basis
• Analysis of atomic-orbital basis sets from the projection of plane-wave results
• Order-N implementation of exact exchange in extended systems
• Recent progress with large-scale ab initio calculations: the CONQUEST code
• Electronic structure calculations and molecular dynamics simulations with linear system-size scaling
• Parallel Self-Consistent-Field Calculations via Chebyshev-Filtered Subspace Acceleration
• Exponential decay properties of Wannier functions and related quantities
• Network equilibration and first-principles liquid water
• Partition Density Functional Theory
• A novel multigrid method for electronic structure calculations
• The Decay Properties of the Finite Temperature Density Matrix in Metals
• Calculations on millions of atoms with DFT: Linear scaling shows its potential
• Expansion algorithm for the density matrix
• Towards a Linear-Scaling DFT Technique: The Density Matrix Approach
• Systematically improvable optimized atomic basis sets for {\it ab inito} calculations
• Efficient and accurate three dimensional Poisson solver for surface problems
• Real-space local polynomial basis for solid-state electronic-structure calculations: A finite-element approach
• Real-space approach to calculation of electric polarization and dielectric constants
• Basis Functions for Linear-Scaling First-Principles Calculations
• Three real-space discretization techniques in electronic structure calculations
• Linear scaling Krylov subspace method for large scale {\it ab initio} electronic structure calculations of metals
• Electrons in Dry DNA from Density Functional Calculations
• Accurate ionic forces and geometry optimisation in linear scaling density-functional theory with local orbitals
• Partly Occupied Wannier Functions
• Density Matrix Perturbation Theory
• Large scale quantum simulations: C_60 impacts on a semiconducting surface
• Calculating the linear response functions of non-interacting electrons by the time-dependent Schroedinger equation
• Linear Algebraic Calculation of Green's function for Large-Scale Electronic Structure Theory
• Kinetic Energy Density Study of Some Representative Semilocal Kinetic Energy Functionals
• Orbital-Free Density Functional Theory: Kinetic Potentials and Ab-Initio Local Pseudopotentials
• Ab initio linear scaling response theory: Electric polarizability by perturbed projection
• Projector self-consistent DFT+U using non-orthogonal generalized Wannier functions
• Kinetic energy density functionals for non-periodic systems
• Using ONETEP for accurate and efficient O(N) density functional calculations
• Parallel Sparse Matrix Multiplication for Linear Scaling Electronic Structure Calculations
• An efficient and accurate decomposition of the Fermi operator
• Electronic structure via potential functional approximations
• Decay of Correlations in Fermi Systems at Non-zero Temperature
• Accurate kinetic energy evaluation in electronic structure calculations with localised functions on real space grids
• Krylov Subspace Method for Molecular Dynamics Simulation based on Large-Scale Electronic Structure Theory
• Linear scaling electronic structure calculations and accurate sampling with noisy forces
• Linear-scaling quantum Monte Carlo with non-orthogonal localized orbitals
• Implicit Purification for Temperature-Dependent Density Matrices
• Block bond-order potential as a convergent moments-based method
• Augmented orbital minimization method for linear scaling electronic structure calculations
• Nanoscale structures formed in silicon cleavage studied with large-scale electronic structure alculations; surface reconstruction, step and bending
• Stochastic linear scaling for metals and non metals
• Evaluation of Exchange-Correlation Energy, Potential, and Stress
• Ab initio study of transport properties in defected carbon nanotubes: an O(N) approach
• Locality properties and Wannier functions for interacting systems
• Efficient Recursion Method for Inverting Overlap Matrix
• Spatial decay of the single-particle density matrix in insulators: analytic results in two and three dimensions
• Spin unrestricted linear scaling electronic structure theory and its application to magnetic carbon doped BN nanotubes
• Parallel, linear-scaling building-block and embedding method based on localized orbitals and orbital-specific basis sets
• Comparison of variational real-space representations of the kinetic energy operator
• Dynamical brittle fractures of nanocrystalline silicon using large-scale electronic structure calculations
• Non-Orthogonal Density Matrix Perturbation Theory
• Spatial decay of the single-particle density matrix in tight-binding metals: +AFwAXA- analytic results in two dimensions
• Theory of composite-band Wannier states and order-N electronic-structure calculations
• Model Hessian for accelerating first-principles structure optimizations
• Linear scaling relaxation of the atomic positions in nano structures
• Linear scaling computation of the Fock matrix. IX. Parallel computation of the Coulomb matrix
• Order-N Density-Matrix Electronic-Structure Method for General Potentials
• Molecular-orbital-free algorithm for excited states in time-dependent perturbation theory
• Variational finite-difference representation of the kinetic energy operator
• Million-atom molecular dynamics simulation by order-N electronic structure theory and parallel computation
• Large-scale electronic structure theory for simulating nanostructure process
• Localization of Wannier functions for entangled energy bands
• Efficient and Accurate Linear Algebraic Methods for Large-scale Electronic Structure Calculations with Non-orthogonal Atomic Orbitals
• Linear scaling calculation of band edge states and doped semiconductors
• Linear scaling calculation of maximally-localized Wannier functions with atomic basis set
• Calculating response functions in time domain with non-orthonormal basis sets
• Exact results for spatial decay of the one-body density matrix in low-dimensional insulators
• Projection method for rapid ab initio calculations of metals
• Low complexity method for large-scale self-consistent ab initio electronic-structure calculations without localization
• Accuracy control in ultra-large-scale electronic structure calculation
• Exact results for spatial decay of correlations in low-dimensional insulators II

Cited by in corpus (156)

• Maximally localized Wannier functions: Theory and applications
• Resolution-of-identity approach to Hartree-Fock, hybrid density functionals, RPA, MP2, and \textit{GW} with numeric atom-centered orbital basis functions
• 86 PFLOPS Deep Potential Molecular Dynamics simulation of 100 million atoms with ab initio accuracy
• How large should the QM region be in QM/MM calculations? The case of catechol O-methyltransferase
• DFT-FE -- A massively parallel adaptive finite-element code for large-scale density functional theory calculations
• Adaptively Compressed Exchange Operator
• Atom-Density Representations for Machine Learning
• Daubechies Wavelets for Linear Scaling Density Functional Theory
• Charge Transfer as a Ubiquitous Mechanism in Determining the Negative Charge at Hydrophobic Interfaces
• SPARC: Accurate and efficient finite-difference formulation and parallel implementation of Density Functional Theory: Extended systems
• ELSI: A Unified Software Interface for Kohn-Sham Electronic Structure Solvers
• Systematic Quantum Mechanical Region Determination in QM/MM Simulation
• Exploiting locality in quantum computation for quantum chemistry
• Large scale and linear scaling DFT with the CONQUEST code
• A brief compendium of time-dependent density-functional theory
• SPARC: Accurate and efficient finite-difference formulation and parallel implementation of Density Functional Theory: Isolated clusters
• DGDFT: A Massively Parallel Method for Large Scale Density Functional Theory Calculations
• Accelerating Atomic Orbital-based Electronic Structure Calculation via Pole Expansion and Selected Inversion
• Electrostatic considerations affecting the calculated HOMO-LUMO gap in protein molecules
• Roadmap on Electronic Structure Codes in the Exascale Era
• DFT-FE 1.0: A massively parallel hybrid CPU-GPU density functional theory code using finite-element discretization
• Lattice Dynamics Calculations based on Density-functional Perturbation Theory in Real Space
• SQDFT: Spectral Quadrature method for large-scale parallel $\mathcal{O}(N)$ Kohn-Sham calculations at high temperature
• A many-body GW+BSE investigation of electronic and optical properties of C2N
• Linear-scaling time-dependent density-functional theory in the linear response formalism
• ATLAS: A Real-Space Finite-Difference Implementation of Orbital-Free Density Functional Theory
• Machine learning accelerated discovery of corrosion-resistant high-entropy alloys
• Coarse-graining Kohn-Sham Density Functional Theory
• Computing the Self-Consistent Field in Kohn-Sham Density Functional Theory
• ELSI -- An Open Infrastructure for Electronic Structure Solvers
• Origin of nonlocal resistance in multiterminal graphene on hexagonal-boron-nitride: Fermi surface edge currents rather than Fermi sea topological valley currents
• A first-principles approach to nonlinear lattice dynamics: Anomalous spectra in PbTe
• GPU-Acceleration of the ELPA2 Distributed Eigensolver for Dense Symmetric and Hermitian Eigenproblems
• On the Subsystem Formulation of Linear-Response Time-Dependent DFT
• Periodic Subsystem Density-Functional Theory
• Generalized Extended Lagrangian Born-Oppenheimer Molecular Dynamics
• Augmented Lagrangian formulation of Orbital-Free Density Functional Theory
• Multiple Chern bands in twisted MoTe${}_2$ and possible non-Abelian states
• A subquadratic-scaling subspace projection method for large-scale Kohn-Sham density functional theory calculations using spectral finite-element discretization
• GPGPU Acceleration of All-Electron Electronic Structure Theory Using Localized Numeric Atom-Centered Basis Functions
• The flexible nature of exchange, correlation and Hartree physics: resolving "delocalization" errors in a 'correlation free' density functional
• Symmetry-adapted real-space density functional theory for cylindrical geometries: application to large X (X=C, Si, Ge, Sn) nanotubes
• Equation of state of warm-dense boron nitride combining computation, modeling, and experiment
• Edge reconstruction in armchair phosphorene nanoribbons revealed by discontinuous Galerkin density functional theory
• Towards Linearly Scaling and Chemically Accurate Global Machine Learning Force Fields for Large Molecules
• Chebyshev polynomial filtered subspace iteration in the Discontinuous Galerkin method for large-scale electronic structure calculations
• Gradient-based stochastic estimation of the density matrix
• Optimal finite-range atomic basis sets for liquid water and ice
• Graph-based linear scaling electronic structure theory
• Stochastic density functional theory
• Efficient Computation of Sparse Matrix Functions for Large-Scale Electronic Structure Calculations: The CheSS Library
• Linear scaling DFT calculations for large Tungsten systems using an optimized local basis
• The CECAM Electronic Structure Library and the modular software development paradigm
• Next generation extended Lagrangian first principles molecular dynamics
• Fault-tolerant quantum simulation of materials using Bloch orbitals
• Self-consistent field theory based molecular dynamics with linear system-size scaling
• Quantum mechanics in an evolving Hilbert space
• SIESTA-PEXSI: Massively parallel method for efficient and accurate \textit{ab initio} materials simulation without matrix diagonalization
• Complexity Reduction in Density Functional Theory Calculations of Large Systems: System Partitioning and Fragment Embedding
• Fast method for quantum mechanical molecular dynamics
• Properties of carbon up to 10 million kelvin from Kohn-Sham density functional theory molecular dynamics
• Linear Scaling Density Matrix Real Time TDDFT: Propagator Unitarity \& Matrix Truncation
• The Cost of Improving the Precision of the Variational Quantum Eigensolver for Quantum Chemistry
• Highly accurate local basis sets for large-scale DFT calculations in CONQUEST
• On nearsightedness in metallic systems for $\mathcal{O}(N)$ Density Functional Theory calculations: A case study on Aluminum
• Generalized canonical purification for density matrix minimization
• eQE 2.0: Subsystem DFT Beyond GGA Functionals
• Interpolation across a muffin-tin interstitial using localized linear combinations of spherical waves
• A tight distance-dependent estimator for screening three-center Coulomb integrals over Gaussian basis functions
• Electronic structure study of screw dislocation core energetics in Aluminum and core energetics informed forces in a dislocation aggregate
• Calculating Hyperfine Couplings in Large Ionic Crystals Containing Hundreds of QM Atoms: Subsystem DFT is the Key
• An Efficient DFT Solver for Nanoscale Simulations and Beyond
• A slave mode expansion for obtaining ab-initio interatomic potentials
• Increasing the Efficiency of Sparse Matrix-Matrix Multiplication with a 2.5D Algorithm and One-Sided MPI
• Ultra-Fast Semi-Empirical Quantum Chemistry for High-Throughput Computational Campaigns with Sparrow
• Mixed Precision Fermi-Operator Expansion on Tensor Cores From a Machine Learning Perspective
• Canonical density matrix perturbation theory
• Locality-aware parallel block-sparse matrix-matrix multiplication using the Chunks and Tasks programming model
• Parameterless stopping criteria for recursive density matrix expansions
• Semi-empirical and Linear-Scaling DFT Methods to Characterize duplex DNA and G-quadruplexes in Presence of Interacting Small Molecules
• Chunks and Tasks: a programming model for parallelization of dynamic algorithms
• Real-space formulation of the stress tensor for $\mathcal{O}(N)$ density functional theory: application to high temperature calculations
• Robust All-Electron Optimization in Orbital-Free Density Functional Theory Using the Trust Region Image Method
• Performance analysis of electronic structure codes on HPC systems: A case study of SIESTA
• GPU acceleration of local and semilocal density functional calculations in the SPARC electronic structure code
• Efficient numerical method for evaluating normal and anomalous time-domain equilibrium Green's functions in inhomogeneous systems
• Benchmarking boron carbide equation of state using computation and experiment
• Strong localization in defective carbon nanotubes: a recursive Green's function study
• Coupled Maxwell and Time-Dependent Orbital Free Density Functional Calculations
• Canonical-ensemble extended Lagrangian Born-Oppenheimer molecular dynamics for the linear scaling density functional theory
• Deep Density: circumventing the Kohn-Sham equations via symmetry preserving neural networks
• Polar morphologies from first principles: PbTiO${}_3$ films on SrTiO${}_3$ substrates and the $p(2\times \Lambda )$ surface reconstruction
• Unsupervised learning-based structural analysis: Search for a characteristic low-dimensional space by local structures in atomistic simulations
• Spectrum-splitting approach for Fermi-operator expansion in all-electron Kohn-Sham DFT calculations
• Solution of the $k$-th eigenvalue problem in large-scale electronic structure calculations
• Simulating nuclear and electronic quantum effects in enzymes
• Large-scale DFT methods for calculations of materials with complex structures
• First-principles quantum corrections for carrier correlations in double-layer two-dimensional heterostructures
• Low-cost orbital-based linear-scaling \emph{ab initio} molecular dynamics for weakly-interacting systems
• First principles soft mode lattice dynamics of PbZr${}_{0.5}$Ti${}_{0.5}$O${}_3$ and shortcomings of the virtual crystal approximation
• High-accuracy large-scale DFT calculations using localized orbitals in complex electronic systems: The case of graphene-metal interfaces
• Localized density matrix minimization and linear scaling algorithms
• Structural properties of Silicon-Germanium and Germanium-Silicon Core-Shell Nanowires
• Graph-based Quantum Response Theory and Shadow Born-Oppenheimer Molecular Dynamics
• Accelerating self-consistent field iterations in Kohn-Sham density functional theory using a low rank approximation of the dielectric matrix
• Decay properties for functions of matrices over $C^{\ast }$-algebras
• Locality of Interatomic Forces in Tight Binding Models for Insulators
• Efficient Parallel Linear Scaling Method to get the Response Density Matrix in All-Electron Real-Space Density-Functional Perturbation Theory
• Element orbitals for Kohn-Sham density functional theory
• Superconductivity, generalized random phase approximation and linear scaling methods
• Pseudo-Fragment Approach for Extended Systems Derived from Linear-Scaling DFT
• Efficient O($N$) divide-conquer method with localized natural orbitals
• DFT study of undoped and As-doped Si nanowires approaching the bulk limit
• Approximating spectral densities of large matrices
• Task-based Parallel Computation of the Density Matrix in Quantum-based Molecular Dynamics using Graph Partitioning
• Unfolding optical transition weights of impurity materials for first-principles LCAO electronic structure calculations
• Real-space density kernel method for Kohn-Sham density functional theory calculations at high temperature
• Machine learning interatomic potential for predicting the thermal properties of uranium nitride
• Decay bounds for functions of matrices with banded or Kronecker structure
• Robust Determination of the Chemical Potential in the Pole Expansion and Selected Inversion Method for Solving Kohn-Sham density functional theory
• SPARC: Simulation Package for Ab-initio Real-space Calculations
• A General Algorithm to Calculate the Inverse Principal $p$-th Root of Symmetric Positive Definite Matrices
• On-the-fly computation of frontal orbitals in density matrix expansions
• The pseudoatomic orbital basis: electronic accuracy and soft-mode distortions in ABO${}_3$ perovskites
• Complexity Reduction in Density Functional Theory: Locality in Space and Energy
• Compact Gaussian basis sets for stochastic DFT calculations
• Modular implementation of the linear and cubic-scaling orbital minimization methods in electronic structure codes using atomic orbitals
• An efficient time-stepping scheme for ab initio molecular dynamics simulations
• On the condition number and perturbation of matrix functions for Hermitian matrices
• Accelerating Sparse Approximate Matrix Multiplication on GPUs
• Decay estimates of discretized Green's functions for Schrödinger type operators
• QM/MM methods for crystalline defects. Part 1: Locality of the tight binding model
• Localized spectrum slicing
• M-SPARC: MATLAB-Simulation Package for Ab-initio Real-space Calculations
• Parallelization and scalability analysis of inverse factorization using the Chunks and Tasks programming model
• An efficient method for calculating spatially extended electronic states of large systems with a divide-and-conquer approach
• Adaptive local basis set for Kohn-Sham density functional theory in a discontinuous Galerkin framework II: Force, vibration, and molecular dynamics calculations
• Variational formulation for Wannier functions with entangled band structure
• Building bridges: matching density functional theory with experiment
• Sparse approximate matrix-matrix multiplication for density matrix purification with error control
• Interpolative Separable Density Fitting through Centroidal Voronoi Tessellation With Applications to Hybrid Functional Electronic Structure Calculations
• Stabilization of Ab Initio Molecular Dynamics Simulations at Large Time Steps
• A generalized and adaptable tensor-contraction-based cluster expansion formalism for multicomponent solids
• Positivity Preserving Density Matrix Minimization at Finite Temperatures via Square Root
• Disentanglement via entanglement: A unified method for Wannier localization
• Solvers for $\mathcal{O}(N)$ Electronic Structure in the Strong Scaling Limit
• iOI: an Iterative Orbital Interaction Approach for Solving the Self-Consistent Field Problem
• Direct unconstrained variable-metric localization of one-electron orbitals
• Quantitative Molecular Simulations
• Tensor-structured algorithm for reduced-order scaling large-scale Kohn-Sham density functional theory calculations
• An Adaptive Multiscale Approach for Electronic Structure Methods
• Accelerated density matrix expansions for Born-Oppenheimer molecular dynamics
• Incomplete selected inversion for linear-scaling electronic structure calculations
• Split representation of adaptively compressed polarizability operator
• Two-level Chebyshev filter based complementary subspace method: pushing the envelope of large-scale electronic structure calculations
• Origin of ferroelectric domain wall alignment with surface trenches in ultrathin films