臺灣博碩士論文加值系統

探討微粒-微粒與微粒-平板之間的相互作用力在生物化學的領域是相當重要的。在假設電解液為平衡的狀態下，可以經由著名的Poisson-Boltzmann方程式電雙層理論得到帶電物體的勢能分佈。因此，我們決定開發以有限元素法三維平行化非線性Poisson-Boltzmann方程式程式(PPBS)搭配平行化調適網格加加密功能程式(PAMR)，並且完成驗證的工作。本論文之研究分成兩大主軸，分別敘述如下：
第一部分，以非線性Poisson-Boltzmann方程式採用非結構性四面體網格之葛勒金有限元素法來完成程式開發，包括了典型的一階與二階的形狀函數元素。因為使用了nodal quadrature的技巧，使得原先的牛頓法Jacobian矩陣僅剩下對角線，以此擬牛頓疊代法來處理非線性項矩陣的部份，有助於平行化程式的完成。接下來，則使用SBS的技巧搭配平行的共軛梯度法來處理線性矩陣方程組。完成的程式以兩個範例來驗證，第一個驗證的範例是帶電球體的勢能分佈，所得答案與解析解、近似解作一比較，結果相當正確。第二個驗證範例則是兩個帶電球體在圓柱孔內，結果顯示與先前所發表的論文結果相符。以上兩個驗證範例證明了平行化Poisson-Boltzmann方程式程式的開發完成。此外，平行化效能使用國家高速網路與計算中心的HP 叢集式電腦系統來做驗證，測試一個帶電球體在圓柱孔內的範例，結果顯示使用了32顆CPU時仍有76.2%的平行效能。在第一部份的最後，我們使用了二階形狀函數元素，所得結果證明了比一階形狀函數元素要來的準確。
第二部份，主要是發展一個以非結構性四面體網格為主，採用h-切割為基礎之分散式記憶體動態領域分解的PAMR程式，而資料結構則使用了較節省記憶體空間之cell-base方式來記錄網格的資訊，可以同時運用在node-base與cell-base的數值方法上。一般的步驟包括了一個分為八個網格的等向性切割，然後以非等向切割搭配網格品質控制將hanging node有效率地移除。我們測試PAMR在叢集式電腦上最多64顆CPU的平行化效能，結果呈現在32顆CPU時仍有N1.5的效能(N為CPU個數)。接著我們將PPBES與PAMR做一個結合，並使用a posteriori的誤差評估方法，驗證兩個帶電球體在圓柱孔內，結果證明了使用PAMR可以增加PPBES解的準確度。最後，利用PPBES-PAMR的程式模擬兩個帶電球體靠近帶電平板的相互影響力之分析，與實驗結果相比較，若考慮實驗本身的不確定因素與誤差，模擬結果與實驗結果有相當程度的符合，這是目前已知與實驗結果相比較之最佳模擬結果。

