[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Efficient Numerical Algorithms Based on Difference Potentials for Chemotaxis Systems in 3D

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

References

  1. Adler, J.: Chemotaxis in bacteria. Annu. Rev. Biochem. 44(1), 341–356 (1975). https://doi.org/10.1146/annurev.bi.44.070175.002013

    Article  Google Scholar 

  2. 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

    Article  MathSciNet  MATH  Google Scholar 

  3. 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

    Article  MathSciNet  MATH  Google Scholar 

  4. 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

    Article  MathSciNet  MATH  Google Scholar 

  5. Bonner, J.T.: The Cellular Slime Molds, 2nd edn. Princeton University Press, Princeton (1967). https://doi.org/10.1515/9781400876884

    Book  Google Scholar 

  6. 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

    Article  Google Scholar 

  7. 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

    Article  Google Scholar 

  8. 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

    Article  MATH  Google Scholar 

  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

    Article  MathSciNet  MATH  Google Scholar 

  10. 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)

  11. 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

    Article  MathSciNet  MATH  Google Scholar 

  12. 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

    Article  Google Scholar 

  13. 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

    Article  MathSciNet  MATH  Google Scholar 

  14. 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

    Article  MathSciNet  MATH  Google Scholar 

  15. 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

    Article  MathSciNet  MATH  Google Scholar 

  16. 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

    Article  MathSciNet  MATH  Google Scholar 

  17. 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

  18. 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

    Article  MathSciNet  MATH  Google Scholar 

  19. Herrero, M.A., Velázquez, J.J.L.: A blow-up mechanism for a chemotaxis model. Ann. Scuola Norm. Super. 24, 633–683 (1997)

    MathSciNet  MATH  Google Scholar 

  20. 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

    Article  MathSciNet  MATH  Google Scholar 

  21. Horstmann, D.: From 1970 until now: the Keller–Segel model in chemotaxis and its consequences i. Jahresber. DMV 105, 103–165 (2003)

    MATH  MathSciNet  Google Scholar 

  22. Horstmann, D.: From 1970 until now: the Keller–Segel model in chemotaxis and its consequences ii. Jahresber. DMV 106, 51–69 (2004)

    MATH  Google Scholar 

  23. 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

    Article  MathSciNet  MATH  Google Scholar 

  24. 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

    Book  MATH  Google Scholar 

  25. 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

    Book  MATH  Google Scholar 

  26. 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

    Article  MathSciNet  MATH  Google Scholar 

  27. 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)

    MATH  Google Scholar 

  28. 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

    Article  MathSciNet  MATH  Google Scholar 

  29. 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

    Article  MATH  Google Scholar 

  30. 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

    Article  MathSciNet  MATH  Google Scholar 

  31. 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

    Article  MathSciNet  MATH  Google Scholar 

  32. 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

    Article  MathSciNet  MATH  Google Scholar 

  33. 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

    Article  MathSciNet  MATH  Google Scholar 

  34. 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

    Article  MathSciNet  MATH  Google Scholar 

  35. 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

    Article  MathSciNet  MATH  Google Scholar 

  36. 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

    Article  Google Scholar 

  37. 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

    Article  MathSciNet  MATH  Google Scholar 

  38. Patlak, C.S.: Random walk with persistence and external bias. Bull. Math. Biophys. 15(3), 311–338 (1953). https://doi.org/10.1007/bf02476407

    Article  MathSciNet  MATH  Google Scholar 

  39. Perthame, B.: Transport equations in biology. Front. Math. Birkhäuser Verlag (2007). https://doi.org/10.1007/978-3-7643-7842-4

    Article  MATH  Google Scholar 

  40. Prescott, L., Harley, J., Klein, D.: Microbiology, 3rd edn. Wm. C. Brown Publishers, Chicago (1996)

    Google Scholar 

  41. 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)

    Book  Google Scholar 

  42. 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

    Article  MathSciNet  MATH  Google Scholar 

  43. 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

    Article  MathSciNet  MATH  Google Scholar 

  44. 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

    Article  MathSciNet  MATH  Google Scholar 

  45. 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

    Article  MathSciNet  MATH  Google Scholar 

  46. 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

    Article  MathSciNet  MATH  Google Scholar 

  47. 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

    Article  MathSciNet  MATH  Google Scholar 

  48. 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

