Linear-scaling selected inversion based on hierarchical interpolative factorization for self Green's function for modified Poisson-Boltzmann equation in two dimensions

Yihui Tu, Qiyuan Pang, Haizhao Yang, Zhenli XuJournal of Computational Physics 2022 · DOI · OpenReview

Abstract

Calculating the self-energy of ions in biological and chemical systems requires solving the Modified Poisson-Boltzmann (MPB) equation, which involves computing the diagonal of the inverse of a large, sparse matrix—the self Green’s function. Traditional methods scale at $O(N^{1.5})$ in two dimensions, creating a significant computational barrier. We present SelInvHIF, an algorithm that combines Selected Inversion (SelInv) with Hierarchical Interpolative Factorization (HIF) to achieve true $O(N)$ linear scaling. By utilizing skeletonization to compress redundant degrees of freedom on hierarchical boundaries, SelInvHIF maintains constant-sized "fronts," enabling high-precision simulations of large-scale ionic systems.

Introduction

The Poisson-Boltzmann (PB) equation is a cornerstone of electrostatics in soft matter and biological physics. However, its mean-field nature neglects ion-ion correlations and self-energy effects, which are critical in high-valence or low-dielectric environments. The Modified Poisson-Boltzmann (MPB) equation addresses these shortcomings by incorporating a self-energy term, but this introduces a daunting numerical task: the evaluation of the self Green’s function.

Numerically, this translates to finding the diagonal entries of the inverse of the discrete Debye-Hückel operator. For a system with $N$ grid points, standard direct solvers or even specialized Selected Inversion (SelInv) techniques typically exhibit $O(N^{1.5})$ complexity in 2D. As researchers aim to model increasingly complex biological structures, this super-linear cost becomes a "wall" that prevents reaching the necessary scales.

Methods: Merging SelInv and HIF

SelInvHIF overcomes the $O(N^{1.5})$ bottleneck by integrating two powerful numerical concepts: Selected Inversion and Hierarchical Interpolative Factorization.

The Challenge of Growing Fronts

Standard solvers often use "Nested Dissection," which recursively splits the domain into blocks. However, the boundaries (or "fronts") between these blocks usually grow in size as the hierarchy ascends, leading to the $O(N^{1.5})$ complexity.

Skeletonization as the Solution

The core innovation of SelInvHIF is the use of skeletonization. This algebraic technique identifies and retains only the essential "skeleton" degrees of freedom on subdomain boundaries, pruning redundant information based on the low-rank properties of the off-diagonal blocks of the elliptic operator.

Figure 1: Hierarchical grid partitioning and skeletonization. The grey dots ($I$) represent interior points of subdomains, while the black dots ($J$) represent the skeleton points on the boundaries that are preserved during the hierarchical factorization.

As shown in Figure 1, the domain is partitioned into a hierarchy. By applying skeletonization at every level, SelInvHIF keeps the number of active degrees of freedom on the fronts small and constant-sized. The algorithm proceeds in two main phases:

  1. Factorization (Bottom-Up): A pass that constructs a hierarchy of Schur complements, applying skeletonization to maintain efficiency.
  2. Extraction (Top-Down): A pass that extracts the diagonal entries of the inverse using the hierarchical structure.

Both phases are optimized to maintain perfect $O(N)$ complexity in both time and memory.

Results and Performance

The efficacy of SelInvHIF was demonstrated across four 2D benchmarks designed to stress-test different physical scenarios, including systems with delta-function charge densities and dielectric discontinuities.

  • True Linear Scaling: Numerical results confirmed that both factorization and extraction times scale linearly with $N$. Quadrupling the grid size resulted in a roughly fourfold increase in computation time, rather than the eightfold increase expected from traditional methods.
  • High Precision: The algorithm achieved absolute errors in the range of $10^{-7}$ to $10^{-8}$ compared to exact reference methods, proving that the skeletonization-based compression does not sacrifice physical accuracy.
  • Robustness to Discontinuities: The solver successfully handled systems with dielectric discontinuities (where the dielectric constant $\epsilon$ jumps significantly), a common and difficult scenario in modeling proteins and membranes.
  • Memory Efficiency: Memory usage also followed a linear $O(N)$ trend, making large-scale simulations feasible on standard workstation hardware.

Conclusion and Future Work

SelInvHIF provides a robust, linear-scaling solution for computing the self Green's function in 2D ionic systems. By breaking the $O(N^{1.5})$ barrier, it opens the door to more detailed studies of ion correlations in biological and chemical contexts.

While this work focuses on 2D systems, the authors identify the extension to 3D as the primary goal for future research. Extending the skeletonization framework to 3D geometries will be essential for modeling realistic, three-dimensional biological structures. Additionally, further optimization of the constant prefactors could enhance the algorithm's practical performance for everyday simulation tasks.

Summary updated

Abstract

Highlights•Linear scaling selected inverse of elliptic operators.•Fast solver for modified Poisson-Boltzmann equation.•Hierarchical interpolative factorization.
BibTeX
@article{tu2022linear,
  author = {Yihui Tu and Qiyuan Pang and Haizhao Yang and Zhenli Xu},
  title = {{Linear-scaling selected inversion based on hierarchical interpolative factorization for self Green's function for modified Poisson-Boltzmann equation in two dimensions}},
  journal = {Journal of Computational Physics},
  year = {2022},
  doi = {10.1016/j.jcp.2021.110893},
}
Figure