Understanding of the interactive particle-particle and particle-wall forces in colloidal systems (electrolytes) plays a very important role in bio-chemistry related research. By assuming equilibrium in the electrolytes, the potential distribution with a very thin electrical double layer near the charged object can be well described by the well-known Poission-Boltzmann equation. Thus, a parallelized 3-D nonlinear Poisson-Boltzmann equation solver (PPBES) using finite element method (FEM) with parallel adaptive mesh refinement (PAMR) is proposed and verified. In this thesis, the research is divided into two phases, which are described as follows.
In the first phase, the nonlinear Poisson-Boltzmann equation is discretized using Galerkin finite element method with unstructured tetrahedral mesh. Interpolation within a typical element includes the first-order and second-order shape functions. Inexact Newton iterative scheme is used to solve the nonlinear matrix equation resulting from the FE discretization. Jacobian matrix resulting from the Newton iterative scheme is diagonalized using nodal quadrature, which further facilitates the easier parallel implementation. A parallel conjugate gradient (CG) method with a subdomain-by-subdomain (SBS) scheme is then used to solve the linear algebraic equation each iterative step. Completed code is verified using two typical examples. The first validated case is the potential distribution around a charged sphere. Excellent agreement of the simulation results with analytical (linearized case) and approximate (nonlinear case) solutions are obtained. The second validated case is the interaction between like-charged spheres within a cylindrical pore. Results show that the agreement between the present simulation and previous results are excellent. The above two typical simulations validate the present implementation of the PPBES. Further, the parallel performance is studied on a HP PC-cluster system at NCHC using a test case with a charged sphere confined in a cylindrical pore. Results show that 76.2% of parallel efficiency can be reached at processors of 32. Also FE discretization using the second-order shape function is demonstrated to be more accurate than using the first-order shape function at the end of this phase.
In the second phase, an h-refinement based PAMR scheme for an unstructured tetrahedral mesh using dynamic domain decomposition on a memory-distributed machine is developed and tested in detail. A memory-saving cell-based data structure is designed such that the resulting mesh information can be readily utilized in both node- or cell-based numerical methods. The general procedures include isotropic refinement from one parent cell into eight child cells and then followed by anisotropic refinement, which effectively removes the hanging nodes, with a simple mesh-quality control scheme. Parallel performance of this PAMR is studied on a PC-cluster system up to 64 processors. Results show that the parallel speedup scales approximately as N1.5 up to 32 processors, where N is the number of processors. Then, procedure of coupling the PPBES with the PAMR using a posteriori error estimator is presented and verified using a test case with two like-charged spheres in a cylindrical pore. Results show that PAMR can systematically increase the solution accuracy of the PPBES. Finally, the coupled PPBES-PAMR code is used to simulate the interactive force between two like-charged spheres near a charged planar wall. Results are in excellent agreement with experimental data considering the experimental uncertainties, which is the first simulation in the literature to the best knowledge of the author.

Abstract i
中文摘要 iv
Table of Contents vi
List of Tables viii
List of Figures ix
Symbols xi
Chapter 1 Introduction 1
1-1 Motivation 1
1-2 Background 2
1-2-1 Poisson-Boltzmann Equation 2
1-2-1-1 Nature of Colloidal Solutions 2
1-2-1-2 Zeta Potential 3
1-2-1-3 Electric Double Layer 4
1-2-1-4 Applications of Poisson-Boltzmann Equation 6
1-2-2 Adaptive Mesh Refinement (AMR) 7
1-2-2-1 Local Polynomial-Degree-Variation (p-refinement) 8
1-2-2-2 Mesh Movement (r-refinement) 8
1-2-2-3 Mesh Enrichment (h-refinement) 9
1-3 Literature Surveys 9
1-3-1 Numerical Simulation of Poisson-Boltzmann Equation 9
1-3-2 Mesh Refinement 12
1-3-2-1 Adaptive Mesh Refinement 12
1-3-2-2 Parallel Adaptive Mesh Refinement (PAMR) 13
1-4 Objectives of the Thesis 16
1-5 Organization of the Thesis 16
Chapter 2 Parallelized Poisson-Boltzmann Equation Solver (PPBES) Using Finite-Element Method 18
2-1 Theoretical Model and Analysis EDL 18
2-2 Discretization Using Finite Element Method with Tetrahedral Mesh 20
2-2-1 Interpolation with First-order Shape Function 22
2-2-2 Interpolation with Second-order Shape Function 27
2-3 Conjugate Gradient Method for Linear Algebra Equation 29
2-4 Inexact Newton-Raphson Iterative Scheme 32
2-5 Parallel Implementation of the P-B Equation Solver 33
2-5-1 Introduction to Parallel Computing 33
2-5-2 Parallel Implementation 35
2-6 Force Calculation in an Electrostatic Field 37
Chapter 3 Validation of the Parallel Poisson-Boltzmann Equation Solver 39
3-1 Convergence of the PPBES 39
3-2 Validation 1: The Potential Distribution around a Charged Sphere 40
3-3 Validation 2: Interaction Between Two Like-charged Spheres within a Cylindrical Pore 41
3-4 Parallel performance of the PPBES 42
3-5 The Second-order Shape Function for PPBES 43
Chapter 4 Parallel Adaptive Mesh Refinement for Unstructured Tetrahedral Mesh 46
4-1 Parallel Adaptive Mesh Refinement 46
4-1-1 Basic Algorithm of Parallel Adaptive Mesh Refinement 46
4-1-2 Cell Neighboring Connectivity 48
4-1-3 Cell-Quality Controls 50
4-1-4 Surface Cell Refinement 53
4-1-5 Modules of Parallel Adaptive Mesh Refinement 54
4-1-6 Procedures of Parallel Adaptive Mesh Refinement 57
4-2 Coupling of PAMR with Parallelized Poisson-Boltzmann Equation Solver 60
4-2-1 A posteriori error estimator 60
4-2-2 Parallelized Poisson-Boltzmann Equation Solver with PAMR 63
4-3 Validation and Parallel Performance of PAMR 64
4-3-1 Validation of the PAMR 64
4-3-2 Parallel Performance of the PAMR 66
4-4 Application to a Realistic Three-dimensional Problem 67
Chapter 5 Concluding Remarks 70
5-1 Summary 70
5-2 Recommendations for Future Work 73
REFERENCES 74
Appendix A Diagonalization of the Jacobian Using Nodal Quadrature 139
Appendix B Three-dimensional Hybrid Mesh 144
B-1 Hybrid Mesh 144
B-2 Shape Function of Hexahedral Element 144
B-3 The Second-Order shape function 148
Appendix C First-order Shape Function of Tetrahedron Element 153
Appendix D Second-order Shape Function of Tetrahedron Element 156

