Universal AMG Accelerated Embedded Boundary Method Without Small Cell Stiffness

Abstract

We develop a universally applicable embedded boundary finite difference method, which results in a symmetric positive definite linear system and does not suffer from small cell stiffness. Our discretization is efficient for the wave, heat and Poisson equation with Dirichlet boundary conditions. When the system needs to be inverted we can use the conjugate gradient method, accelerated by algebraic multigrid techniques. A series of numerical tests for the wave, heat and Poisson equation and applications to shape optimization problems verify the accuracy, stability, and efficiency of our method. Our fast computational techniques can be extended to moving boundary problems (e.g. Stefan problem), to the Navier–Stokes equations, and to the Grad-Shafranov equations for which problems are posed on domains with complex geometry and fast simulations are of great interest.

A Proof of Lemma 2.1

For the case $n=1$ and $n=2$, the lemma can be verified through direct computations of leading principal minors. We only focus on the case $n\ge 3$.

The matrix $\mathcal {D}^{(n)}(a,b)$ is manifestly symmetric. To prove that $\mathcal {D}^{(n)}\in \mathbb {R}^{n\times n}$ is SPD, we use mathematical induction to prove that its leading principal minors are all positive. When $1\le k\le n-1$, the k-th order leading principal minor of $\mathcal {D}^{(n)}\in \mathbb {R}^{n\times n}$ is

$$\begin{aligned} Q^{(n)}_k(a) = \det \underbrace{\left( \begin{array}{llllll} a &{} -1 &{} 0 &{} \dots &{} 0 &{} 0\\ -1 &{} 2 &{}-1&{} \dots &{} 0 &{} 0\\ 0 &{} -1 &{} 2 &{} \dots &{} 0 &{} 0\\ \vdots &{} &{}\vdots &{} \vdots &{} \vdots &{} \vdots \\ 0 &{} 0 &{} 0 &{} \dots &{} 2 &{} -1\\ 0 &{} 0 &{} 0 &{} \dots &{}-1 &{} 2 \end{array}\right) }_{k\times k}, \qquad 1\le k\le n-1. \end{aligned}$$

(31)

The n-th order leading principal minor of $\mathcal {D}^{(n)}(a,b)\in \mathbb {R}^{n\times n}$ is

$$\begin{aligned} P^{(n)}(a,b) = \det \underbrace{\left( \begin{array}{llllll} a &{} -1 &{} 0 &{} \dots &{} 0 &{} 0\\ -1 &{} 2 &{}-1&{} \dots &{} 0 &{} 0\\ 0 &{} -1 &{} 2 &{} \dots &{} 0 &{} 0\\ \vdots &{} &{}\vdots &{} \vdots &{} \vdots &{} \vdots \\ 0 &{} 0 &{} 0 &{} \dots &{} 2 &{} -1\\ 0 &{} 0 &{} 0 &{} \dots &{}-1 &{} b \end{array}\right) }_{n\times n}. \end{aligned}$$

(32)

(1) We first prove that if $a>\frac{n-2}{n-1}$, then the first $n-1$ principal minors of $\mathcal {D}^{(n)}\in \mathbb {R}^{n\times n}$, namely $Q^{(n)}_k(a)$ ($1\le k\le n-1)$ are all positive.

For $n=3$, with direct computations, one can check that if $a>\frac{3-2}{3-1}=\frac{1}{2}$ then $Q^{(3)}_1(a)$ and $Q^{(3)}_2(a)$ are positive. Now, for the induction case $n-1$, we assume if $a>\frac{n-3}{n-2}$, then the first $n-2$ principal minors of $\mathcal {D}^{(n-1)}$, namely $Q^{(n-1)}_k(a)$ $(1\le k\le n-2)$, are all positive. With this induction assumption, we will prove that if $a>\frac{n-2}{n-1}$ then the first $n-1$ principal minors of $\mathcal {D}^{(n)}(a,b)$ are all positive.

The definition in (31) implies that $Q^{(n)}_k(a)=Q^{(n-1)}_k(a)$ when $1\le k\le n-2$. Moreover, if $a>\frac{n-2}{n-1}$, then $a>\frac{n-3}{n-2}$ and the induction assumption leads to

$$\begin{aligned} Q^{(n)}_k(a)=Q^{(n-1)}_k(a)>0,\; 1\le k\le n-2. \end{aligned}$$

Now, we only need to prove that $Q^{(n)}_{n-1}$ is positive:

