Abstract
In this work, we propose efficient and accurate numerical algorithms based on difference potentials method for numerical solution of chemotaxis systems and related models in 3D. The developed algorithms handle 3D irregular geometry with the use of only Cartesian meshes and employ Fast Poisson Solvers. In addition, to further enhance computational efficiency of the methods, we design a difference-potentials-based domain decomposition approach which allows mesh adaptivity and easy parallelization of the algorithm in space. Extensive numerical experiments are presented to illustrate the accuracy, efficiency and robustness of the developed numerical algorithms.
Similar content being viewed by others
References
Adler, J.: Chemotaxis in bacteria. Annu. Rev. Biochem. 44(1), 341–356 (1975). https://doi.org/10.1146/annurev.bi.44.070175.002013
Albright, J., Epshteyn, Y., Medvinsky, M., Xia, Q.: High-order numerical schemes based on difference potentials for 2d elliptic problems with material interfaces. Appl. Numer. Math. 111, 64–91 (2017). https://doi.org/10.1016/j.apnum.2016.08.017
Albright, J., Epshteyn, Y., Xia, Q.: High-order accurate methods based on difference potentials for 2D parabolic interface models. Commun. Math. Sci. 15(4), 985–1019 (2017). https://doi.org/10.4310/CMS.2017.v15.n4.a4
Blanchet, A., Carrillo, J.A., Kinderlehrer, D., Kowalczyk, M., Laurençot, P., Lisini, S.: A hybrid variational principle for the Keller–Segel system in \({\mathbb{R}}^2\). ESAIM Math. Model. Numer. Anal. 49(6), 1553–1576 (2015). https://doi.org/10.1051/m2an/2015021
Bonner, J.T.: The Cellular Slime Molds, 2nd edn. Princeton University Press, Princeton (1967). https://doi.org/10.1515/9781400876884
Budrene, E.O., Berg, H.C.: Complex patterns formed by motile cells of Escherichia coli. Nature 349(6310), 630–633 (1991). https://doi.org/10.1038/349630a0
Budrene, E.O., Berg, H.C.: Dynamics of formation of symmetrical patterns by chemotactic bacteria. Nature 376(6535), 49–53 (1995). https://doi.org/10.1038/376049a0
Chertock, A., Epshteyn, Y., Hu, H., Kurganov, A.: High-order positivity-preserving hybrid finite-volume-finite-difference methods for chemotaxis systems. Adv. Comput. Math. (2017). https://doi.org/10.1007/s10444-017-9545-9
Chertock, A., Kurganov, A.: A second-order positivity preserving central-upwind scheme for chemotaxis and haptotaxis models. Numer. Math. 111(2), 169–205 (2008). https://doi.org/10.1007/s00211-008-0188-0
Chertock, A., Kurganov, A.: High-resolution positivity and asymptotic preserving numerical methods for chemotaxis and related models. Active Particles, 2: Advances in Theory, Models, and Applications, Modeling and Simulation in Science, Birkhauser/Springer, Cham (accepted)
Childress, S., Percus, J.: Nonlinear aspects of chemotaxis. Math. Biosci. 56(3–4), 217–237 (1981). https://doi.org/10.1016/0025-5564(81)90055-9
Cohen, M.H., Robertson, A.: Wave propagation in the early stages of aggregation of cellular slime molds. J. Theor. Biol. 31(1), 101–118 (1971). https://doi.org/10.1016/0022-5193(71)90124-x
Epshteyn, Y.: Upwind-difference potentials method for Patlak–Keller–Segel chemotaxis model. J. Sci. Comput. 53(3), 689–713 (2012). https://doi.org/10.1007/s10915-012-9599-2
Epshteyn, Y.: Algorithms composition approach based on difference potentials method for parabolic problems. Commun. Math. Sci. 12(4), 723–755 (2014). https://doi.org/10.4310/CMS.2014.v12.n4.a7
Epshteyn, Y., Izmirlioglu, A.: Fully discrete analysis of a discontinuous finite element method for the Keller–Segel chemotaxis model. J. Sci. Comput. 40(1–3), 211–256 (2009). https://doi.org/10.1007/s10915-009-9281-5
Epshteyn, Y., Kurganov, A.: New interior penalty discontinuous galerkin methods for the keller–segel chemotaxis model. SIAM J. Numer. Anal. 47(1), 386–408 (2008). https://doi.org/10.1137/07070423x
Frigo, M.: A fast fourier transform compiler. In: Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation-PLDI ’99. ACM Press (1999). https://doi.org/10.1145/301618.301661
Gholami, A., Malhotra, D., Sundar, H., Biros, G.: FFT, FMM, or multigrid? A comparative study of state-of-the-art poisson solvers for uniform and nonuniform grids in the unit cube. SIAM J. Sci. Comput. 38(3), C280–C306 (2016). https://doi.org/10.1137/15M1010798
Herrero, M.A., Velázquez, J.J.L.: A blow-up mechanism for a chemotaxis model. Ann. Scuola Norm. Super. 24, 633–683 (1997)
Hillen, T., Painter, K.J.: A user’s guide to PDE models for chemotaxis. J. Math. Biol. 58(1–2), 183–217 (2008). https://doi.org/10.1007/s00285-008-0201-3
Horstmann, D.: From 1970 until now: the Keller–Segel model in chemotaxis and its consequences i. Jahresber. DMV 105, 103–165 (2003)
Horstmann, D.: From 1970 until now: the Keller–Segel model in chemotaxis and its consequences ii. Jahresber. DMV 106, 51–69 (2004)
Huang, H., Liu, J.G.: Discrete-in-time random particle blob method for the Keller–Segel equation and convergence analysis. Commun. Math. Sci. 15(7), 1821–1842 (2017). https://doi.org/10.4310/CMS.2017.v15.n7.a2
Hubbert, S., Gia, Q.T.L., Morton, T.M.: Spherical Radial Basis Functions. Theory and Applications. Springer, Berlin (2015). https://doi.org/10.1007/978-3-319-17939-1
Hundsdorfer, W., Verwer, J.: Numerical Solution of Time-Dependent Advection–Diffusion–Reaction Equations, Springer Series in Computational Mathematics, vol. 33. Springer, Berlin (2003). https://doi.org/10.1007/978-3-662-09017-6
Jordan, R., Kinderlehrer, D., Otto, F.: The variational formulation of the Fokker–Planck equation. SIAM J. Math. Anal. 29(1), 1–17 (1998). https://doi.org/10.1137/s0036141096303359
Jüngel, A., Leingang, O.: Blow-up of solutions to semi-discrete parabolic-elliptic Keller–Segel models. Discrete Contin. Dyn. Sys. B 25, 1 (2018)
Keller, E.F., Segel, L.A.: Initiation of slime mold aggregation viewed as an instability. J. Theor. Biol. 26(3), 399–415 (1970). https://doi.org/10.1016/0022-5193(70)90092-5
Keller, E.F., Segel, L.A.: Model for chemotaxis. J. Theor. Biol. 30(2), 225–234 (1971). https://doi.org/10.1016/0022-5193(71)90050-6
Li, X.H., Shu, C.W., Yang, Y.: Local discontinuous galerkin method for the Keller–Segel chemotaxis model. J. Sci. Comput. 73(2), 943–967 (2017). https://doi.org/10.1007/s10915-016-0354-y
Lie, K.A., Noelle, S.: On the artificial compression method for second-order nonoscillatory central difference schemes for systems of conservation laws. SIAM J. Sci. Comput. 24(4), 1157–1174 (2003). https://doi.org/10.1137/S1064827501392880
Liu, J.G., Wang, L., Zhou, Z.: Positivity-preserving and asymptotic preserving method for 2D Keller-Segal equations. Math. Comp. 87(311), 1165–1189 (2018). https://doi.org/10.1090/mcom/3250
Liu, J.G., Yang, R.: A random particle blob method for the Keller–Segel equation and convergence analysis. Math. Comp. 86(304), 725–745 (2017). https://doi.org/10.1090/mcom/3118
Ludvigsson, G., Steffen, K.R., Sticko, S., Wang, S., Xia, Q., Epshteyn, Y., Kreiss, G.: High-order numerical methods for 2D parabolic problems in single and composite domains. J. Sci. Comput. 76(2), 812–847 (2018). https://doi.org/10.1007/s10915-017-0637-y
Magura, S., Petropavlovsky, S., Tsynkov, S., Turkel, E.: High-order numerical solution of the Helmholtz equation for domains with reentrant corners. Appl. Numer. Math. 118, 87–116 (2017). https://doi.org/10.1016/j.apnum.2017.02.013
Nanjundiah, V.: Chemotaxis, signal relaying and aggregation morphology. J. Theor. Biol. 42(1), 63–105 (1973). https://doi.org/10.1016/0022-5193(73)90149-5
Nessyahu, H., Tadmor, E.: Nonoscillatory central differencing for hyperbolic conservation laws. J. Comput. Phys. 87(2), 408–463 (1990). https://doi.org/10.1016/0021-9991(90)90260-8
Patlak, C.S.: Random walk with persistence and external bias. Bull. Math. Biophys. 15(3), 311–338 (1953). https://doi.org/10.1007/bf02476407
Perthame, B.: Transport equations in biology. Front. Math. Birkhäuser Verlag (2007). https://doi.org/10.1007/978-3-7643-7842-4
Prescott, L., Harley, J., Klein, D.: Microbiology, 3rd edn. Wm. C. Brown Publishers, Chicago (1996)
Ryaben’kii, V.S.: Method of Difference Potentials and Its Applications, Springer Series in Computational Mathematics, vol. 30. Springer, Berlin (2002). https://doi.org/10.1007/978-3-642-56344-7. (Translated from the 2001 Russian original by Nikolai K. Kulman)
Sokolov, A., Strehl, R., Turek, S.: Numerical simulation of chemotaxis models on stationary surfaces. Discrete Contin. Dyn. Syst. Ser. B 18(10), 2689–2704 (2013). https://doi.org/10.3934/dcdsb.2013.18.2689
Strehl, R., Sokolov, A., Kuzmin, D., Horstmann, D., Turek, S.: A positivity-preserving finite element method for chemotaxis problems in 3d. J. Comput. Appl. Math. 239, 290–303 (2013). https://doi.org/10.1016/j.cam.2012.09.041
Strehl, R., Sokolov, A., Kuzmin, D., Turek, S.: A flux-corrected finite element method for chemotaxis problems. Comput. Methods Appl. Math. 10(2), 219 (2010). https://doi.org/10.2478/cmam-2010-0013
Sweby, P.K.: High resolution schemes using flux limiters for hyperbolic conservation laws. SIAM J. Numer. Anal. 21(5), 995–1011 (1984). https://doi.org/10.1137/0721062
Tadmor, E.: A review of numerical methods for nonlinear partial differential equations. Bull. Am. Math. Soc. (N.S.) 49(4), 507–554 (2012). https://doi.org/10.1090/S0273-0979-2012-01379-4
Tyson, R., Stern, L., LeVeque, R.J.: Fractional step methods applied to a chemotaxis model. J. Math. Biol. 41(5), 455–475 (2000). https://doi.org/10.1007/s002850000038
van Leer, B.: Towards the ultimate conservative difference scheme. V. A second-order sequel to Godunov’s method. J. Comput. Phys. 32(1): 101–136 (1979). J. Comput. Phys. 135(2), 227–248 (1997). https://doi.org/10.1006/jcph.1997.5757. With an introduction by Ch. Hirsch, Commemoration of the 30th anniversary of J. Comput. Phys
Acknowledgements
The research of Y. Epshteyn and Q. Xia was partially supported by National Science Foundation Grant # DMS-1112984. Q. Xia would also like to thank N. Beebe, M. Berzins, M. Cuma and H. Sundar for helpful discussions on different aspects of high-performance computing related to this work. Q. Xia gratefully acknowledges the support of the University of Utah, Department of Mathematics.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
5 Appendix
5 Appendix
1.1 5.1 Proof to Theorem 1
Proof
For the reader’s convenience, let us recall proof of Theorem 1 in [13, 41]. First of all, let us assume that there is a density \(u^{i+1}_{\gamma }\) that satisfies the BEP (17). Using \(u^{i+1}_{\gamma }\), we can construct a superposition of the Particular Solution using (12–14) and the Difference Potential using (12–13) and (16):
It can be seen that \(u^{i+1}\) defined in (64) is a solution to the following discrete system on \(N^0\):
which implies that \(u^{i+1}_{j,k,l},\;(x_i,y_j,z_k)\in M^+\) in (64) is some solution to (11) on \(M^+\), and note that the trace of \(u^{i+1}\) satisfies
from the definition of trace operator. Moreover, from our assumption on the density \(u^{i+1}_{\gamma }\), we have \(P_{\gamma }u^{i+1}_{\gamma }+G_{h,\Delta t}f^i_\gamma =u^{i+1}_{\gamma }\). Thus, \(Tr_{\gamma }u^{i+1}=u^{i+1}_{\gamma }\) and we can conclude that if some density \(u^{i+1}_{\gamma }\) satisfies the BEP (17), it is a trace to some solution of system (11).
Now assume the density \(u^{i+1}_{\gamma }\) is a trace to some solution of system (11): \(u^{i+1}_{\gamma }=Tr_{\gamma }u^{i+1}\) where \(u^{i+1}_{j,k,l}\), \((x_j,y_k,z_l)\in N^+\) is the unique solution to the difference equation (11) subject to certain boundary condition. Then by our assumption on \(u^{i+1}\), \(u^{i+1}\) with zero extension from \(N^+\) to \(N^0\) is also a solution to the system of difference equation (65) on \(N^0\). Since \(P_{N^+\gamma }u^{i+1}_{\gamma }+G_{h,\Delta t}f^i\) is also a solution the system of difference equation (65), we conclude that:
by the uniqueness argument. Finally, restriction of the \(u^{i+1}\) from \(N^+\) to the discrete grid boundary \(\gamma \) would give us
and \(u^{i+1}_{\gamma }=P_{\gamma }u^{i+1}_{\gamma }+G_{h,\Delta t}f^i_{\gamma }\), since \(u^{i+1}_{\gamma }=Tr_{\gamma }u^{i+1}\) by our assumption. In other words, if \(u^{i+1}_{\gamma }\) is a trace to some solution of system (11), it satisfies the BEP (17). \(\square \)
1.2 5.2 Proof to Proposition 1
Proof
The proof is similar to ideas in [13, 41]. Without boundary conditions, the difference equations (11) would admit infinite number of solutions and so will the BEP (17), due to Theorem 1. However, if we provide density values \(u^{i+1}_{\gamma _{ex}}\) on \(\gamma _{ex}\), the difference equation (11) will be well-posed and will admit a unique solution. Hence, the BEP (17) will have a unique solution if \(u^{i+1}_{\gamma _{ex}}\) is given. The solution to BEP (17) is uniquely determined by densities on \(\gamma _{ex}\), thus the solution \(u^{i+1}_{\gamma }\) to BEP (17) has dimension \(|\gamma _{ex}|\), which is the cardinality of set \(\gamma _{ex}\). As a result, the BEP (17) has rank \(|\gamma |-|\gamma _{ex}|=|\gamma _{in}|\).\(\square \)
1.3 5.3 Proof to Theorem 2
Proof
The proof is based on ideas in [13, 41]. First, define the grid function:
where \(P^{i+1}\) is a solution to the AP (12)–(13) on \(N^0\) with right hand side (16) using density \(u^{i+1}_{\gamma }\), \(G^{i+1}\) is a solution to the AP (12)–(13) on \(N^0\) with right hand side (14), and \(u^{i+1}_\gamma \) is extended from \(\gamma \) to \(N^0\) by zero. By the construction of \(v^{i+1}\), one can see that \(v^{i+1}\) is a solution to the following difference equation:
Thus, we conclude that \(v^{i+1}\) solves the following homogeneous difference equations on \(M^-\):
In addition, due to the construction of \(v^{i+1},P^{i+1}\) and \(G^{i+1}\), the grid function \(v^{i+1}\) satisfies the following boundary condition:
Next, observe that the BEP (17) and the reduced BEP (19) can be reformulated using grid function \(v^{i+1}\) in (69) as follows:
and
Hence, it is enough to show that (73) is equivalent to (74) to prove the equivalence between the BEP (17) and the reduced BEP (19). First, note that if (73) is true, then (74) is obviously satisfied.
Now, assume that (74) is true and let us show that (73) holds. Let us consider problem (71): \(L_{h,\Delta t}v^{i+1}=0\) on \(M^-\), subject to boundary conditions (72) and (74), since the set \(\gamma _{in}\cup (N^0\backslash M^0)\) is the boundary set for set \(M^-\). Then we have the following discrete boundary value problem:
which admits a unique zero solution: \(v^{i+1}=0\) on \(M^-\). Since \(\gamma _{ex}{\subset } M^-\), we conclude that \(v^{i+1}=0\) on \(\gamma _{ex}\), as well as on \(\gamma \equiv \gamma _{ex}\cup \gamma _{in}\), which shows that (74) implies (73).
Thus, we showed that (73) is equivalent to (74), and therefore, BEP (17) is equivalent to the reduced BEP (19). Moreover, due to Proposition 1, the reduced BEP (19) consists of only linearly independent equations. \(\square \)
Rights and permissions
About this article
Cite this article
Epshteyn, Y., Xia, Q. Efficient Numerical Algorithms Based on Difference Potentials for Chemotaxis Systems in 3D. J Sci Comput 80, 26–59 (2019). https://doi.org/10.1007/s10915-019-00928-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-019-00928-z
Keywords
- Chemotaxis models
- Convection–diffusion–reaction systems
- Finite difference
- Finite volume
- Difference potentials method
- Cartesian meshes
- Irregular geometry
- Positivity-preserving algorithms
- Spectral approximation
- Spherical harmonics
- Mesh adaptivity
- Domain decomposition
- Parallel computing