桂林边界元
幻灯模式
阅读 1687
评论(0)
分享:
bzlu 2017-12-02 11:07:42
中国力学大会2017,MS079 边界元法与降维方法专题研讨会,北京2017.8.13-16 [](ICCM 2017, Guilin, China) [](边界元法与降维方法进展与应用研讨会,桂林2017) [](#AFMPB: An adaptive fast multipole Poisson–Boltzmann solver for calculating electrostatics in biomolecular systems) [](#Accelerating BEM in macromolecular electrostatics computing) #=!= 分子模拟中快速边界元计算静电方法进展 ##=!= 卢本卓 ###=!= 科学院计算数学与科学工程计算研究所 ###=!= 国家数学与交叉科学中心 ###=!= 北京,2017-8-15 [TOC] <page> ###Collaborators Jingfang Huang (黄京芳) (Univ. of North Carolina, US) Xiaolin Cheng (Oak Ridge National Lab, US) Bo Zhang (Indiana University, IN, USA) Nikos P. Pitsianis, and Xiaobai Sun (Duke University, US) J. Andrew McCammon (Uinv. Calfornia, San Diego) 陈旻昕 (苏州大学) 刘田田 (科学院计算数学所) 彭波 (科学院计算数学所) <page> #=!= Outline - **Introduction** - **Boundary integral equations for PB electrostatics** - **Molecular surface mesh generation (triangulation)** - **Fast algorithms** -- **Node-patch BEM** -- **FMM** - **AFMPB**: Adaptive fast multipole Poisson-Boltzmann solver - **Online computing and visualization** <page> # Explicit solvent molecular dynamics (MD) simulation **分子模拟是目前国际上最耗费超算机时的领域之一 !** ![](http://data.xyzgate.com/c387b5b9037f19b17dd769b384210dcf.png) A view of a channel protein molecule: <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=100% height=400px src="/scene?id= 59f83a764f022e388f25e817"></iframe> <page> =!= Electrostatic field of AChE ![](http://data.xyzgate.com/8e123a226a84433d31241e1db9ec8594.png) =!= Potential map of a drug-targeted protein ![](http://data.xyzgate.com/1193ce98688a0603c4ccdccd9cded64e.png) <br><br><br> ## Two main reasons for developing Poisson-Boltzmann electrostatics: - Electrostatics is a main interaction at atomic level: nonbond interactions: electrostatics and van der Waals - Explicit MD simulation $$\to$$ very expensive. $$\to$$ implicit/continuum solvent, PB is an established model <page> ##=!= Implicit solvent (continuum) model Poisson equation ```math -\nabla \cdot \varepsilon \nabla \phi -\lambda \rho^{ion} -\rho^f =0 ``` $$\rho^{ion} \to$$ Boltzmann distribution $$\to$$ **Poisson-Boltzmann equation** ```math -\nabla \cdot \varepsilon \nabla \phi -\lambda \displaystyle\sum_j c_j q_j e^{-\beta q_j \phi} - \rho^f=0 ``` **Linearized PBE** (for 1:1 electrolyte, piece-wise constant $$\epsilon$$) ```math -\nabla^2\phi +\lambda\kappa^2 \phi=\rho^f ``` Or ```math {\nabla}^2 \phi_p^{int}=-\frac{1}{D_{int}} \displaystyle\sum_k q_k \delta(r-r_k), ~ \text{inside molecule} ``` ```math {\nabla}^2 \phi^{ext}=\lambda^2 \phi ^{ext}(r), ~ \text{outside molecule} ``` Interface conditions: ```math \phi^{int}= \phi^{ext}, \epsilon_{int}\frac{\partial \phi^{int}}{\partial n}=\epsilon_{ext}\frac{\partial \phi^{ext}}{\partial n} ``` ![](http://data.xyzgate.com/0217d3ede086857fd539c9104c09a864.png) <br><br><br><br> ## Features - Singular charge distribution within the molecule - Discontinuous dielectric at the molecular surface - Different domains - Highly irregular molecular surface <page> #=!= Numerical methods BZ Lu, YC Zhou, Michael J. Holst, and JA McCammon. Recent progress in numerical methods for the Poisson-Boltzmann equation in biophysical applications. *Commun. in Comput. Phys.*, 3:973-1009, 2008 <br> - **Finite difference** : Delphi, APBS, UHBD, MEAD, PBEQ, MIBPB ... -- Grid ~ $$N^3$$ -- Operations ~ $$N^3$$ -- Less accurate ![](http://data.xyzgate.com/e48dba86d1b775460b713a480d1dc3e4.png) - **Finite element method** : mFES, APBS -- Grid ~ $$N^3$$ -- Operations ~ $$N^2$$ -- Not easy to setup ![](http://data.xyzgate.com/fbe1933ef8e161462860f06d591b88ec.png) - **Boundary element method (LPBE) ** : AFMPB -- Grid ~ $$N^2$$ -- Operations ~ $$N^2 \times N^2$$ $$\to$$ challenge! ![](http://data.xyzgate.com/e142f9003de678880f6c5b9ad973a68c.png) <page> #=!= Boundary integral equations for the PBE Using Green’s theorem to recast the PBE to an integral form: ```math \frac{1}{2} \phi_p^{int}=\oint_{\footnotesize S}^{\footnotesize {PV}} [G_{pt} \frac{\partial \phi_t^{int}}{\partial n} -\frac{\partial G_{pt}}{\partial n} \phi_t^{int}]dS_t + \frac{1}{D_{int}} \displaystyle\sum_k q_k G_{pk}, \ p\in S ``` ```math \frac{1}{2} \phi_p^{ext}=\oint_{\footnotesize S}^{\footnotesize {PV}} [-u_{pt} \frac{\partial \phi_t^{ext}}{\partial n}+\frac{\partial u_{pt}}{\partial n} \phi_t^{ext}]dS_t,\ p \in S ``` where ```math G_{pt}=\frac{1}{4\pi |r_t-r_p|}, ~ u_{pt}=\frac{exp(-\kappa |r_t-r_p|)}{4\pi |r_t-r_p|}. ``` Discretize: integral $$\to$$ summation ! **Discretize** $$\Longrightarrow Ax=b$$ ![](http://data.xyzgate.com/b45bf7832421c01ee8e8b16a25484dcb.png) ## Derivative BIEs (dBIE): Well conditioned Taking derivatives of above BIEs and make combinations, we get ```math (\frac{1}{2 \varepsilon}+\frac{1}{2}) f_p = \oint_ S^ {PV} [(G_{pt}-u_{pt})h_t - (\frac{1}{\varepsilon} \frac{\partial G_{pt}}{\partial n}-\frac{\partial u_{pt}}{\partial n})f_t]dS_t +\frac{1}{D_{ext}} \displaystyle\sum_k q_k G_{pk},\ p\in S ``` ```math (\frac{1}{2}+\frac{1}{2 \varepsilon}) h_p = \oint_ S^ {PV} [(\frac{\partial G_{pt}}{\partial n_0}-\frac{1}{\varepsilon} \frac{\partial u_{pt}}{\partial n_0})h_t- \frac{1}{\varepsilon}(\frac{{\partial}^2 G_{pt}}{\partial n_0 \partial n}-\frac{{\partial}^2 u_{pt}}{\partial n_0 \partial n})f_t]dS_t +\frac{1}{D_{ext}} \displaystyle\sum_k q_k \frac{\partial G_{pk}}{\partial n_0}, ``` Note $$f=\phi^{ext},\ h=\partial \phi^{ext}/{\partial n}$$ ==! *AH Juffer, HJC Berendsen, et al. J. Comput. Phys., 97(1991), 144.* ==! *J. Liang and S. Subramaniam. Biophys. J., 73 (1997), 1830.* <page> - **Main issue**: computationally cost - **Acceleration strategies:** -- Efficient molecular surface mesh generation -- “Node patch” BEM -- Fast multipole method and adaptive FMM: ~ O(N) complexity. <page> #=!= Molecular surface mesh generation (triangulation) ![](http://data.xyzgate.com/1a43bce46d141a1b69b519a69952931e.png) ![](http://data.xyzgate.com/999ef4e0e78705314baff19767dc0f8e.png) ## 分子表面三角化进展 - Software: MSMS,nanoshape, **TMSmesh** - Main development of **TMSmesh**: (1) surface trace; (2) triliear approximation ![](http://data.xyzgate.com/9189a8e0d43ba76fb3b8dc4febe4acd8.png) ![](http://data.xyzgate.com/bdb3fb7d186e11697bf8fcdfa6f1eb4c.png) Chen MX, Lu BZ, *J Chem Theory Comput*. 2011, 7, 203–212 <br><br><br><br> ## 关于 PB静电计算 误差的注释: - **物理模型, 平均场 ** - **分子表面 ** - 离散近似和数值误差 ## New method in our TMSmesh2 Gaussian surface: ```math \{ \vec x \in R^3,\phi \left(\vec x \right) = c \}, ``` ```math \phi \left(\vec x \right) = \sum _{i=1}^{N}e^{-d(\Vert \vec x - \vec x_i \Vert ^2 -r_i^2)}, ``` Duncan, B. S.; Olson, A. J. *Biopolymers* **1993**, 33, 231–238. Two steps in the algorithm: 1. n*th*-degree polynominal approximation of the Gaussian surface --> upper/lower bound estimation --> adaptively partition the space into cells -- and finally in each cell using trilinear polynomial approximation to the Gaussian surface. 2. Divide the triliear surface into single-valued pieces along each of *x, y, z* directions, then triangularize them. Tiantian Liu, Minxin Chen, Benzhuo Lu, https://arxiv.org/pdf/1611.03474.pdf (submitted to *SIAM J Sci. Computing*). ## n*th*-degree polynominal approxiamtion ```math \phi \left(\vec x \right) = \sum _{i=1}^{N}e^{-(\Vert \vec x - \vec x_i \Vert ^2 - r_i^2 )}=\sum _{i=1}^{N}e^{r_i^2}e^{-\left( x-x_i \right)^2}e^{-\left( y-y_i \right)^2}e^{-\left( z-z_i \right)^2}. ``` in the cubic cell $$[a,b]\times [c,d]\times [e,f]$$,above equation can be approximated as: ```math P(x,y,z) = \sum_{i=1}^{N}e^{r_i^2}P_n(x,x_i,a,b)Q_n(y,y_i,c,d)R_n(z,z_i,e,f), ``` ```math P_n(x,x_i,a,b) = \sum_{j=0}^n \alpha_j(x_i,a,b)L_j(\frac{2x-(a+b)}{b-a}), ``` ```math Q_n(y,y_i,c,d) = \sum_{j=0}^n \beta_j(y_i,c,d)L_j(\frac{2y-(c+d)}{d-c}), ``` ```math R_n(z,z_i,e,f) = \sum_{j=0}^n \gamma_j(z_i,e,f)L_j(\frac{2z-(e+f)}{f-e}), ``` ## Trilinear polynomial approximation to the polynomial surface P(x,y,z) = c in each final cube. ```math g(x,y,z) = a_0xyz+a_1xy+a_2xz+a_3yz+a_4x+a_5y+a_6z+a_7 = c. ``` ## Illustration of adaptive cell division Cubes in mesh generation of ADP molecule ![](http://data.xyzgate.com/00e2722de0c8d321191070bf32dc405d.png) ## Triangularization of trilinear surface ![](http://data.xyzgate.com/d0e970ce3d66ac66f4436e32fdde81f7.png) <page> ##Being able to treat arbitrarily large molecules =!= Dengue Virus surface triangular mesh: ~ $$10^6$$ atoms, and more than $$6\times 10^6$$ triangles in the figure ![](http://data.xyzgate.com/32752b672c50d640d1be6be23d2f25fc.png) =!= membrane-channel protein surface ![](http://data.xyzgate.com/562252ebdc0ef79d325b4099ea681eed.png) =!= Volume mesh (for finite element simulation) ![](http://data.xyzgate.com/6a5af8351ad734e438ebbcbfe7dad2a1.png) <page> #“Node patch” BEM -- efficient low order BEM! ![](http://data.xyzgate.com/786a0c69ffc48b7e543261bcc781353e.png) ==! *Lu, B. Z. and McCammon, J. A. . J. Chem. Theory. Comput. 3:1134, 2007* ####Advantages: - Reduce the linear system size by half without losing accuracy - Save time when storing the matrix coefficients - Source points = target points, nearly optimal in current AFMM calculations <page> #=!= Fast multipole method - ####Top 10 Algorithm of the 20th Century! ~O(N) algorithm ![](http://data.xyzgate.com/c4281d1a36d22ba9a782242e13f06529.png) =!= **Vladimir Rokhlin** ![](http://data.xyzgate.com/47a4cd23a645916d22fcbd2054d42590.png) =!= **Leslie Greengard** FMM: ![](http://data.xyzgate.com/30ae6df21b236c729e465df3e2b05b56.png) New version FMM, 1997: uses exponential expansions and the merge-and-shift technique. <page> ## Fast multipole method - Multipole expansion ![](http://data.xyzgate.com/945b1304c3d59bb94f07ccbb5365d509.png) ```math \displaystyle\sum_i \frac{1}{r(x_i,y)}=(\displaystyle\sum_i f(x_i)) \cdot f(y) ``` ```math \frac{1}{|y-x|}=\displaystyle\sum_{n=0}^{\infty} \displaystyle\sum_{m=-n}^{n} |x|^n Y_n^{-m}(x) \frac{Y_n^m(y)}{|y|^{n+1}} ``` ```math \begin{aligned} \Phi(Y)&=\displaystyle\sum_{n=0}^{\infty} \displaystyle\sum_{m=-n}^{n}\displaystyle\sum_{i=1}^{N_c} q_i \cdot \rho_i^n \cdot Y_n^{-m}(\alpha_i, \beta_i) \frac{Y_n^m(\theta, \phi)}{r^{n+1}} \\ &=\displaystyle\sum_{n=0}^{\infty} \displaystyle\sum_{m=-n}^{n} \frac{M_n^m}{r^{n+1}} \cdot Y_n^m(\theta, \phi) \end{aligned} ``` - Local expansion ![](http://data.xyzgate.com/25da128772026f2dc4290ca6825e6cd9.png) ```math \begin{aligned} \Phi(X)&=\displaystyle\sum_{j=0}^{\infty} \displaystyle\sum_{k=-j}^{j}\displaystyle\sum_{l=1}^{N_c} q_l \cdot \frac{Y_j^{-k}(\alpha_l,\beta_l)}{\beta_l^{j+1}} \cdot Y_j^k(\theta,\phi)\cdot r^j \\ &=\displaystyle\sum_{j=0}^{\infty} \displaystyle\sum_{k=-j}^{j} L_j^k \cdot Y_j^k(\theta,\phi)\cdot r^j \end{aligned} ``` - FMM: local expansion can be transformed from multipole expansion in each cell. Red particles in each cell (Multipole) --> act on black one (Local expansion) ![](http://data.xyzgate.com/43e5a4c7337409cc51bf11920aabffe4.png) For kernel $$\frac{1}{r}$$: Greengard, Rokhlin, 1987, 1997; For kernel $$\frac{exp(-kr)}{r}$$: Greengard, LF, Huang, JF, 2002 <page> ## Adaptive FMM (AFMM) =!= A 2D adaptive tree structure 4 levels $$\Longrightarrow\ $$ 256 smallest cells $$\Longrightarrow\ $$ 64 used cells ![](http://data.xyzgate.com/50a237683dee674d0231b50a594b0ed4.png) kernel $$1/r$$: Cheng, H, Greengard L, Rokhlin V, 1999 both kernels $$1/r$$ and $$e^{-kr}/r$$: Jingfang huang et al, (in AFMPB package), 2009, 2010 <page> ## Comparison between FFT and FMM Basic comparisons in execution time (seconds) between the FFT-based and FMM-based methods for calculating electrostatic interactions with cubic volume and spherical surface data. ![](http://data.xyzgate.com/939329bbed5560c768fb0f2623c6328c.png) <page> ## Parallel Adaptive FMM (pAFM) ![](http://data.xyzgate.com/f35ba6b5e6067e1ec18dd4d2f9c88bdd.png) A parallel traversing the FMM tree graph (ST-DAG) using **Cilk plus** *B. Zhang, B Lu, JF Huang, NP Pitsianis, Xiaobai Sun, et al. Commun. Comput. Phys., 13 (2013), 107* <page> ## BEM PB Solver: FMPB --> AFMPB --> pAFMPB **AFMPB** (Adaptive fast multipole Poisson-Boltzmann solver) Refs: Lu, BZ, Cheng, XL, Huang, JF, and McCammon, JA. *Proc. Natl. Acad. Sci. USA*, 103: 19314, 2006. BZ Lu, XL Cheng, JF Huang, JA McCammon, *Computer Physics Communications*, 181 (2010) 1150 Bo Zhang, Jingfang Huang,Benzhuo Lu et al, *Computer Physics Communications*, 190: 173, 2015 <page> ### Computational performance ![](http://data.xyzgate.com/eeb16ecfc62321bf866ae7b97ba072db.png) FMPB (2006, *PNAS*), for a case of 81920 boundary elements, --> ~ 40 folds speed up AFMPB (2009, *J. Chem. Theory Comput*), same case --> $$>$$100 folds speed up <page> ![](http://data.xyzgate.com/ddb3edf9f79bcf98934bc67f476491ad.png) ==! BZ Lu, XL Cheng, and JA McCammon. *J. Comput. Phys.*, 226:1348, 2007. <page> ### Surface potential of dengue virus System: ~$$10^6$$ atoms Mesh: Nodes: ~$$10^7$$ Triangles: $$2 \times 10^7$$ Edge length: ~ 1 $$\A$$ ![](http://data.xyzgate.com/d86f3f6fd5cda43d1ea5f8eeee4c6036.png) ==! *Bo Zhang, Jingfang Huang,Benzhuo Lu et al, Computer Physics Communications, 190: 173, 2015* <page> ### Two proteins: energy, force and torque calculations ![](http://data.xyzgate.com/3ac1c376c086634de63338209d509d65.png) <page> #=!= Other progress: **GPU-FMM+BEM** for Poisson Eq: GPUs --> billion unknowns ==! R. Yokota et al. *Computer Physics Communications*,182: 1272, 2011. ![](http://data.xyzgate.com/7d015d5a841c18b6b9a97413108b746d.png) <page> #=!= Relevant work - Models: nonlinear PB, electro-diffusion (PNP) ... - Methods: FD, FEM, FEM/BEM ... ![](http://data.xyzgate.com/9af4831a711e8c975a163594793082ca.png) <page> #=!= Source code: - AFMPB: **AFMPB**: http://cpc.cs.qub.ac.uk/summaries/AEGB_v1_0.html **pAFMPB**: http://cpc.cs.qub.ac.uk/summaries/AEGB_v1_1.html - adaptive parallel FMM library: **RECFMM (shared memory)**: For both Coulomb (Laplace kernel) and Screened Coulomb (Yukawa kernel) Interactions, recursive parallelization via CILK, Ref.: Bo Zhang, Jingfang Huang, Nikos P. Pitsianis and Xiaobai Sun, RECFMM: Recursive Parallelization of the Adaptive Fast Multipole Method for Coulomb and Screened Coulomb Interactions, *Computer Physics Communications*, 20: 534-550, 2016 **DASHMM (distributed and shared memory architectures)**(to be published and released): For generic Multipole Methods, Laplace Potential, Yukawa Potential, Helmholtz Potential. Ref.: J. DeBuhr, B. Zhang, T. Sterling, Revision of DASHMM: Dynamic Adaptive System for Hierarchical Multipole Methods, *Computer Physics Communications*, 2017 <page> ####=!= 一个科学计算网站: www.xyzgate.com <br><br><br> #=!= Thanks! <page> <page> An online scientific computing website: ##=!= www.xyzgate.com <page> 摘要: This talk will give a brief introduction on the application and development of boundary element methods for electrostatic interaction calculations, in particular focusing on solution of the linearized Poisson-Boltzmann equation in biomolecular modeling. Different aspects/directions will be discussed: efficient and accurate boundary element methods, fast algorithms such as fast multipole method for acceleration of the boundary integrals, parallelization, molecular surface mesh generation, incorporation into molecular dynamics simulation, applications, program packages and online computing. Keywords:BEM, Fast algorithm, Biomolecule, Poisson-Boltzmann electrostatics, online computing 边界元, Taking derivatives of the BIEs ```math \frac{\partial \phi_p^{int}}{\partial n_0} =\oint_{\footnotesize S} [\frac{\partial G_{pt}}{\partial n_0} \frac{\partial \phi_t^{int}}{\partial n} -\frac{{\partial}^2 G_{pt}}{\partial n_0 \partial n} \phi_t^{int}]dS_t + \frac{1}{D_{int}} \displaystyle\sum_k q_k \frac{\partial G_{pk}}{\partial n_0}, ``` ```math \frac{\partial \phi_p^{ext}}{\partial n_0} =\oint_{\footnotesize S} [-\frac{\partial u_{pt}}{\partial n_0} \frac{\partial \phi_t^{ext}}{\partial n} + \frac{{\partial}^2 u_{pt}}{\partial n_0 \partial n} \phi_t^{ext}]dS_t,\ p\in \overline{\Omega} ``` Let $$ {p \to S}$$, we get the dBIEs: <page> Considering geometric modification, the BIEs for PBE: ```math \alpha_p \phi_p^{int}=\oint_{\footnotesize S}^{\footnotesize {PV}} [G_{pt} \frac{\partial \phi_t^{int}}{\partial n} -\frac{\partial G_{pt}}{\partial n} \phi_t^{int}]dS_t + \frac{1}{D_{int}} \displaystyle\sum_k q_k G_{pk}, \ p\in S ``` ```math (1-\alpha_p) \phi_p^{ext}=\oint_{\footnotesize S}^{\footnotesize {PV}} [-u_{pt} \frac{\partial \phi_t^{ext}}{\partial n}+\frac{\partial u_{pt}}{\partial n} \phi_t^{ext}]dS_t,\ p \in S ``` where $$\alpha_p=A_p/4\pi$$, $$A_p$$ is the interior solid andgle at node $$p$$. The BEM Solution at the First Five Nodes on a Unit Spherical Surface: ![](http://data.xyzgate.com/f8ad62cc491c717c76bc4f4eef721c34.png) $$f_N$$ and $$h_N$$ are the potential and its normal derivative, respectively, obtained with the normal BIE, and $$f_M$$ and $$h_M$$ are from the geometrically modified BIE. <page> ###Benzhuo Lu (卢本卓) ###Institute of Computational Math and Scientific/Engineering Computing, Chinese Academy of Sciences, China ### (科学院计算数学与科学工程计算研究所,国家数学与交叉科学中心) ### Guilin, July 25, 2017 ##National Center for Mathematics and Interdisciplinary Sciences, Acknowledgement: Jingfang Huang (黄京芳) (Univ. of North Carolina, US) Xiaolin Cheng (Oak Ridge National Lab, US) Bo Zhang (Indiana University, IN, USA) Nikos P. Pitsianis, and Xiaobai Sun (Duke University, US) J. Andrew McCammon (Uinv. Calfornia, San Diego) Minxin Chen, (Soochow Univ., Suzhou, China) Tiantian Liu (Inst Computational Math, CAS, China) Bo Peng (Inst Computational Math, CAS, China) http://lsec.cc.ac.cn/~lubz/afmpb.html [](### 桂林,2017-7-29)
×
打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