$$\begin{aligned} Q^{(n)}_{n-1}(a)&=\det \left( \begin{array}{llllll} a &{} -1 &{} 0 &{} \dots &{} 0 &{} 0\\ -1 &{} 2 &{}-1&{} \dots &{} 0 &{} 0\\ 0 &{} -1 &{} 2 &{} \dots &{} 0 &{} 0\\ \vdots &{} &{}\vdots &{} \vdots &{} \vdots &{} \vdots \\ 0 &{} 0 &{} 0 &{} \dots &{} 2 &{} -1\\ 0 &{} 0 &{} 0 &{} \dots &{}-1 &{} 2 \end{array}\right) =\det \left( \begin{array}{llllll} a &{} -1 &{} 0 &{} \dots &{} 0 &{} 0\\ 0 &{} 2-\frac{1}{a} &{}-1&{} \dots &{} 0 &{} 0\\ 0 &{} -1 &{} 2 &{} \dots &{} 0 &{} 0\\ \vdots &{} &{}\vdots &{} \vdots &{} \vdots &{} \vdots \\ 0 &{} 0 &{} 0 &{} \dots &{} 2 &{} -1\\ 0 &{} 0 &{} 0 &{} \dots &{}-1 &{} 2 \end{array}\right) \nonumber \\&= aQ^{(n-1)}_{n-2}\left( 2-\frac{1}{a}\right) . \end{aligned}$$

(33)

Moreover, if $a>\frac{n-2}{n-1}>0$, then

$$\begin{aligned} 2-\frac{1}{a}>2-\frac{n-1}{n-2}=\frac{n-3}{n-2}, \end{aligned}$$

(34)

and together with the induction assumption for $n-1$, we have

$$\begin{aligned} Q^{(n)}_{n-1}(a)= aQ^{(n-1)}_{n-2}\left( 2-\frac{1}{a}\right) >0. \end{aligned}$$

(2) Finally, we prove if $a > \frac{(n-2)b-(n-3)}{(n-1)b-(n-2)}$ and $b>\frac{n-2}{n-1}$, the last principal minor $P^{(n)}(a,b)$ is positive. We perform an induction proof with respect to n.

For the base case, when $n=3$, $b>\frac{n-2}{n-1}=\frac{1}{2}$ and $a > \frac{(n-2)b-(n-3)}{(n-1)b-(n-2)}=\frac{b}{2b-1}$. A direct computation shows that $P^{(3)}(a,b)$ is positive. Now, we turn to the induction case, for $n-1$, assume that

$$\begin{aligned} b>\frac{n-2}{n-3}\quad \text {and}\quad a > \frac{(n-3)b-(n-4)}{(n-2)b-(n-3)} \end{aligned}$$

(35)

implies that $P^{(n-1)}(a,b)$ is positive.

We note that $P^{(n)}(a,b)$ can be related to $P^{(n-1)} \left( 2-\frac{1}{a},b\right)$ through the rules of determinants as follows:

$$\begin{aligned} P^{(n)}(a,b)&=\det \left( \begin{array}{llllll} a &{} -1 &{} 0 &{} \dots &{} 0 &{} 0\\ -1 &{} 2 &{}-1&{} \dots &{} 0 &{} 0\\ 0 &{} -1 &{} 2 &{} \dots &{} 0 &{} 0\\ \vdots &{} &{}\vdots &{} \vdots &{} \vdots &{} \vdots \\ 0 &{} 0 &{} 0 &{} \dots &{} 2 &{} -1\\ 0 &{} 0 &{} 0 &{} \dots &{}-1 &{} b \end{array}\right) =\det \left( \begin{array}{llllll} a &{} -1 &{} 0 &{} \dots &{} 0 &{} 0\\ 0 &{} 2-\frac{1}{a} &{}-1&{} \dots &{} 0 &{} 0\\ 0 &{} -1 &{} 2 &{} \dots &{} 0 &{} 0\\ \vdots &{} &{}\vdots &{} \vdots &{} \vdots &{} \vdots \\ 0 &{} 0 &{} 0 &{} \dots &{} 2 &{} -1\\ 0 &{} 0 &{} 0 &{} \dots &{}-1 &{} b \end{array}\right) \nonumber \\&= a P^{(n-1)} \left( 2-\frac{1}{a},b\right) . \end{aligned}$$

(36)

Now, we just need to verify that $a>0$ and $P^{(n-1)} \left( 2-\frac{1}{a},b\right) >0$ under the assumption that $b>\frac{n-2}{n-1}$ and $a > \frac{(n-2)b-(n-3)}{(n-1)b-(n-2)}$. As $b>\frac{n-2}{n-1}$ and $a> \frac{(n-2)b-(n-3)}{(n-1)b-(n-2)}$, we have

$$\begin{aligned}&(n-1)b-(n-2)>0,\quad (n-2)b-(n-3)\ge \frac{(n-2)^2-(n-1)(n-3)}{n-1}\frac{1}{n-1}>0,\\&0<\frac{1}{a}<\frac{(n-1)b-(n-2)}{(n-2)b-(n-3)}\quad \text {and}\quad a^*=2-\frac{1}{a}>2-\frac{(n-1)b-(n-2)}{(n-2)b-(n-3)}\\&=\frac{(n-3)b-(n-4)}{(n-2)b-(n-3)}. \end{aligned}$$

Hence, we have $b=\frac{n-2}{n-1}>\frac{n-2}{n-3}$, and $a^*>\frac{(n-3)b-(n-4)}{(n-2)b-(n-3)}$. The induction assumption for the $n-1$ case in (35) is satisfied and $P^{(n-1)} \left( 2-\frac{1}{a},b\right) =P^{(n-1)} \left( a^*,b\right) >0$.