TY - JOUR

T1 - A fast solver for the narrow capture and narrow escape problems in the sphere

AU - Kaye, Jason

AU - Greengard, Leslie

N1 - Funding Information:
We would like to thank Michael Ward for suggesting this problem and for several valuable insights. We would also like to thank Mike O'Neil for many useful conversations. J.K. was supported in part by the Research Training Group in Modeling and Simulation funded by the National Science Foundation via grant RTG/DMS-1646339 .

PY - 2020/1

Y1 - 2020/1

N2 - We present an efficient method to solve the narrow capture and narrow escape problems for the sphere. The narrow capture problem models the equilibrium behavior of a Brownian particle in the exterior of a sphere whose surface is reflective, except for a collection of small absorbing patches. The narrow escape problem is the dual problem: it models the behavior of a Brownian particle confined to the interior of a sphere whose surface is reflective, except for a collection of small patches through which it can escape. Mathematically, these give rise to mixed Dirichlet/Neumann boundary value problems of the Poisson equation. They are numerically challenging for two main reasons: (1) the solutions are non-smooth at Dirichlet-Neumann interfaces, and (2) they involve adaptive mesh refinement and the solution of large, ill-conditioned linear systems when the number of small patches is large. By using the Neumann Green's functions for the sphere, we recast each boundary value problem as a system of first-kind integral equations on the collection of patches. A block-diagonal preconditioner together with a multiple scattering formalism leads to a well-conditioned system of second-kind integral equations and a very efficient approach to discretization. This system is solved iteratively using GMRES. We develop a hierarchical, fast multipole method-like algorithm to accelerate each matrix-vector product. Our method is insensitive to the patch size, and the total cost scales with the number N of patches as O(NlogN), after a precomputation whose cost depends only on the patch size and not on the number or arrangement of patches. We demonstrate the method with several numerical examples, and are able to achieve highly accurate solutions with 100 000 patches in one hour on a 60-core workstation. For that case, adaptive discretization of each patch would lead to a dense linear system with about 360 million degrees of freedom. Our preconditioned system uses only 13.6 million “compressed” degrees of freedom and a few dozen GMRES iterations.

AB - We present an efficient method to solve the narrow capture and narrow escape problems for the sphere. The narrow capture problem models the equilibrium behavior of a Brownian particle in the exterior of a sphere whose surface is reflective, except for a collection of small absorbing patches. The narrow escape problem is the dual problem: it models the behavior of a Brownian particle confined to the interior of a sphere whose surface is reflective, except for a collection of small patches through which it can escape. Mathematically, these give rise to mixed Dirichlet/Neumann boundary value problems of the Poisson equation. They are numerically challenging for two main reasons: (1) the solutions are non-smooth at Dirichlet-Neumann interfaces, and (2) they involve adaptive mesh refinement and the solution of large, ill-conditioned linear systems when the number of small patches is large. By using the Neumann Green's functions for the sphere, we recast each boundary value problem as a system of first-kind integral equations on the collection of patches. A block-diagonal preconditioner together with a multiple scattering formalism leads to a well-conditioned system of second-kind integral equations and a very efficient approach to discretization. This system is solved iteratively using GMRES. We develop a hierarchical, fast multipole method-like algorithm to accelerate each matrix-vector product. Our method is insensitive to the patch size, and the total cost scales with the number N of patches as O(NlogN), after a precomputation whose cost depends only on the patch size and not on the number or arrangement of patches. We demonstrate the method with several numerical examples, and are able to achieve highly accurate solutions with 100 000 patches in one hour on a 60-core workstation. For that case, adaptive discretization of each patch would lead to a dense linear system with about 360 million degrees of freedom. Our preconditioned system uses only 13.6 million “compressed” degrees of freedom and a few dozen GMRES iterations.

KW - Fast multipole method

KW - Integral equations

KW - Mean first passage time

KW - Mixed boundary value problems

KW - Narrow capture

KW - Narrow escape

UR - http://www.scopus.com/inward/record.url?scp=85079085456&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85079085456&partnerID=8YFLogxK

U2 - 10.1016/j.jcpx.2019.100047

DO - 10.1016/j.jcpx.2019.100047

M3 - Article

AN - SCOPUS:85079085456

VL - 5

JO - Journal of Computational Physics: X

JF - Journal of Computational Physics: X

SN - 2590-0552

M1 - 100047

ER -