1. Almasi, G. and Gottlieb, A., “Highly Parallel Computing,” Benjamin/Cummings, Red-Wood city, CA, 2nd Editon 1989.
2. Bowen, W.R. and Sharif, A.O., “Long-range electrostatic attraction between like-charge spheres in a charged pore,” Nature, Vol.393, pp.663-665, 1998.
3. Bowen, W.R. and Sharif, A.O., “Adaptive finite-element solution of the nonlinear Poisson-Boltzmann equation: A. charged spherical particle at various distances from a charged cylindrical pore in a charged planar surface,” Journal Colloid Interface Sci., Vol.187, pp.363-374, 1997.
4. Brackbill, JU, “An adaptive grid with direction control,” Journal of Computational Physics, Vol.108, pp.38–50, 1993.
5. Baker, N., Holst, M. and Wang, F., “Adaptive multilevel finite element solution of the Poisson-Boltzmann equation II. Refinement at solvent-accessible surfaces in biomolecular systems,” Journal of Computational Chemistry, Vol.21, pp. 1343-1352, 2000.
6. Baker, N. A., Sept, D., Joseph, S., Holst, M. J. and McCammon, J. A., “Electrostatics of nanosystems: Application to microtubules and the ribosome,” Proceedings of the National Academy of Sciences of the United States of America, 98, pp.10037-10041, 2001a.
7. Baker, N., Sept, D., Holst, M. and McCammon, J. A.,"The adaptive multilevel finite element solution of the Poisson-Boltzmann Equation on massively parallel computers," IBM Journal of Research and Development, Vol.45, No.3/4, page 427, 2001b.
8. Balls, G. T. and Colella, P., “A Finite Difference Domain Decomposition Method Using Local Corrections for the Solution of Poisson's Equation, Journal of Computational Physics, Vol.180, pp.25-53, 2002.
9. Bank, R. E. and Holst, M., “A new paradigm for parallel adaptive meshing algorithms,” Siam Journal on Scientific Computing, Vol.22, pp.1411-1443, 2000.
10. Carnie, S. L., Chen, D. Y. C., and Stankovich, J., "Computation of forces between spherical colloidal particles: Nonlinear Poisson-Boltzmann Theory," Journal of Colloid and Interface Science, Vol.165, pp.116-128, 1994.
11. Cortis, C. M. and Friesner, R. A., “An automatic three-dimensional finite element mesh generation system for the Poisson-Boltzmann equation,” Journal of Computational Chemistry, Vol.18, pp.1570-1590, 1997a.
12. Cortis, C. M. and Friesner, R. A., “Numerical solution of the Poisson-Boltzmann equation using tetrahedral finite-element meshes,” Journal of Computational Chemistry, Vol.18, pp.1591-1608, 1997b.
13. Collins, John and Lee, Abraham P., “Microfluidic flow transducer based on the measurement of electrical admittance,” Lab on a Chip, NO.4(1), pp.7-10, 2004.
14. Connell, S.D. and Holms, D.G., “Three-Dimensional Unstructured Adaptive Multigrid Scheme for the Euler Equations,” AIAA Journal, Vol.32, pp.1626-1632, 1994.
15. Chandra, R., Dagum, L., Kohr, D., Maydan, D., J. McDonald, “Parallel programming in OpenMP,” Morgan Kaufmann Publishers, San Francisco, CA, 2000.
16. Das, P.K. and Bhattacharjee, S., “Finite Element Estimation of Electrostatic Double Layer Interaction between Colloidal Particles inside a Rough Cylindrical Capillary: Effect of Charging Behavior,” Colloids and Surface A, Vol.256, pp.91-103, 2005.
17. Dyshlovenko, Pavel, “Adaptive Mesh Enrichment for the Poisson-Boltzmann Equation,” Journal of Computation Physics, Vol.172, pp.198-208, 2001.
18. Dyshlovenko, Pavel, “Adaptive numerical method for Poisson-Boltzmann equation and its application,” Computer Physics Communications, Vol.147, pp.335-338, 2002.
19. Fogolari, Federico, Zuccato, Pierfrancesco, Esposito Gennaro and Viglino, Paolo, "Biomolecular Electrostatics with the Linearized Poisson-Boltzmann Equation," Biophysical Journal, Vol.76, pp.1-16, 1999.
20. Gilson, M. K., Davis, M. E., Luty, B. A. and McCammon, J. A., "Computation of electrostatic forces on solvated molecules using the Poisson-Boltzmann equation," Journal of Physical Chemistry, Vol.97, pp.3591–3600, 1993.
21. Gowda, Shivaraju B. “A Comparison of Sparse & Element-by-Element Storage Schemes on The Efficiency of Parallel Conjugate Gradient Iterative Methods for Finite Element Analysis”, MS thesis, Graduate School of Clemeson University, 2002.
22. Hunter, R. J., “Foundations of Colloid Science,” Vol.2, Oxford: Clarendon Press, 1989.
23. Holst, M., Baker, N. and Wang ,F., “Adaptive multilevel finite element solution of the Poisson-Boltzmann equation I. Algorithms and examples, Journal of Computational Chemistry, Vol.21, pp.1319-1342, 2000.
24. Holst, M., Kozack, R. E., Saied, F. and Subramaniam, S., “Protein electrostatics: rapid multigrid-based Newton algorithm for solution of the full nonlinear Poisson-Boltzmann equation,” Journal of Biomolecular Structure and Dynamics, Vol.11, pp.1437-45, 1994a.
25. Holst, M., Kozack, R. E., Saied, F. and Subramaniam, S., “Treatment of electrostatic effects in proteins: multigrid-based Newton iterative method for solution of the full nonlinear Poisson-Boltzmann equation,” Proteins, Vol.18, pp. 231-45, 1994b.
26. Hoskin, N. E., "The interaction of two identical spherical colloidal particles I-- Potential Distribution," Proceedings of the Royal Society (London), Series A, 248, pp.433-448, 1956.
27. Hestenes, M. and Stiefel E. ,"Methods of Conjugate Gradient for Solving Linear Systems," Journal of research of the National Bureau of Standards, Vol.49, pp.409-439, 1952.
28. Harries, Daniel, "Solving the Poisson-Boltzmann Equation for Two Parallel Cylinders," Langmuir, Vol.14, pp.3149-3152, 1998.
29. Wu, Fu-Yuan, "The Three-Dimensional Direct Simulation Monte Carlo Method Using Unstructured Adaptive Mesh and It Applications," MS Thesis, NCTU, Hsinchu, Taiwan , July, 2002.
30. Hsu, K.-H., “Development of a Parallelized PIC-FEM Code Using a Three-Dimensional Unstructured Mesh and Its Applications,” PhD Thesis, NCTU, Hsinchu, Taiwan, July, 2006.
31. Kuo, Chia-Hao, "The Direct Simulation Monte Carlo Method Using Unstructured Adaptive Mesh and Its Applications," MS Thesis, NCTU, Hsinchu, Taiwan, June, 2000.
32. Kozack, R. E. and Subramaniam, S., “Brownian dynamics simulations of molecular recognition in an antibody-antigen system,” Protein Science, Vol.2, pp.915-926, 1993.
33. Kallinderis, Y. and Vijayan, P., “Adaptive Refinement-Coarsening Scheme for Three-Dimensional Unstructured Meshes”, AIAA JOURNAL, Vol.31, No.8, 1993.
34. Karypis, G., Kumar, V., ParMETIS 3.1: An MPI-based Parallel Library for Partitioning Unstructured Graphs, Meshes, and Computing Fill-Reducing Orderings of Sparse matrices, 2003. Available from (http://www-users.cs.umn.edu/~karypis/metis/parmetis).
35. Larsen, A.E. and Grier, D.G., “Like-charge attractions in metastable colloidal crystallites,” Nature, Vol.385, pp.230-233, 1997.
36. Lian, Y.-Y., Hsu, K.-H., Shao, Y.-L., Lee ,Y.-M., Jeng, Y.-W. and Wu, J.-S.,“Parallel Adaptive Mesh-Refining Scheme on Three-dimensional Unstructured Mesh and Its Applications,” Computer Physics Communications (Accepted in May 2006).
37. Mackenzie, J. A. and Robertson, M. L., “A moving mesh method for the solution of the one-dimensional phase-field equations,” Journal of Computational Physics, Vol.181, pp.526–544, 2002.
38. MacNeice, P., Olsonb, K.M., C. Mobarry, R. de Fainchtein, Packer, Charles, Computer Physics Communications, Vol.126, pp.330, 2000.
39. MPI library, http://www-unix.mcs.anl.gov/mpi
40. METIS library, http://glaros.dtc.umn.edu/gkhome/views/metis
41. MANIFOLD CODE http://www.scicomp.ucsd.edu/~mholst/codes/mc
42. Nadeem, S A and Jimack, P K, “Parallel implementation of an optimal two level additive Schwarz preconditioner for the 3-D finite element solution of elliptic partial differential equations,” International Journal for Numerical Methods in Fluids, Vol.40, pp.1571, 2002.
43. Norton, C.D., Lou, J.Z. and Cwik, T., “Status and Directions for the PYRAMID Parallel Unstructured AMR Library,” Proceedings of the 15th International Parallel & Distributed Processing Symposium, IEEE Computer Society, Washington, DC, 2001.
44. Neu, J.C., "Wall-Mediated Forces between Like-Charged Bodies in an Electrolyte," Physical Review Letters, Vol.82, pp.1072-1074, 1999.
45. Oliker, L., Biswas, R., Gabow, H.N., “Parallel Tetrahedral Mesh Adaptation with Dynamic Load Balancing.,” Parallel Computing Journal, Vol.26, pp.1583-1608, 2000.
46. Okubo, T. and Aotani, S., “Microscopic observation of ordered colloids in sedimentation equilibrium and the importance of the Debye-screening length. 9. Compressed crystals of giant colloidal spheres,” Colloid & Polymer Science, Vol.266, No.11, pp.1042-1048, 1988.
47. Peano, A .G.., “Hierarchies of Conforming Finite Elements for Plane Elasticity and Plate Bending,” Journal of Computers and Mathematics with Applications, Vol.2, pp.211-224, 1976.
48. Pao, C. V., "Block monotone iterative methods for numerical solutions of nonlinear elliptic equations," Numerische Mathematik, Vol.72, pp.239-262, 1995.
49. Prof. F.-N. Hwang, http://www.math.ncu.edu.tw/~hwangf
50. Quddus, N., Bhattacharjee, S. and Moussa, W., “An Electrostatic–Peristaltic Colloidal Micropump: A Finite Element Analysis,” Journal of Computational and Theoretical Nanoscience, Vol.1, No.4, pp.438-444, 2004.
51. Rausch, R.D., Batina, J.T. and Yang, H.T.Y., "Spatial Adaption Procedures on Unstrutuctured Meshes for Accurate Unsteady Aerodynamics Flow Computation," AIAA Paper, No.91-1106-CP, 1991.
52. Russel, W. B., Saville, D. A., and Schowalter, W. R., “Colloidal Dispersions,” Cambridge Univ. Press, Cambridge, England, 1989.
53. Shao, Z., Ren, C. L. and Schneider, G. E., “3D Electrokinetic Flow Structure of Solution Displacement in Microchannels for on-Chip Sample Preparation Applications”, Journal of Micromechanics and Microengineering, Vol.16, pp.589-600, 2006.
54. Sharp, K. A. and Honig, B., "Calculating total electrostatic energies with the nonlinear Poisson-Boltzmann equation," Journal of Physical Chemistry, Vol.94, pp.7684-7692, 1990.
55. Squires, Todd M. and Brenner, Michael P., “Like-Charge Attraction and Hydrodynamic Interaction,” Physical Review Letters, Vol.85, pp.4976-4979, 2000.
56. Saad, Yousef, “Iterative Method for Sparse Linear System,” Society for Industrial and Applied Mathematics, 2003.
57. Tuinier, R., “Approximate solutions to the Poisson-Boltzmann equation in spherical and cylindrical geometry,” Journal of Colloid and Interface Science, Vol.258, pp.45-49, 2003.
58. Thompson, Erik G., "Introduction to the Finite Element Method: Theory, Programming and Applications," John Wiley & Sons Inc, 2003.
59. Waltz, J., “Parallel adaptive refinement for unsteady flow calculations on 3D unstructured grids,” International Journal for Numerical Methods in Fluids, Vol.46, pp.37-57, 2004.
60. Wang, L. and Harvey, J.K., “The Application of Adaptive Unstructured Grid Technique to the Computation of Rarefied Hypersonic Flows Using the DSMC Method,” 19th International Symposium on Rarefied Gas Dynamics, Harvey J, Lord G (ed.), pp.843, 1994.
61. Wu, J.-S., Tseng, K.-C. and Wu, F.-Y., “Three Dimensional Direct Simulation Monte Carlo Method Using Unstructured Adaptive Mesh and Variable Time Step,” Computer Physics Communications, Vol. 162, No. 3, pp.166-187, 2004.
62. Wu, Fu-Yuan, "The Three-Dimensional Direct Simulation Monte Carlo Method Using Unstructured Adaptive Mesh and It Applications," MS Thesis, NCTU, Hsinchu, Taiwan, July, 2002.
63. Yang, R.-J., Fu, L.-M. and Lin, Y.-C., “Electroosmotic Flow in Microchannels,” Journal of Colloid and Interface Science, Vol.239, pp.98-105, 2001.
64. Zienkiewicz, O. C., J. P. de S. R. Gago and Kelly, D. W., “The Hierarchical Concept in Finite Element Analysis,” Computers and Structures, Vol.16, No.1-4, pp.53-65, 1983.
65. Zienkiewicz, O.C. and Zhu, J.Z., “A Simple Error Estimator And Adaptive Procedure For Practical Engineering Analysis,” International Journal for Numerical Methods in Engineering, Vol.24, pp.337-357, 1987.
66. Zienkiewicz, O.C. and Taylor, R.L., “The Finite Element Method,” Butterworth-Heinemann, Oxford, 5th edition, 2000.