Piecewise Constant Upwind Approximations to the Stationary Radiative Transport Equation

Abstract

We discuss piecewise constant approximations to the stationary radiative transport equation. Convergence of the proposed scheme is numerically studied with geometrically nonconformal and nonconvex polygonal meshes, and the results imply some extension of the conventional theoretical framework of the standard finite element method. An advantage of the proposed scheme in terms of reducing computational resources is also discussed in comparison with the finite difference method.

1 Introduction

In the present paper, we discuss numerical computation of the stationary radiative transport equation (RTE). RTE is a mathematical model to describe light propagation in terms of photon migration in random mediums such as biomedical tissue [11, 13], and its numerical treatment plays an essential role in the development of next-generation diagnostic methods using near-infrared light [10].

Let $\varOmega \subset \mathbb {R}^{2}$ be a convex polygonal domain, $S = \{ \xi \in \mathbb {R}^{2}\,;\, |\xi | = 1\}$ be the unit circle, and $X = \varOmega \times S$. Since the speed of light is sufficiently fast in comparison with the size of bodies, we focus on the following boundary value problem of RTE:

$$\begin{aligned} -\xi \cdot \nabla _x I(x,\xi ) - (\mu _\text {a}+\mu _\text {s}) I(x,\xi ) + \mu _\text {s}\int _{S}p(x;\xi ,\xi ') I(x,\xi ')\,d\sigma _{\xi '}&= -q(x,\xi ),&\quad&\text {in }X, \end{aligned}$$

(1a)

$$\begin{aligned} I(x,\xi )&= I_1(x,\xi ),&\quad&\text {on }\varGamma _-, \end{aligned}$$

(1b)

where $\nabla _xI = (\partial I/\partial x_1,\partial I/\partial x_2)$ and $\mathrm{d}\sigma _{\xi }$ is the curve element on S. The function $I = I(x,\xi )$ represents a particle density at a position $x \in \varOmega$ with a velocity $\xi \in S$. The boundary is decomposed into two parts:

$$ \varGamma _{\pm } = \{(x,\xi ) \in \partial \varOmega \times S \,;\, \xi \cdot n(x) \gtrless 0\}, $$

where n(x) is the outward unit normal at x to $\partial \varOmega$, and the inflow boundary condition (1b) is given on $\varGamma _{-}$. Functions $\mu _\text {a}=\mu _\text {a}(x)$ and $\mu _\text {s}=\mu _\text {s}(x)$ are called absorption and scattering coefficients, respectively, and the scattering kernel $p(x;\xi ,\xi ')$ is the conditional probability of changing velocity from $\xi '$ to $\xi$ scattered at x. The inhomogeneous term $q=q(x,\xi )$ is an internal particle source.

Even though $\varOmega$ is a two-dimensional domain, the unknown function I depends on $(x,\xi ) \in \varOmega \times S$. It means that the straightforward discretization of RTE leads a three-dimensional large-scale problem. To save computational resources, the diffusion approximation has been frequently used by introducing a new function $\varPhi (x) = \int _{S}I(x,\xi )\mathrm{d}\sigma _{\xi }$ [2, 14], which is the first mode of the Fourier series (or the spherical harmonic series in three dimensions) of $I(x,\xi )$. Since the diffusion approximation computes only $\varPhi (x)$ without the dependency on $\xi$, additional algorithms are required in order to recover directivity of light propagation. On the other hand, the Monte Carlo method is one of standard numerical procedures in biomedical studies [3, 15]. It involves relatively large statistical errors, and thus accurate and reliable numerical methods have been still under development.

Recently, the discrete ordinate discontinuous Galerkin method has been developed as an effective method [8, 9] based on regularity of the exact solution to RTE [1]. It is formulated by the discontinuous Galerkin method and the collocation method w.r.t. x and $\xi$, respectively. Its convergence was proved in [9], where they mainly focused on spatial discretization errors with sufficiently accurate discretization for $\xi$.

In this paper, we adopt the piecewise constant approximation w.r.t. both x and $\xi$ and construct another discretization scheme similar to finite volume methods, since RTE is based on a balance law of particles. We also study its convergence by numerical experiments.

Throughout the paper, the following conditions are assumed.

• 1. $\varOmega$ is a convex polygonal domain in $\mathbb {R}^2$.

• 2. $q \in L^2(X)$, $I_1 \in L^2(\varGamma _-)$.

• 3. $p \in L^\infty (\varOmega \times S\times S)$, $p \ge 0$, $p(x; \xi ,\xi ') = p(x; \xi ',\xi )$, and $\int _S p(x;\xi ,\xi ')\,d\sigma _{\xi '} = 1$, a.e. $x, \xi$.

• 4. $\mu _\text {t}= \mu _\text {s}+ \mu _\text {a}$, $\mu _\text {s}, \mu _\text {a}\in L^\infty (\varOmega )$, $\mu _\text {s}\ge 0$, and there exists a positive number $\mu _\text {a}^- \in \mathbb {R}{}$ such that $\mu _\text {a}\ge \mu _\text {a}^-$.

• 5. There exists a unique solution to RTE in $V = \left\{ f \,;\, f, \nabla _x f, \partial _\xi f \in L^2(X) \right\}$, where $\partial _\xi = \partial /\partial \theta$ is calculated by the identification $\xi =(\cos \theta ,\sin \theta )\in S$ with $\theta \in [0,2\pi )$.

We give a remark on terminology of “convergence” in the present paper. We shall discuss error behaviors with a mesh-dependent norm. Strictly speaking, “convergence” with the mesh-dependent norm is abuse since error is measured with different norms. However, we use it for clarity.

2 Piecewise Constant Upwind Approximations to RTE

In this section, we derive a discretization scheme to RTE by employing the piecewise constant approximation w.r.t. both x and $\xi$ variables.

First, we introduce some notations to describe the proposed scheme. Let $\mathscr {K}$ be a polygonal mesh of $\varOmega$, i.e., each $\kappa \in \mathscr {K}$ is a nonempty polygonal domain and

$$ \kappa ,\tau \in \mathscr {K}, \kappa \ne \tau \Rightarrow \kappa \cap \tau = \emptyset , \quad \text {and} \quad \overline{\varOmega } = \bigcup _{\kappa \in \mathscr {K}}\overline{\kappa }. $$

Subsets of $\partial {\kappa }$ for a fixed $\xi \in S$ are denoted by

$$ \partial {\kappa }_{\xi }^{\pm } = \{x \in \partial {\kappa }\,;\, \xi \cdot n_\kappa (x) \gtrless 0\}, $$

where $n_\kappa (x)$ is the outer unit normal to $\partial {\kappa }$. Define the set of adjacent elements of $\kappa \in \mathscr {K}$ as

$$ \partial \varLambda _\kappa = \{\tau \in \mathscr {K} \,;\, \tau \ne \kappa , |\partial \tau \cap \partial {\kappa }| \ne 0\}. $$

The unit circle $S = [0,2\pi )$ is split into ${\omega _1,\dotsc ,\omega _N}$ where each $\omega _n$ is identified with the open interval $(\theta _{n-1},\theta _n)\mod 2\pi$.

Let $V_h = V_h\bigl (\mathscr {K}\times \{\omega _n\}\bigr )$ be the set of $\mathscr {K} \times \{\omega _n\}$-piecewise (element-wise) constant functions, that is, the restriction of a function in $V_h$ on each $\kappa \times \omega \in \mathscr {K}\times \{\omega _n\}$ is constant. We introduce a vector space $V + V_h = \{ v + v_h \,;\, v \in V, v_h \in V_h \}$.

For $u \in V + V_h$ and $x \in \partial \kappa$, we note that the directional limits

$$ u^{\pm }(x,\xi ) = \lim _{\varepsilon \rightarrow +0} \tilde{u}(x\pm \varepsilon \xi , \xi ) $$

exist in the trace sense if $n_\kappa (x)\cdot \xi \ne 0$, where $\tilde{u}$ is the zero extension of u:

$$ {\tilde{u}}(x,\xi ) = {\left\{ \begin{array}{ll} u(x,\xi ), \quad &{} x \in \varOmega ,\\ 0, \quad &{}\text {otherwise}. \end{array}\right. } $$

Now we discretize RTE using above notations. Suppose that $I \in V$ satisfies (1a). Integration of (1a) on $\kappa \times \omega \in \mathscr {K}\times \{\omega _n\}$, and Green’s formula yield

$$\begin{aligned}&\int \limits _{\omega }\int \limits _{\partial {\kappa }\cap \varOmega } \bigl (\xi \cdot n(x)\bigr )I(x,\xi )\,\mathrm{d}\ell \,\mathrm{d}\sigma _{\xi } + \int \limits _{\varGamma _+\cap (\partial {\kappa }\times \omega )}\bigl (\xi \cdot n(x)\bigr )I(x,\xi )\,\mathrm{d}\ell \,\mathrm{d}\sigma _{\xi } \nonumber \\&\quad +\int \limits _{\kappa \times \omega }\big \{\mu _\text {t}(x) I(x,\xi ) - \mu _\text {s}(x)\int \limits _{S}p(x; \xi ,\xi ') I(x,\xi ')\,\mathrm{d}\sigma _{\xi '}\big \}\mathrm{d}x\,\mathrm{d}\sigma _{\xi } \nonumber \\&= \int \limits _{\kappa \times \omega } q(x,\xi )\,\mathrm{d}x\,\mathrm{d}\sigma _\xi + \int \limits _{\varGamma _{-}\cap (\partial \kappa \times \omega )} \bigl |\xi \cdot n(x)\bigr |I_1(x,\xi )\,\mathrm{d}\ell \,\mathrm{d}\sigma _\xi , \end{aligned}$$

(2)

where $\mathrm{d}\ell$ is the line element along $\partial {\kappa }$. We adopt the upwind approximation $I\approx I^{-}$ on $\partial \kappa$ in the first and the second terms. Further, we apply the piecewise constant approximation $I\approx I_h \in V_h$. These two approximations lead

$$\begin{aligned}&\int \limits _{\omega }\int \limits _{\partial {\kappa }\cap \varOmega } (\xi \cdot n)I_h^-(x,\xi )\,\mathrm{d}\ell \,\mathrm{d}\sigma _{\xi } + \int \limits _{\varGamma _+\cap (\partial {\kappa }\times \omega )}(\xi \cdot n)I_h^-(x,\xi )\,\mathrm{d}\ell \,\mathrm{d}\sigma _{\xi } \\&\quad +\int \limits _{\kappa \times \omega }\big \{\mu _\text {t}I_h - \mu _\text {s}\int \limits _{S}p I_h(x,\xi ')\,\mathrm{d}\sigma _{\xi '}\big \}\mathrm{d}x\,\mathrm{d}\sigma _{\xi } \\&= \int \limits _{\kappa \times \omega } q\,\mathrm{d}x\,\mathrm{d}\sigma _\xi + \int \limits _{\varGamma _{-}\cap (\partial \kappa \times \omega )} |\xi \cdot n|I_1\,\mathrm{d}\ell \,\mathrm{d}\sigma _\xi . \end{aligned}$$

Since $I_h$ is constant on each $\kappa \times \omega$, $I_h|_{\kappa \times \omega } = I_{\kappa ,\omega }$, the following numerical scheme is obtained: for any $\kappa \times \omega \in \mathscr {K}\times \{\omega _n\}$,

$$\begin{aligned}&\sum _{\tau \in \partial \varLambda _\kappa }\bigg (\int \limits _{\omega } \int \limits _{\partial \tau \cap \partial {\kappa }_{\xi }^{-}\cap \varOmega }|\xi \cdot n(x)|\,\mathrm{d}\ell \,\mathrm{d}\sigma _{\xi }\bigg )(I_{\kappa ,\omega } - I_{\tau ,\omega }) \nonumber \\&\quad + \bigg (\int \limits _{\omega } \int \limits _{\partial {\kappa }_{\xi }^-\cap \partial \varOmega }|\xi \cdot n(x)|\,\mathrm{d}\ell \,\mathrm{d}\sigma _{\xi }\bigg )I_{\kappa ,\omega } \nonumber \\&\quad + |\omega |\bigg (\int \limits _{\kappa }\mu _\text {t}(x)\,\mathrm{d}x\bigg )I_{\kappa ,\omega } - \sum _{\omega '}\bigg (\int \limits _{\kappa \times \omega _{\xi }\times \omega '_{\xi '}} \mu _\text {s}(x) p(x;\xi ,\xi ')\,\mathrm{d}x\,\mathrm{d}\sigma _{\xi }\,\mathrm{d}\sigma _{\xi '}\bigg ) I_{\kappa ,\omega '} \nonumber \\&= \int \limits _{\kappa \times \omega } q(x,\xi )\,\mathrm{d}x\,\mathrm{d}\sigma _{\xi } + \int \limits _{\varGamma _{-}\cap (\partial {\kappa }\times \omega )}|\xi \cdot n(x)| I_1(x,\xi )\,\mathrm{d}\ell \,\mathrm{d}\sigma _\xi . \end{aligned}$$

(3)

Since the scheme (3) is considered as a finite volume method, the next lemma follows directly from finite difference analysis in [7] as a generalized finite difference method.

Lemma 1

We assume that $\displaystyle \sup _{\begin{array}{c} x\in \varOmega \\ \omega \in \{\omega _n\} \end{array}}\left( |\omega |\sup _{\xi ,\xi ' \in \omega } p(x;\xi ,\xi ')\right) \le 1$. Then, there uniquely exists an elementary matrix of interexchanging rows which transforms the coefficient matrix into a strictly diagonally dominant one.

It follows from the above lemma immediately that there exists a unique solution $I_h \in V_h$ to (3). It is also a direct consequence that Gauss–Seidel iteration gives $I_h$ to the system of linear equations (3).

3 Numerical Study for Convergence of the Proposed Scheme

In this section, we exhibit some numerical experiments to verify convergence of the proposed scheme.

Let $\varOmega$ be the unit square and $\mu _\text {s}= 1$, $\mu _\text {a}= 0.001$. Similarly as an example in [9], we use the Poisson kernel

$$\begin{aligned} p(x;\xi ,\xi ') = \dfrac{1}{2\pi }\dfrac{1-g^2}{1-2g\cos (\theta -\theta ')+g^2}, \quad g=0.9, \end{aligned}$$

(4)

as the scattering kernel. The inhomogeneous term and the boundary condition are

$$\begin{aligned} q(x_1,x_2,\theta )&= 2\pi x_1 \xi _1^2 \cos (\pi x_1^2) \cos (2\pi x_2^2)\\&\quad - 4 \pi x_2 \xi _1 \xi _2 \sin (\pi x_1^2) \sin (2\pi x_2^2)\\&\quad + (\mu _\text {a}+ (1-g)\mu _\text {s}) \xi _1 \sin (\pi x_1^2) \cos (2\pi x_2^2), \end{aligned}$$

and

$$ I_1(x_1,x_2,\theta ) = {\left\{ \begin{array}{ll} 0, &{}\quad x_1 = 0~\text {or }x_1 = 1,\\ \xi _1 \sin (\pi x_1^2), &{}\quad x_2 = 0~\text {or}~x_2 = 1. \end{array}\right. } $$

This setting admits the exact solution given by

$$ I(x_1,x_2,\theta ) = \xi _1 \sin (\pi x_1^2) \cos (2\pi x_2^2). $$

Since the proposed scheme is a kind of finite volume methods, the discontinuous Galerkin techniques are applicable to prove convergence [6, 9]. Therefore, numerical error is measured in the sense of the standard $L^2(X)$ norm and a mesh-dependent norm with $\mathscr {K}_h\times \{\omega _n\}$ as

$$\begin{aligned} \left\Vert {u}\right\Vert _{h,N}^2&= \left\Vert {u}\right\Vert _{L^2(X)}^2 + \left\Vert {u^+ - u^-}\right\Vert _{L_f^2(\mathscr {E}_h^i \times S)}^2 + \left\Vert {u^-}\right\Vert _{L_f^2(\varGamma _+)}^2 + \left\Vert {u^+}\right\Vert _{L_f^2(\varGamma _-)}^2, \end{aligned}$$

where

$$\begin{aligned} \left\Vert {u}\right\Vert _{L_f^2(e\times \omega )}^2&= \int \limits _{e\times \omega } |\xi \cdot n(x)|\,u(x,\xi )^2 \,\mathrm{d}\ell \,\mathrm{d}\sigma _{\xi }, \quad e \subset \mathscr {E}_h~\text {and }\omega \subset S. \end{aligned}$$

Sets of spatial edges in $\mathscr {K}_h$ are denoted by

$$ \mathscr {E}_h = \bigcup _{\kappa \in \mathscr {K}_h} \partial {\kappa }, \quad \mathscr {E}_h^i = \mathscr {E}_h \setminus \partial \varOmega = \mathscr {E}_h \cap \varOmega . $$

It should be noted that $\left\Vert {\cdot }\right\Vert _{h,N}$ is used so as to detect jumps across edges [6], and that it can be applied to $u \in V+V_h$.

Fig. 1

Example of triangle mesh ($h\approx 0.109$) and error behaviors with triangle meshes and square meshes

Three kinds of spatial meshes are examined to discuss convergence of the proposed scheme (3). The symbol h indicates the maximum of diameters of the spatial mesh as $h = \max \bigl \{{{\,\mathrm{diam}\,}}(\kappa ) \,;\, \kappa \in \mathscr {K}_h\bigr \}$.

Example 1

(Regular Mesh). Regular triangle and square meshes are used. Equi-spaced 4N vertices are placed on $\partial \varOmega$ and $\omega _n = \bigl ((n-1)\varDelta \theta ,n\varDelta \theta \bigr )$ with $\varDelta \theta = 2\pi /N$. An example of triangle meshes is depicted in Fig. 1 (left).

The numerical results suggest that

$$ \left\Vert {I-I_h}\right\Vert _{h,N} = O(h^{1/2}) \quad \text {and}\quad \left\Vert {I-I_h}\right\Vert _{L^2(X)} = O(h). $$

Example 2

(Geometrically Nonconformal Mesh). Meshes are generated as follows: $\varOmega$ is decomposed into $N\times N$ squares, and some squares are randomly split into either rectangles, squares, or triangles (Fig. 2 left). The interval $\omega _n$ is the same as Example 1. This yields a geometrically nonconformal mesh [6], where some vertices lie on edges of other elements. Our numerical experiments show convergence rates similar to Example 1. We remark that nonconformal meshes enable us to generate graded meshes and mesh refinements without any difficulties, although they are treated as a forbidden situation [5] in theory of the finite element analysis.

Fig. 2

Example of geometrically nonconformal meshes ($h=\sqrt{2}/10 \approx 0.141$) and error behaviors

Fig. 3

Example of nonconvex polygonal meshes ($h\approx \sqrt{2}/10\approx 0.141$) and error behaviors

Example 3

(Nonconvex Mesh). Finally, we adopt nonconvex meshes, which is also discarded in the conventional theoretical framework of the finite element method since the interpolation error analysis on each element is based on the homogeneity argument [4]. Figure 3 shows an example of meshes (left) and numerical errors (right). The convergence rate of numerical errors in $\left\Vert {\cdot }\right\Vert _{h,N}$ is $O(h^{1/2})$, while that in $L^2(X)$-norm is not O(h) but $O(h^{0.7})$.

These numerical examples suggest that

$$ \left\Vert {I-I_h}\right\Vert _{h,N} = O(h^{1/2}) $$

even for geometrically nonconformal and nonconvex meshes, while mesh convexity is required to achieve convergence as

$$ \left\Vert {I-I_h}\right\Vert _{L^2(X)} = O(h). $$

4 Efficiency of Graded Meshes

One of the difficulties in numerical computation of RTE is its requirement of huge computational resources. In this section, we discuss the efficiency of the proposed scheme in comparison with the finite difference method (FDM) [7, 12] from the quantitative viewpoint.

Let $\varOmega = (-10,10)\times (0,20)$. We consider two polygonal inclusions depicted with gray in Fig. 4; vertices of the pentagon are $(-3.28,12.42)$, (2.72, 14.42), (0.72, 16.20), $(-3.50,16.44)$, $(-5.54,14.32)$ and those of the quadrilateral are $(-5.18,4.34)$, (6.08, 4.78), (7.08, 10.84), (2.42, 12.82). The coefficients are set as $\mu _\text {s}= 0.109$ and $\mu _\text {a}= 0.008$ in the inclusions, and $\mu _\text {s}= 1.09$ and $\mu _\text {a}= 0.08$ outside the inclusions. We pose $q\equiv 0$ and p as (4). Assuming light emittance from optical fiber with diameter 0.1, we set the boundary condition as

$$ I_1(x,\theta ) = {\left\{ \begin{array}{ll} \left\{ 1-\left( \dfrac{x}{r}\right) ^2\right\} ^3 \dfrac{1}{\sqrt{2\pi }\sigma } \exp \left( -\dfrac{(\theta -\pi /2)^2}{2\sigma ^2}\right) , &{}|x_1| < r~\text {and }x_2 = 0, \\ 0, &{}\text {otherwise} \end{array}\right. } $$

with $r = 0.05, \sigma = 0.2$.

Fig. 4

Polygonal inclusions filled with gray

Fig. 5

Contour lines of numerical solution of total light intensity $\varPhi _h(x_1,x_2)$ with $\varDelta x_i = 0.01$, $\varDelta \theta = 2\pi /360$

Figure 5 shows the profile of the total light intensity $\varPhi (x) = \int _{S}I(x,\xi )\,d\sigma _{\xi }$ on $\varOmega$, and Fig. 6 shows its decay along $x_1 = 0$ with $\varDelta x_1 = \varDelta x_2$ and $\varDelta \theta = 2\pi /360$. The results suggest that the numerical solution by FDM converges as $\varDelta x_i$ tends to zero. In particular, we can conclude that FDM solutions with $\varDelta x_i = 0.02$ and $\varDelta x_i = 0.01$ are reliable from the quantitative viewpoint in this example. On the other hand, the number of unknowns for $\varDelta x_i = 0.01$ and $\varDelta \theta = 2\pi /360$ is approximately 1.4 billions, which corresponds to 10GB in the double precision. The computational time is about 5.5 hours with 68 threads parallel computation (9200 iterations with Gauss–Seidel method to reduce residual less than $10^{-12}$) on XeonPhi 7250 processor. This means that for reliable computation with FDM requires huge computational resources.

Fig. 6

Decay of $\varPhi (0,x_2)$ along the line $x_1=0$, which shows that the numerical results with $\varDelta x_i = 0.02$ ($\Box$) and those with $\varDelta x_i = 0.01$ ($\bigcirc$) show good agreements

In order to reduce computational resources, we pay attention to concentration of the boundary condition $I_1$ at the origin, which corresponds to light emittance from a thin optical fiber in practical situations. It is natural to introduce a graded mesh depicted in Fig. 7 (left). We note that the mesh contains geometrically nonconformal and nonconvex polygonal elements, which are accepted by the proposed scheme (3).

Fig. 7

Example of nonconformal graded polygonal mesh ($\#\mathscr {K} = 320$) and numerical results $\varPhi (0,x_2)$ with the proposed method ($+, \triangle , \Box$) and FDM ($\varDelta x_i=0.01$, $\bigcirc$)

Figure 7 (right) illustrates decay of $\varPhi (x)$ along $x_1 = 0$ with coarse ($\#\mathscr {K} = 320$), middle ($\#\mathscr {K} = 5463$), and fine ($\#\mathscr {K} = 211933)$ graded meshes. Figure 7 demonstrates their good agreements. The number of unknowns in the fine mesh case with $\varDelta \theta = 2\pi /360$ is 76 millions, which corresponds to 582MB ($5.3\%$ of FDM) in the double precision. The computational time is about 10 minutes ($3.1\%$ of FDM, 1560 iterations with Gauss–Seidel method to reduce residual less than $10^{-12}$) on the same computational environment. From this experiments, it is clearly concluded that the proposed method is quite efficient to reduce computational resources.

5 Concluding Remarks

The proposed scheme derived from the piecewise constant upwind approximation shows two types of error convergence: O(h) with the standard $L^2$-norm and $O(h^{1/2})$ with the mesh-dependent norm even for geometrically nonconformal polygonal mesh. The difference is that the former requires convexity of meshes, while the latter holds on nonconvex meshes. A proof of convergence will be given in a subsequent paper.