Download references

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

Authors

Corresponding author

Correspondence to Yekaterina Epshteyn.

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 (1214) and the Difference Potential using (1213) and (16):

$$\begin{aligned} u^{i+1}_{j,k,l}=P_{N^+\gamma }u^{i+1}_{\gamma }+G_{h,\Delta t}f^{i},\quad (x_j,y_k,z_l)\in M^0. \end{aligned}$$
(64)

It can be seen that \(u^{i+1}\) defined in (64) is a solution to the following discrete system on \(N^0\):

$$\begin{aligned} \begin{aligned} L_{h,\Delta t}u^{i+1}_{j,k,l}&=\left\{ \begin{array}{ll} f^i_{j,k,l}, &{} \quad (x_j,y_k,z_l)\in M^+,\\ L_{h,\Delta t}[u^{i+1}_{\gamma }],&{}\quad (x_j,y_k,z_l)\in M^-, \end{array} \right. \\ u^{i+1}_{j,k,l}&=0,\quad (x_j,y_k,z_l)\in N^0\backslash M^0, \end{aligned} \end{aligned}$$
(65)

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

$$\begin{aligned} Tr_{\gamma }u^{i+1}=Tr_{\gamma }\left( P_{N^+\gamma }u^{i+1}_{\gamma }+G_{h,\Delta t}f^{i}\right) =P_{\gamma }u^{i+1}_{\gamma }+G_{h,\Delta t}f^i_\gamma , \end{aligned}$$
(66)

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:

$$\begin{aligned} u^{i+1}\equiv P_{N^+\gamma }u^{i+1}_{\gamma }+G_{h,\Delta t}f^i, \quad (x_j,y_k,z_l)\in N^+, \end{aligned}$$
(67)

by the uniqueness argument. Finally, restriction of the \(u^{i+1}\) from \(N^+\) to the discrete grid boundary \(\gamma \) would give us

$$\begin{aligned} Tr_{\gamma }u^{i+1}=Tr_\gamma \left( P_{N^+\gamma }u^{i+1}_{\gamma }+G_{h,\Delta t}f^i\right) =P_{\gamma }u^{i+1}_{\gamma }+G_{h,\Delta t}f^i_{\gamma }. \end{aligned}$$
(68)

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:

$$\begin{aligned} v^{i+1}:=P^{i+1}+G^{i+1}-u^{i+1}_{\gamma },\quad \text{ on } N^0, \end{aligned}$$
(69)

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:

$$\begin{aligned} \begin{aligned} L_{h,\Delta t}[v^{i+1}]&=\left\{ \begin{array}{ll} f^i-L_{h,\Delta t}[u^{i+1}_{\gamma }],&{}\quad \text{ on } M^+,\\ 0, &{} \quad \text{ on } M^-. \end{array} \right. \end{aligned} \end{aligned}$$
(70)

Thus, we conclude that \(v^{i+1}\) solves the following homogeneous difference equations on \(M^-\):

$$\begin{aligned} L_{h,\Delta t}v^{i+1}=0,\quad \text{ on } M^-. \end{aligned}$$
(71)

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:

$$\begin{aligned} v^{i+1}=0,\quad \text{ on } N^0\backslash M^0. \end{aligned}$$
(72)

Next, observe that the BEP (17) and the reduced BEP (19) can be reformulated using grid function \(v^{i+1}\) in (69) as follows:

$$\begin{aligned} v^{i+1}=0, \quad \text{ on } \gamma , \quad (\text{ BEP } (17)), \end{aligned}$$
(73)

and

$$\begin{aligned} v^{i+1}=0, \quad \text{ on } \gamma _{in},\quad (\text{ BEP } (19)). \end{aligned}$$
(74)

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:

$$\begin{aligned} L_{h,\Delta t}v^{i+1}&=0,\quad \text{ on } M^-, \end{aligned}$$
(75)
$$\begin{aligned} v^{i+1}&=0,\quad \text{ on } N^0\backslash M^0, \end{aligned}$$
(76)
$$\begin{aligned} v^{i+1}&=0,\quad \text{ on } \gamma _{in}, \end{aligned}$$
(77)

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10915-019-00928-z

Keywords

Mathematics Subject Classification

Navigation