Fast Fourier-Galerkin Methods for Nonlinear Boundary Integral Equations

Abstract

We develop in this paper a fast Fourier-Galerkin method for solving the nonlinear integral equation which is reformulated from a class of nonlinear boundary value problems. By projecting the nonlinear term onto the approximation subspaces, we make the Fourier-Galerkin method more efficient for solving the nonlinear integral equations. A fast algorithm for solving the resulting discrete nonlinear system is designed by integrating together the techniques of matrix compressing, numerical quadrature for oscillatory integrals, and the multilevel augmentation method. We prove that the proposed method enjoys an optimal convergence order and a nearly linear computational complexity. Numerical experiments are presented to confirm the theoretical estimates and to demonstrate the efficiency and accuracy of the proposed method.

1 Introduction

We consider in this paper the Laplace equation with nonlinear boundary conditions, which serves as mathematical models for many important applications, such as acoustics, elasticity, electromagnetics, and fluid dynamics. Suppose that $D$ is a simply connected bounded domain in $\mathbb R ^2$ with a $C^2$ boundary $\Gamma .$ Specifically, we shall solve the nonlinear boundary value problem

$$\begin{aligned} \left\{ \begin{array}{ll} \Delta u(x)=0,&\quad x \in D, \\ \displaystyle {\frac{\partial u(x)}{\partial \mathbf{n}_x} = -g(x,u(x))+g_0(x)},&\quad x \in \Gamma , \end{array} \right. \end{aligned}$$

(1.1)

where $\mathbf{n}_x$ denotes the exterior unit normal to $\Gamma$ at $x.$ Throughout this paper we assume that $g(x,u)$ is continuous with respect to $x \in \Gamma$ and Lipschitz continuous with respect to $u \in \mathbb R ,$ the partial derivative $D_u g$ of $g$ with respect to the variable $u$ exists and is Lipschitz continuous, and for each $u\in C(\Gamma ),\,g(\cdot ,u(\cdot )), D_u g(\cdot ,u(\cdot ))\in C(\Gamma ).$

The boundary integral equation approach is commonly used in solving (1.1). It transforms the boundary problem into an integral equation defined on the boundary $\Gamma .$ In contrast to the Laplace equation with linear boundary conditions, the reformulation of nonlinear boundary value problem (1.1) leads to a nonlinear boundary integral equation. In the literature, various numerical methods for solving nonlinear integral equations reformulated from a broad range of boundary value problems were developed. Specifically, a degenerate kernel scheme was introduced in [13, 19]. Nyström’s method and the product integration method were discussed in [17, 22]. Projection methods, including the Galerkin scheme and the collocation scheme, were discussed in [2, 3, 6, 12, 16, 20, 21, 24–27, 29]. Recently, a series of schemes based on the projection method were proposed in [4, 7, 8]. Also, an extrapolation algorithm based on Nyström’s method was developed in [11].

In this paper, we shall develop a fast algorithm based on the Fourier-Galerkin method for solving the nonlinear boundary integral equation reformulated from (1.1). The main difficulties of the numerical solution of the integral equations are caused by the nonlinearity. Typically, solving the corresponding discrete nonlinear system by the classical Newton’s method and its variants demands a significantly large amount of computational efforts. Specifically, in each iteration step, we have to evaluate and update the Jacobian matrix in the entire approximate subspace. Moreover, the dimension of the approximate subspace is usually required to be large so that one can get good approximation accuracy.

The resulting boundary integral equation contains both linear and nonlinear components. The nonlinear component involves an integral operator with the logarithmic kernel. This will lead us to compute double singular integrals when we implement Newton’s method. As in the case of solving linear boundary integral equations [30], we decompose the integral operator into the form $\mathcal A+\mathcal B,$ where $\mathcal A$ is a singular operator carrying the main singularity characteristic of the integral operator and $\mathcal B$ is a compact operator with a smooth kernel. It is worth to point out that the singular operator $\mathcal A$ has the Fourier basis functions as its eigenfunctions. Motivated by the features of $\mathcal A$ and $\mathcal B,$ we choose the subspaces generated by the Fourier basis functions as the approximate subspaces in the Galerkin methods. Moreover, we project the nonlinear term arising in the nonlinear integral operator onto the approximate subspace. This idea was used in [7], where a collocation method was considered. By doing this, we avoid evaluating the double singular integrals which appear in the related Jacobian matrix. Instead, we only need to generate once the matrix representation of operators $\mathcal A$ and $\mathcal B$ under the Fourier basis and in each iteration step multiply the matrix representation by vectors generated by evaluating single integrals.

Since operator $\mathcal A$ has the Fourier basis functions as its eigenfunctions, the matrix representation of $\mathcal A$ is diagonal and the entries on the diagonal can be obtained directly. However, the matrix representation of operator $\mathcal B$ and the integral operator in the linear components are usually dense. Hence, generating these matrices and multiplying them by vectors will still need large computational costs. Furthermore, the multiplications of vectors and dense matrices have to be carried out in each iteration step of Newton’s method because the Jacobian matrices need to be established and updated during the iteration. To overcome these computational challenges so as to develop a fast solver for the Fourier-Galerkin method, we adopt three techniques. A matrix truncation strategy has been proposed in [5] for solving linear boundary integral equations. In the spirit of [5], the matrix representation of smooth kernels under the Fourier basis can be compressed to sparse ones. Here, we also employ the numerical quadrature scheme proposed in [15] for computing all the nonzero entries of the representation matrices. The multilevel augmentation method has been presented in [10] and developed in [7, 8] for solving nonlinear boundary integral equations. In this method, one inverts the nonlinear operator in a much smaller subspace rather than in the whole approximate subspace. It reduces the computational complexity to a nearly linear order. Combining these three techniques together, we develop a multilevel augmentation method for solving the resulting fully discrete truncated nonlinear system.

We organize this paper in four sections. In Sect. 2 we review the boundary integral equation reformulation of nonlinear boundary value problem (1.1), then we describe a Fourier-Galerkin method based on nonlinear term projection for solving the resulting nonlinear boundary integral equation. In Sect. 3 we show that the Fourier-Galerkin method enjoys the exponential convergence order if the exact solution is analytic. For the case that the exact solution has a Sobolev regularity, we develop in Sect. 4 a fully discrete fast Fourier-Galerkin method by employing a matrix truncation strategy, a quadrature formula for oscillatory integrals, and the multilevel augmentation method. To show the proposed method is a fast and efficient solver, we establish optimal estimates of its computational complexity and its convergence order. Moreover, we present numerical examples to show the computational efficiency and the approximate accuracy of the proposed method.

2 The Fourier-Galerkin Method for Nonlinear Boundary Integral Equation

In this section, we describe the Fourier-Galerkin method for solving the nonlinear boundary integral equation reformulated from the nonlinear boundary value problem (1.1).

We begin with reviewing the boundary integral equation reformulation. Following [2, 24], solving (1.1) leads to the following nonlinear integral equation defined on $\Gamma$

$$\begin{aligned} u(x)-\frac{1}{\pi }\int \limits _{\Gamma }u(y)\frac{\partial }{\partial \mathbf n _y}\log |x-y|d s_y \, - \, \frac{1}{\pi }\int \limits _{\Gamma }g(y,u(y))\log |x-y|d s_y\nonumber \\ =\, - \, \frac{1}{\pi }\int \limits _{\Gamma }g_0(y)\log |x-y|d s_y, \ \ x\in \Gamma . \end{aligned}$$

(2.1)

Making use of the solution of Eq. (2.1) and the boundary condition in (1.1), we can obtain the value of $u$ at $x\in D$ by the following formula

$$\begin{aligned} u(x)=\frac{1}{2\pi }\int \limits _{\Gamma }u(y)\frac{\partial }{\partial \mathbf n _y}\left(\log |x-y|\right)d s_y-\frac{1}{2\pi }\int \limits _{\Gamma }\frac{\partial u(y)}{\partial \mathbf n _y}\log |x-y|d s_y. \end{aligned}$$

From this viewpoint, in this paper, we aim at solving the nonlinear boundary integral equation (2.1) numerically. Suppose that the boundary $\Gamma$ has a parametrization

$$\begin{aligned} x(t)= (\xi (t),\eta (t)), \quad \ t \in I:=[0,2\pi ]. \end{aligned}$$

Let $\mathbb Z$ be the set of all integers. We define three kernels at $t, \tau \in I$ as

$$\begin{aligned} K(t,\tau ):= \left\{ \begin{array}{ll} \displaystyle \frac{1}{\pi } \frac{\eta ^{\prime }(\tau )(\xi (\tau )-\xi (t))-\xi ^{\prime }(\tau )(\eta (\tau )-\eta (t))}{(\xi (\tau )-\xi (t))^2 +(\eta (\tau )-\eta (t))^2},&\quad t-\tau \ne 2k\pi , k\in \mathbb Z ,\\ \displaystyle \frac{1}{\pi } \frac{\eta ^{\prime }(t) \xi ^{\prime \prime }(t) - \xi ^{\prime }(t) \eta ^{\prime \prime }(t)}{2(\xi ^{\prime }(t)^2+\eta ^{\prime }(t)^2)},&\quad \ \text{ otherwise}, \end{array} \right. \end{aligned}$$

$$\begin{aligned} A(t,\tau ):=-\frac{1}{\pi }\log \left|2 \text{ e}^{-1/2}\sin \frac{t-\tau }{2}\right|, \end{aligned}$$

and

$$\begin{aligned} B(t,\tau ):= \left\{ \begin{array}{ll} -\frac{1}{\pi }\log \left|\frac{\text{ e}^{1/2}\sqrt{(\xi (t)-\xi (\tau ))^2+(\eta (t)-\eta (\tau ))^2}}{2\sin \frac{t-\tau }{2}}\right|,&\quad t - \tau \ne 2k\pi , k\in \mathbb Z ,\\ -\frac{1}{\pi }\log \left|\text{ e}^{1/2}\sqrt{\xi ^{\prime }(\tau )^2+\eta ^{\prime }(\tau )^2}\right|,&\quad \text{ otherwise}. \end{array} \right. \end{aligned}$$

We also introduce functions

$$\begin{aligned} u(t):=u\left(x(t) \right), g\left(t,u(t) \right):=g\left(x(t),u(x(t)) \right),\ g_0(t):=g_0\left(x(t) \right), \quad \ t\in I. \end{aligned}$$

With these notations, Eq. (2.1) can now be rewritten as

$$\begin{aligned} u(t)-\int \limits _{I}K(t,\tau )u(\tau )d\tau&+ \int _{I}A(t,\tau )g(\tau ,u(\tau ))|x^{\prime }(\tau )|d\tau +\int \limits _{I} B(t,\tau )g(\tau ,u(\tau ))|x^{\prime }(\tau )|d\tau \nonumber \\&= \int \limits _{I}A(t,\tau )g_0(\tau )|x^{\prime }(\tau )|d\tau +\int \limits _{I}B(t,\tau )g_0(\tau )|x^{\prime }(\tau )|d\tau , \quad \ t \in I. \nonumber \\ \end{aligned}$$

(2.2)

We next represent Eq. (2.2) in an operator form. To this end, we introduce three linear integral operators defined, respectively, by

$$\begin{aligned} (\mathcal{K}u)(t):= \int \limits _{I}K(t,\tau ) u(\tau ) d\tau , \quad t \in I, \end{aligned}$$

and

$$\begin{aligned} (\mathcal{A}u)(t) := \int \limits _{I}A(t,\tau ) u(\tau ) d\tau , \quad (\mathcal{B }u)(t) := \int \limits _{I}B(t,\tau ) u(\tau ) d\tau , \quad t \in I, \end{aligned}$$

and define a nonlinear operator by

$$\begin{aligned} (\Psi u)(t) := g\left(t,u(t) \right)|x^{\prime }(t)|, \quad \ \ t\in I. \end{aligned}$$

With these operators, Eq. (2.2) is represented as the operator equation

$$\begin{aligned} u-\left(\mathcal{K} - \mathcal{A}\Psi -\mathcal{B}\Psi \right)u=f, \end{aligned}$$

(2.3)

where $f:=(\mathcal{A}+\mathcal{B})(g_0 \sqrt{\xi ^{\prime 2}+\eta ^{\prime 2}}).$

We observe from the definition of the kernels that $K$ is of $C^{s-2}$ and $B$ is of $C^{s-1}$ when the boundary $\Gamma$ is of $C^s, s\ge 2.$ By the smoothness of the two kernels, we have that the operators $\mathcal K$ and $\mathcal B$ are both compact operators. The operator $\mathcal A$ has weak singularity and it has trigonometric monomials as its eigenfunctions, that is, there holds

$$\begin{aligned} \mathcal{A}: \text{ e}^{ikt}\rightarrow \frac{1}{\max \{1,|k|\}}\text{ e}^{ikt},\quad \ k\in \mathbb Z . \end{aligned}$$

We note that the sum $\mathcal{A}+\mathcal{B}$ is the boundary integral operator with logarithmic kernel, which has weak singularity. In particular, $\mathcal A$ carries the main singularity characteristic of the boundary integral operator and $\mathcal B$ is a compact operator with a smooth kernel. This decomposition has two advantages. One is that $\mathcal A$ has good properties that its matrix representation under some basis can be calculated with less efforts. For instance, in [8], the entries of the matrix representation of $\mathcal A$ under the multi-scale wavelet basis can be calculated exactly by explicit formulas. In our case, since operator $\mathcal A$ has the Fourier basis functions as its eigenfunctions, its matrix representation under the Fourier basis is diagonal and the entries on the diagonal can also be obtained exactly. The other is that the matrix representation of the compact operator $\mathcal B$ under the same basis can be compressed to a sparse matrix without loss of critical information encoded in the matrix.

Taking advantages of the operator decomposition, we will establish the Galerkin method using the Fourier basis for solving operator equation (2.3). Let $\mathbb N$ denote the set of all positive integers and set $\mathbb N _{0}:=\mathbb N \cup \{0\}.$ To enumerate finite sets, we also introduce index sets $\mathbb Z _n^{+}:=\{1,2,\cdots ,n-1\}$ and $\mathbb Z _n:=\mathbb Z _n^+\cup \{0\}.$ For any $k\in \mathbb Z ,$ for $x\in I$ we set

$$\begin{aligned} \text{ e}_k(x):=\left\{ \begin{array}{ll} \frac{1}{\sqrt{\pi }}\cos kx,&\quad k\in \mathbb N , \\ \frac{1}{\sqrt{2\pi }},&\quad k=0, \\ \frac{1}{\sqrt{\pi }}\sin (-kx),&\quad k\in \mathbb Z \setminus \mathbb N _0. \end{array} \right. \end{aligned}$$

For each $n\in \mathbb N ,$ we define a finite dimensional subspace $\mathbb X _n$ by

$$\begin{aligned} \mathbb X _n:=\text{ span}\{\text{ e}_k: |k|\in \mathbb Z _n\}. \end{aligned}$$

Let $\mathcal{P}_n$ be the orthogonal projection operator from $L^2(I)$ to $\mathbb X _n.$ The Fourier-Galerkin method for solving Eq. (2.3) is to seek $u_n$ in $\mathbb X _n$ such that

$$\begin{aligned} u_n - \mathcal{P}_n \left(\mathcal{K}-\mathcal{A} \Psi -\mathcal{B} \Psi \right) u_n = \mathcal{P }_n f. \end{aligned}$$

(2.4)

The following theorem gives the unique solvability of Eq. (2.4), which can be proved by making use of Theorem 2 of [27, 28].

Theorem 2.1

Suppose that $u\in L^2(I)$ is an isolated solution of (2.3) and $1$ is not an eigenvalue of the linear operator $\mathcal{K}-((\mathcal{A}+\mathcal{B}) \Psi )^{\prime }(u).$ Then for sufficiently large $n,$ Eq. (2.4) has a unique solution $u_n\in B(u,\delta )$ for some $\delta >0$ and there exist positive constants $c_1$ and $c_2$ such that

$$\begin{aligned} c_1||u-\mathcal{P}_nu||\le ||u-u_n||\le c_2||u-\mathcal{P}_nu||. \end{aligned}$$

To describe the regular property of the solution and then estimate the convergence order of the Fourier-Galerkin method, we introduce appropriate Sobolev spaces. For each $\mu \ge 0,$ we denote by $H^\mu (I)$ the Sobolev space of functions $\phi \in L^2(I)$ with the property

$$\begin{aligned} \sum _{k\in \mathbb Z }\left(1+k^2 \right)^\mu |\phi _k|^2<\infty , \end{aligned}$$

where $\phi _k$ is the $k$th Fourier coefficient of $\phi$ defined by $\phi _k:=\int _I\phi (x)e_k(x)dx.$ The inner product of the Sobolev space $H^\mu (I)$ is defined for $\phi ,\psi \in H^\mu (I)$ by

$$\begin{aligned} \left\langle \phi ,\psi \right\rangle _\mu :=\sum _{k\in \mathbb Z }\left(1+k^2 \right)^\mu \phi _k\overline{\psi _k}, \end{aligned}$$

and its norm is defined by $||\phi ||_\mu :=\langle \phi ,\phi \rangle _\mu ^{\frac{1}{2}}.$ It is well-known [1, 18] that there exists a positive constant $c$ such that for any $v\in H^{\mu }(I),$

$$\begin{aligned} ||v-\mathcal{P}_nv||\le cn^{-\mu }||v||_{\mu }. \end{aligned}$$

(2.5)

The following corollary is a direct result of Theorem 2.1 and estimation (2.5).

Corollary 2.2

If the solution $u\in H^{\mu }(I), \mu \ge 0,$ there exists a constant $c>0$ such that

$$\begin{aligned} ||u-u_n||\le cn^{-\mu }||u||_{\mu }. \end{aligned}$$

Based upon the Fourier basis of the subspace $\mathbb X _n,$ the Fourier-Galerkin method (2.4) is equivalent to a system of nonlinear equations. Specifically, it suffices to seek a function $u_n\in \mathbb X _n$ with the form

$$\begin{aligned} u_n(t)=\sum _{|l|\in \mathbb Z _n}a_l\text{ e}_l(t), \quad \ t\in I, \end{aligned}$$

which satisfies the nonlinear system

$$\begin{aligned} \left\langle u_n -\left(\mathcal{K}-\mathcal{A}\Psi -\mathcal{B}\Psi \right) u_n, \text{ e}_k \right\rangle =\left\langle f, \text{ e}_k \right\rangle , \quad \ |k|\in \mathbb Z _n. \end{aligned}$$

(2.6)

Newton’s method is a standard iterative method for solving nonlinear system (2.6). However, at each iteration step of this method we have to establish and invert the Jacobian matrix, which is usually dense and has the size of $(2n-1)\times (2n-1).$ Moreover, each entry of the Jacobian matrix is of the form

$$\begin{aligned} \left\langle \text{ e}_l, \text{ e}_k \right\rangle - \left\langle \mathcal{K}\text{ e}_l, \text{ e}_k \right\rangle + \left\langle \left(\mathcal{A}+\mathcal{B} \right)\Psi ^{\prime } \left(u_n^{(m)} \right)\text{ e}_l,\text{ e}_k \right\rangle ,\quad \ \ \ |k|,|l|\in \mathbb Z _n, \end{aligned}$$

(2.7)

which involves double integrals. Hence, solving (2.6) by Newton’s method demands a large amount of computational efforts.

To develop a fast algorithm for solving (2.6), we first need to consider the computation of the Jacobian matrix. We observe from (2.7) that the first term need not be evaluated because of the orthogonality of $e_k$’s. For the second term, we need to compute it only once during the iteration. In addition, we will point out later that the quantities $\langle \mathcal{K }\text{ e}_l, \text{ e}_k\rangle , |k|,|l|\in \mathbb Z _n,$ can be evaluated efficiently by compressing the matrix representation of operator $\mathcal K.$ In fact, it is the third item that involves the nonlinear operator and carries the main computational difficulties. Motivated by the operator decomposition and the fact that the Fourier basis functions are the eigenfunctions of operator $\mathcal{A},$ we consider overcoming the difficulties of evaluating the third term by projecting the nonlinear terms $\Psi ^{\prime }(u_n^{(m)})$ into the subspace $\mathbb X _n.$ By doing so, we will transform the computation of double singular integrals into setting up the matrix representations of $\mathcal A$ and $\mathcal B$ and the multiplication of matrices and vectors.

To implement the above idea, we do not solve (2.4) directly and instead, we consider solving the following equation

$$\begin{aligned} \hat{u}_n - \mathcal{P}_n \left(\mathcal{K}-\mathcal{A} \mathcal{P}_n\Psi -\mathcal{B }\mathcal{P}_n \Psi \right)\hat{u}_n = \mathcal{P}_n f \end{aligned}$$

(2.8)

for a solution

$$\begin{aligned} \hat{u}_n:=\sum _{|l|\in \mathbb Z _n}\hat{a}_l \text{ e}_l\in \mathbb X _n. \end{aligned}$$

By proofs similar to those of Theorem 2.1 and Corollary 2.2, we obtain in the following theorem regarding the existence and the error estimation of the solution of Eq. (2.8).

Theorem 2.3

Suppose that $u\in L^2(I)$ is an isolated solution of (2.3) and $1$ is not an eigenvalue of the linear operator $\mathcal{K}-((\mathcal{A}+\mathcal{B}) \Psi )^{\prime }(u).$ Then for sufficiently large $n,$ Eq. (2.8) has a unique solution $\hat{u}_n\in B(u,\delta )$ for some $\delta >0$ and there exists a constant $c>0$ such that

$$\begin{aligned} ||u-\hat{u}_n||\le c||u-\mathcal{P}_nu||. \end{aligned}$$

Furthermore, if the solution $u\in H^{\mu }(I), \mu \ge 0,$ then there exists a constant $c>0$ such that

$$\begin{aligned} ||u-\hat{u}_n||\le cn^{-\mu }||u||_{\mu }. \end{aligned}$$

In the rest of this section, we establish a matrix form of the nonlinear equation (2.8) and then describe Newton’s method for solving the resulting nonlinear system, from which one will see the advantages of introducing the projection operator. In terms of the Fourier basis of $\mathbb X _n,$ Eq. (2.8) is equivalent to the nonlinear system

$$\begin{aligned} \left\langle \hat{u}_n -\left(\mathcal{K}-\mathcal{A} \mathcal{P}_n \Psi -\mathcal{B}\mathcal{P }_n \Psi \right)\hat{u}_n, \text{ e}_k \right\rangle = \left\langle f, \text{ e}_k \right\rangle , \quad \ |k|\in \mathbb Z _n. \end{aligned}$$

(2.9)

In order to rewrite (2.9) in a matrix form, we begin with describing the matrix representation of the operators appearing in (2.9) under the Fourier basis. In this paper, we write $\mathbf v =[v_k,v_{-k}:k\in \mathbb Z _n^{+}]$ to denote the vector $\mathbf v =[v_1,v_{-1},\ldots , v_{n-1},v_{-(n-1)}]$ and $\mathbf v =[v_k,v_{-k}:k\in \mathbb Z _n]$ to denote the vector $\mathbf v =[v_0,v_1,v_{-1},\ldots , v_{n-1},v_{-(n-1)}].$ For each $|k|,|l|\in \mathbb Z _n,$ we let

$$\begin{aligned} K_{k,l}:=\int \limits _I\int \limits _I K(t,\tau ) \text{ e}_k(t) \text{ e}_l(\tau )dtd\tau \end{aligned}$$

and introduce $2\times 2$ matrix

$$\begin{aligned} \mathbf K _{k,l}:= \left[ \begin{array}{cc} K_{k,l}&K_{k,-l}\\ K_{-k, l}&K_{-k,-l} \end{array} \right]. \end{aligned}$$

By defining the matrix blocks

$$\begin{aligned}&\mathbf K :=\left[\mathbf K _{k, l}: k,l \in \mathbb Z _n^+ \right], \ \ \mathbf {K}^{\prime } : =\left[K_{0,0} \right], \ \ \mathbf {K}^{\prime \prime } :=\left[K_{0,k},K_{0,-k}: k\in \mathbb Z _n^+ \right], \ \ \\&\mathbf {K}^{\prime \prime \prime } :=\left[K_{k,0},K_{-k,0}: k\in \mathbb Z _n^+ \right]^T, \end{aligned}$$

the matrix representation of operator $\mathcal K$ can be written as

$$\begin{aligned} \mathbf{K}_n=\left[ \begin{array}{cc} \mathbf {K}^{\prime }&\mathbf {K}^{\prime \prime } \\ \mathbf {K}^{\prime \prime \prime }&\mathbf K \end{array}\right]. \end{aligned}$$

Likewise, the matrix representation of operators $\mathcal A$ and $\mathcal B$ can be described by replacing the kernel $K$ by $A$ and $B,$ respectively. Since for each $k\in \mathbb Z ,\,\text{ e}_k$ is an eigenfunction of the operator $\mathcal{A},$ the matrix $\mathbf{A}_n$ is diagonal. Specifically, there holds

$$\begin{aligned} \mathbf{A}_n:=\text{ diag}\left(1,1,1,\frac{1}{2},\frac{1}{2}, \ldots ,\frac{1}{n-1},\frac{1}{n-1}\right). \end{aligned}$$

It follows that

$$\begin{aligned} \mathcal{P}_n\Psi \hat{u}_n(t)=\sum _{|k|\in \mathbb Z _n}\hat{b}_k \text{ e}_k(t), \quad t\in I, \end{aligned}$$

where $\hat{b}_k:=\langle \Psi \hat{ u}_n, \text{ e}_k\rangle ,\ |k|\in \mathbb Z _n.$ Associated with $\hat{u}_n=\sum _{|l|\in \mathbb Z _n}\hat{a}_l \text{ e}_l$ we introduce two vectors

$$\begin{aligned} \hat{\mathbf{u }}_n:=\left[\hat{a}_k,\hat{a}_{-k}:k\in \mathbb Z _n \right]^T\ \text{ and}\ \hat{\mathbf{v }}_n:=\left[\hat{b}_k,\hat{b}_{-k}:k\in \mathbb Z _n \right]^T. \end{aligned}$$

We note that each $\hat{b}_k$ is a nonlinear function of $2n-1$ variables $\hat{a}_l,|l|\in \mathbb Z _n.$ For each $|k|\in \mathbb Z _n,$ we set

$$\begin{aligned} f_k:=\left\langle f,\text{ e}_k \right\rangle \ \text{ and}\ \mathbf f _n:=\left[f_k,f_{-k}:k\in \mathbb Z _n \right]^T. \end{aligned}$$

Let $\mathbf E _n$ denote the identity matrix which has the same order as matrix $\mathbf K _n.$ By using the matrix and vector notation, we have the equivalent matrix form of (2.9)

$$\begin{aligned} \left(\mathbf E _n-\mathbf K _n \right)\hat{\mathbf{u }}_n+\left(\mathbf A _n+\mathbf B _n \right) \hat{\mathbf{v }}_n=\mathbf f _n. \end{aligned}$$

(2.10)

For solving Eq. (2.10), we describe the classic Newton’s method in the following algorithm. For any $u\in L^2(I)$ and each $k,l\in \mathbb Z ,$ we let $\psi _{k,l}(u):=\langle \Psi ^{\prime }(u)\text{ e}_{k}, \text{ e}_{l}\rangle .$

Algorithm 1: The Newton Iteration Scheme

Set $m:=0,\,\mathbf{f}_{n} := [ \langle f,\text{ e}_{k}\rangle ,\langle f,\text{ e}_{-k}\rangle : k \in \mathbb Z _n ]^T$ and choose an initial guess $\hat{\mathbf{u}}_{n}^{(0)}$ and an iteration stopping threshold $\delta .$

• Step 1: Let $\hat{u}_{n}^{(m)} := \sum _{|k|\in \mathbb Z _n} (\hat{\mathbf{u}}_{n}^{(m)})_{k}e_{k}.$ Compute $2\times 2$ matrices

  $$\begin{aligned} F_{k,l}:= \left[ \begin{array}{cc} \psi _{k,l}\left(\hat{u}_{n}^{(m)} \right)&\psi _{k,-l}\left(\hat{u}_{n}^{(m)} \right)\\ \psi _{-k,l}\left(\hat{u}_{n}^{(m)} \right)&\psi _{-k,-l}\left(\hat{u}_{n}^{(m)} \right) \end{array} \right], \quad \ k,l \in \mathbb Z _n^+, \end{aligned}$$

  and vectors ${F}^{\prime }: =[\psi _{0,0}(\hat{u}_{n}^{(m)})]$ and

  $$\begin{aligned}&{F}^{\prime \prime }:=\left[\psi _{0,k}\left(\hat{u}_{n}^{(m)} \right),\psi _{0,-k}\left(\hat{u}_{n}^{(m)} \right): k\in \mathbb Z _n^+ \right], \ \ \\&{F}^{\prime \prime \prime }:=\left[\psi _{k,0}\left(\hat{u}_{n}^{(m)} \right), \psi _{-k,0}\left(\hat{u}_{n}^{(m)} \right): k\in \mathbb Z _n^+ \right]^T. \end{aligned}$$

  Set

  $$\begin{aligned} F_1:=\left[F_{k,l}: k,l \in \mathbb Z _n^+ \right],\ \mathbf F _{n}^{(m)}:=\left[ \begin{array}{cc} {F}^{\prime }&{F}^{\prime \prime }\\ {F}^{\prime \prime \prime }&F_1 \end{array}\right] \end{aligned}$$

  and compute the Jacobian matrix

  $$\begin{aligned} \mathbf{J}\left(\hat{\mathbf{u }}_{n}^{(m)} \right) := \mathbf{E}_{n} - {\mathbf{K}}_{n}+ \left(\mathbf{A}_{n} +{\mathbf{B}}_{n} \right) \mathbf F _{n}^{(m)}. \end{aligned}$$

• Step 2: Compute

  $$\begin{aligned} \hat{\mathbf{v }}_{n}^{(m)}:= \left[ \left\langle \Psi \left(\hat{u}_{{n}}^{(m)} \right),\text{ e}_{k} \right\rangle , \left\langle \Psi \left(\hat{u}_{n}^{(m)} \right),\text{ e}_{-k} \right\rangle : k \in \mathbb Z _n\right]^T \end{aligned}$$

  and

  $$\begin{aligned} \mathbf{F}(\hat{\mathbf{u}}_{n}^{(m)}) := (\mathbf{E}_{n} - {\mathbf{K}}_{n}) \hat{\mathbf{u}}_{n}^{(m)} + (\mathbf{A}_{n} +{\mathbf{B}}_{n}) \hat{\mathbf{v }}_{n}^{(m)}-\mathbf{f}_{n}. \end{aligned}$$

• Step 3: Solve $\mathbf{\Delta }_{n}^{(m)}$ from $\mathbf{J}(\hat{\mathbf{u}}_{n}^{(m)}) \mathbf{\Delta }_{n}^{(m)} = - \mathbf{F}(\hat{\mathbf{u}}_{n}^{(m)})$ and compute $\hat{\mathbf{u}}_{n}^{(m+1)} := \hat{\mathbf{u}}_{n}^{(m)} + \mathbf{\Delta }_{n}^{(m)}.$

• Step 4: Set $m \leftarrow m+1$ and go back to Step 1 until $|| \mathbf{\Delta }_{n}^{(m)} ||_\infty < \delta .$

We observe from Algorithm 1 that through introducing the projection on the nonlinear term $\Psi (u_n),$ we reduce the difficulties of computing the Jacobian matrices $\mathbf{J}(\hat{\mathbf{u}}_{n}^{(m)})$ and $\mathbf{F}(\hat{\mathbf{u}}_{n}^{(m)})$ in each iteration step of Newton’s method. In fact, instead of computing double integrals involved in the entries of $\mathbf{J}(\hat{\mathbf{u}}_{n}^{(m)})$ and $\mathbf{F}(\hat{\mathbf{u}}_{n}^{(m)})$ in each iteration step, we only need to set up the matrices $\mathbf{K }_{n},\mathbf{A }_{n}$ and $\mathbf{B }_{n}$ once, evaluate the single integrals $\langle \Psi ^{\prime }(\hat{u}_{{n}}^{(m)})\text{ e}_{k}, \text{ e}_{l}\rangle$ and $\langle \Psi (\hat{u}_{{n}}^{(m)}),\text{ e}_{k}\rangle , |k|,|l|\in \mathbb Z _n$ and then compute the multiplications of matrices and vectors. Especially for the operator $\mathcal A,$ we even avoid calculating the double singular integrals because of the eigenfunctions property of $\mathcal{A }.$

In spite of this, we still face large computational costs for solving nonlinear system (2.10) by Algorithm 1. Although matrix $\mathbf A _n$ is diagonal and its entries on the diagonal are known, we still have to treat matrices $\mathbf{K}_n$ and $\mathbf{B}_n.$ By the smoothness of the kernel functions $K$ and $B,$ matrices $\mathbf K _n$ and $\mathbf B _n$ are usually dense. The density will lead to large computational costs for setting up the matrices and in each iteration step, computing the multiplications of the matrices and some vectors. Moreover, since the Jacobian matrix $\mathbf{J}(\hat{\mathbf{u}}_{n}^{(m)})$ and $\mathbf{F}(\hat{\mathbf{u}}_{n}^{(m)})$ need to be updated during the iteration, the generating of vectors and the multiplications of vectors and dense matrices have to be carried out in each iteration step. All these demand the availability of a fast solver for the nonlinear system (2.10).

3 Exponential Convergence Order for Analytic Solutions

We consider fast solutions of the nonlinear system (2.10) on two cases according to the regularity of the exact solution of (2.3). We discuss in this section the case of periodic analytic solutions and postpone the case of solutions with general regularity to the next section.

It is known [1, 18] that the projection error of a periodic analytic function decays exponentially. That is, for a periodic analytic function $v,$ there exist positive constants $c$ and $s$ such that

$$\begin{aligned} ||v-\mathcal{P}_nv||\le c\text{ e}^{-sn}. \end{aligned}$$

(3.1)

This together with the error estimate given in Theorem 2.3 leads to the following result about the convergence property of the approximate solution of (2.8):

Corollary 3.1

If the solution $u$ is a periodic analytic function, there exist positive constants $c$ and $s$ such that

$$\begin{aligned} ||u-\hat{u}_n||\le c \text{ e}^{-sn}. \end{aligned}$$

The above corollary shows that the Fourier-Galerkin method (2.8) enjoys the exponential convergence order if the exact solution of the boundary integral equation is analytic. Therefore, for this special case, there is no need to develop a fast solver for the Fourier-Galerkin method, since for a small $n$ the approximate solution $\hat{u}_n$ will get enough accuracy.

To close this section, we present a numerical example for the case of periodic analytic solutions to illustrate the exponential convergence of the approximate solution of (2.8).

All computer programs for the numerical experiments presented in this paper are run on a personal computer with 2.8G CPU and 8G memory.

Example 3.2

We consider solving the nonlinear boundary integral equations (2.2) reformulated from the boundary value problem (1.1) in an elliptical region

$$\begin{aligned} D:x_1^2+\frac{x_{2}^{2}}{4}<1. \end{aligned}$$

Utilizing the parametrization of the boundary $\Gamma$ as $x(t)=(\cos t, 2\sin t),t\in I,$ we establish the boundary integral equation (2.2) with the kernel functions $K, A$ and $B$ defined respectively by

$$\begin{aligned} K(t,\tau )=\frac{1}{2\pi }\frac{2}{\displaystyle {\sin ^2\frac{t+\tau }{2}+4\cos ^2\frac{t+\tau }{2}}} \end{aligned}$$

and

$$\begin{aligned}&A(t,\tau )=-\frac{1}{\pi }\log \left|2\text{ e}^{-1/2}\sin \frac{t-\tau }{2}\right|, \ \ \\&B(t,\tau )=-\frac{1}{2\pi }\left[1+\log \left(\sin ^2\frac{t+\tau }{2}+4\cos ^2\frac{t+\tau }{2}\right)\right]. \end{aligned}$$

We assume that the nonlinear function $g$ is with the form $g(t,u(t)):=u(t)+\sin (u(t))$ and choose $g_0$ so that the function

$$\begin{aligned} u(t)=\text{ e}^{\cos (t)}\cos (2\sin (t)), \quad \ \ t\in I, \end{aligned}$$

is the exact solution of (2.2). Here, we note that the solution $u$ is analytic.

In this example, the integral equation is solved directly by Algorithm 1. We report the numerical results in Table 1. The second column in Table 1 lists the dimensions of the approximate subspaces. We present the relative error “Err” of the approximate solution in the third column, which is computed by $\text{ Err}:=\frac{||u-\hat{u}_{n}||}{||u||}.$ We observe from the numerical results that the approximation error decays quite fast so that for $n=16$ the approximate solution $\hat{u}_n$ has already got enough accuracy. Hence, we need not to consider a fast solver for the Fourier-Galerkin method.

Table 1 Numerical results of Algorithm 1 for analytic solutions

4 Fast Fully Discrete Fourier-Galerkin Method

We know from Theorem 2.3 that if $u\in H^{\mu }(I), \mu \ge 0,$ the approximation error of $\hat{u}_n$ can not decay as fast as the error in the case of analytic solutions. Hence, in this section when the exact solution has a general regularity, we develop a fast solver for the nonlinear system (2.10) which requires only nearly linear number of multiplications to implement it. This will be done by implementing three approximation techniques. They include a matrix truncation strategy, a quadrature formula for oscillatory integrals, and the multilevel augmentation method. We then show theoretically and numerically that the use of these approximation techniques does not ruin the convergence order of the conventional Fourier-Galerkin method.

4.1 A Fast Solver for the Nonlinear System

To develop a fast algorithm, we first compress the matrices $\mathbf{K}_n$ and $\mathbf{B}_n$ to sparse ones by using the matrix truncation strategy proposed in [5]. For each $n\in \mathbb N ,$ we introduce the index set

$$\begin{aligned} \mathbb L _n:=\{ [k,l]\in \mathbb Z _n^2:kl\le n\}, \end{aligned}$$

which will be used to compress the matrices. Specifically, we define the truncation matrix of $\mathbf{K}_n$ by setting

$$\begin{aligned} \widetilde{\mathbf{K }}_{k,l}:=\left\{ \begin{array}{cc} \mathbf K _{k,l}, \quad&[k,l]\in \mathbb L _n\cap (\mathbb Z _n^+)^2,\\ {0}_{2\times 2},&\quad \text{ otherwise}, \end{array} \right. \quad \ \ \widetilde{\mathbf{K }}:=[\widetilde{\mathbf{K }}_{k,l}: k,l\in \mathbb Z _n^+] \end{aligned}$$

and letting

$$\begin{aligned} \widetilde{\mathbf{K}}_n:=\left[ \begin{array}{cc} \mathbf {K}^{\prime }&\mathbf {K}^{\prime \prime } \\ \mathbf {K}^{\prime \prime \prime }&\widetilde{\mathbf{K }} \end{array}\right]. \end{aligned}$$

In the same way, we also define the truncation matrix of $\mathbf{B}_n.$ Clearly, the matrices $\widetilde{\mathbf{K}}_n$ and $\widetilde{\mathbf{B}}_n$ are sparse. In Eq. (2.10), we replace the dense matrices $\mathbf{K}_n$ and $\mathbf{B}_n$ by $\widetilde{\mathbf{K}}_n$ and $\widetilde{\mathbf{B}}_n,$ respectively. We then obtain the truncated nonlinear system

$$\begin{aligned} (\mathbf E _n-\widetilde{\mathbf{K }}_n)\tilde{\mathbf{u }}_n+(\mathbf A _n+\widetilde{\mathbf{B }}_n) \tilde{\mathbf{v }}_n=\mathbf f _n, \end{aligned}$$

(4.1)

where $\tilde{\mathbf{u }}_n:=[\tilde{a}_k,\tilde{a}_{-k}:k\in \mathbb Z _n]^T$ is the corresponding solution to be determined and $\tilde{\mathbf{v }}_n:=[\tilde{b}_k,\tilde{b}_{-k}:k\in \mathbb Z _n]^T$ with

$$\begin{aligned} \tilde{b}_k:=\left\langle \Psi \left(\sum _{|l|\in \mathbb Z _n}\tilde{a}_l \text{ e}_l(t)\right), \text{ e}_k \right\rangle . \end{aligned}$$

Before solving numerically the truncated nonlinear system (4.1), we are required to efficiently evaluate the nonzero entries of matrices $\widetilde{\mathbf{K}}_{n}$ and $\widetilde{\mathbf{B}}_{n},$ defined by the integrals

$$\begin{aligned}&K_{k,l}:=\int \limits _I\int \limits _I K(t,\tau )\text{ e}_k(t)\text{ e}_l(\tau )dtd\tau ,\ \ \ \nonumber \\&B_{k,l}:=\int \limits _I\int \limits _I B(t,\tau )\text{ e}_k(t)\text{ e}_l(\tau )dtd\tau , \ \ \ |k|,|l|\in \mathbb L _n. \end{aligned}$$

(4.2)

It is clear that we have to compute the oscillatory integrals when $k\gg 1$ or $l\gg 1.$ An efficient quadrature formula for dealing with the integrals in (4.2) was developed in [14] by using the notion of the refinable set which was initiated in [9]. Following [9, 14], we first construct multi-scale piecewise Lagrange interpolations of kernel functions $K$ and $B$ on sparse grids. The multi-scale piecewise Lagrange interpolation requires the interpolation points used in the current scale contain those used in the previous scale. To this end, we need the notion of the refinable set. We introduce two contractive mappings from $\mathbb R$ to $\mathbb R$ by

$$\begin{aligned} \varphi _0(x):=\frac{x}{2},\ \ \varphi _1(x):=\frac{x+2\pi }{2}, \quad x\in I, \end{aligned}$$

and set $\Phi :=\{\varphi _\varrho :\varrho \in \mathbb Z _2\}.$ It is clear that $I$ is the invariant set related to the mappings $\Phi .$ A subset $V$ of $I$ is called a refinable set relative to the mappings $\Phi$ if $V\subseteq \Phi (V).$

To establish the multi-scale piecewise Lagrange interpolation formula, we need to construct the Lagrange polynomials on $I.$ For $m\in \mathbb N ,$ we assume that $V:=\{v_r:0<v_0<v_1<\cdots <v_{m-1}<2\pi ,r\in \mathbb Z _m\}$ is refinable relative to $\Phi .$ These points will be used to construct the Lagrange interpolation polynomial of the initial scale. The set $\Phi ^j(V)$ is used to generate the interpolation points of for the Lagrange interpolation polynomials of scale $j.$ Specifically, for any $N\in \mathbb N$ and $\mathbf p _N:=[\varrho _\gamma :\gamma \in \mathbb Z _N]\in \mathbb Z _2^N,$ we let

$$\begin{aligned} \varphi _\mathbf{p _N}:=\varphi _{\varrho _{N-1}}\circ \cdots \circ \varphi _{\varrho _{0}}\ \text{ and} \ \mu (\mathbf p _N):=\sum _{\gamma \in \mathbb Z _N} \varrho _\gamma 2^\gamma . \end{aligned}$$

For any $N\in \mathbb N$ and $r\in \mathbb Z _{2^Nm},$ we define $v_{N,r}:=\varphi _\mathbf{p _N}(v_{r^{\prime }}),$ where $\mathbf p _{N}\in \mathbb Z _2^N$ and $r^{\prime }\in \mathbb Z _m$ satisfy $r=m\mu (\mathbf p _N)+r^{\prime }.$ For any $r\in \mathbb Z _m,$ we also let $v_{0,r}:=v_r.$ We set $V_N:=\{v_{N,r}, r\in \mathbb Z _{2^Nm}\}, N\in \mathbb N _0,$ and accordingly define the Lagrange polynomials of degree $m-1$ on $I$ by

$$\begin{aligned} l_{0,r}(x):=\prod _{q=0,q\ne r}^{m-1}\frac{x-v_{0,q}}{v_{0,r}-v_{0,q}},\quad \ \ x\in I \ \ \text{ and}\ \ r\in \mathbb Z _m, \end{aligned}$$

and

$$\begin{aligned} l_{N,r}(x):=\left\{ \begin{array}{ll} \displaystyle {\prod _{q=m\mu (\mathbf p _N),q\ne r}^{m\mu (\mathbf p _N)+m-1}\frac{x-v_{N,q}}{v_{N,r}-v_{N,q}}},&\quad x\in \varphi _\mathbf{p _N}(I),\\ 0,&\quad x\in I\setminus \varphi _\mathbf{p _N}(I), \end{array} \right. \quad N\ge 1 \ \ \text{ and} \ \ r\in \mathbb Z _{2^Nm}, \end{aligned}$$

where $\mathbf p _N\in \mathbb Z _2^N$ and $r^{\prime }\in \mathbb Z _m$ satisfy $r=m\mu (\mathbf p _N)+r^{\prime }.$ We also need to define some useful linear functionals on $C(I).$ For any $r\in \mathbb Z _m$ and $\kappa \in \mathbb Z _{2m},$ let $a_{r,\kappa }:=l_{0,r}(v_{1,\kappa }).$ We define linear functionals $\eta _{j,r}, j\in \mathbb N _0, r\in \mathbb Z _{2^jm},$ by

$$\begin{aligned}&\eta _{0,r}(f):=f(v_{0,r}), \ \ \\&\eta _{j,r}(f):=f(v_{j,r})-\sum _{q\in \mathbb Z _m}f(v_{j-1,m\lfloor \frac{r}{2m}\rfloor +q})a_{q,r\ \text{ mod}\ 2m}, \quad \ \text{ for} \text{ all}\ f\in C(I). \end{aligned}$$

Here, we denote by $\lfloor x\rfloor$ the largest integer not greater than $x.$

Making use of the Lagrange polynomials and the linear functionals defined above, we now describe the multi-scale piecewise Lagrange interpolation of kernel function $K$ on sparse grids. We define index sets $\mathbb W _0:=\mathbb Z _m$ and for any $N\in \mathbb N ,\,\mathbb W _N:=\{r\in \mathbb Z _{2^Nm}:v_{N,r}\in V_N\setminus V_{N-1}\}.$ For any $\mathbf j :=[j_0,j_1]\in \mathbb N _0^2,$ we let $\mathbb W _\mathbf j :=\mathbb W _{j_0}\otimes \mathbb W _{j_1},$ and for any $\mathbf j :=[j_0,j_1]\in \mathbb N _0^2$ and $\mathbf r :=[r_0,r_1]\in \mathbb W _\mathbf j ,$ we set

$$\begin{aligned} \eta _\mathbf{j ,\mathbf r }:=\eta _{j_0,r_0}\otimes \eta _{j_1,r_1} \;\ \text{ and}\;\ l_\mathbf{j ,\mathbf r }:=l_{j_0,r_0}\otimes l_{j_1,r_1}. \end{aligned}$$

For any $N\in \mathbb N ,$ we introduce the index set by

$$\begin{aligned} \mathbb S _N:= \{ \mathbf j :=[j_0,j_1]\in \mathbb Z _{N+1}^2:\max \{ j_0,1\}+\max \{ j_1,1\}\le N\}. \end{aligned}$$

With these notations, we get the multi-scale piecewise Lagrange interpolation of $K$ on sparse grids

$$\begin{aligned} \mathcal S _NK=\sum _\mathbf{j \in \mathbb S _N}\sum _\mathbf{r \in \mathbb W _\mathbf j }\eta _\mathbf{j ,\mathbf r }(K)l_\mathbf{j ,\mathbf r }, \quad N\in \mathbb N . \end{aligned}$$

Replacing $K$ by $\mathcal S _NK$ in the second term of (4.2), we establish a numerical quadrature formula for evaluating the coefficients $K_{k,l},|k|,|l|\in \mathbb L _n,$ as

$$\begin{aligned} \tilde{K}_{k,l}:=\sum _\mathbf{j \in \mathbb S _N}\sum _\mathbf{r \in \mathbb W _\mathbf j }\eta _\mathbf{j , \mathbf r }(K)K_\mathbf{j ,\mathbf r }(k,l), \end{aligned}$$

(4.3)

where for any $\mathbf j \in \mathbb S _N,\mathbf r \in \mathbb W _\mathbf j$ and $|k|,|l|\in \mathbb L _n,\,$

$$\begin{aligned} K_\mathbf{j ,\mathbf r }(k,l):=\int \limits _I\int \limits _Il_\mathbf{j ,\mathbf r }(t,\tau )\text{ e}_k(t)\text{ e}_l(\tau )dtd\tau . \end{aligned}$$

We note that by rewriting (4.3) in the form of discrete Fourier transforms of matrices $[\eta _\mathbf{j , \mathbf r }(K):\mathbf r \in \mathbb W _\mathbf j ],\mathbf j \in \mathbb S _N,$ and then employing the well-known fast Fourier transform, we can design a fast quadrature algorithm for computing $\tilde{K}_{k,l}, |k|,|l|\in \mathbb L _n.$ For a detailed description of the algorithm, the readers are referred to Appendix in [15]. We denote by $\widetilde{\mathbf{K }}_{n,N}$ the matrix $\widetilde{\mathbf{K }}_{n}$ with $K_{k,l}$ being evaluated by the quadrature formula (4.3), where ${N}$ is the number of partition level of the multiscale Lagrange interpolation for kernel $K.$ Likewise, we also define matrix $\widetilde{\mathbf{B }}_{n,N}.$ We thus obtain a fully discrete truncated nonlinear system

$$\begin{aligned} \left(\mathbf E _n-\widetilde{\mathbf{K }}_{n,N} \right)\widetilde{\mathbf{u }}_{n,N}+\left(\mathbf A _n+ \widetilde{\mathbf{B }}_{n,N} \right)\widetilde{\mathbf{v }}_{n,N}=\mathbf f _n. \end{aligned}$$

(4.4)

We next consider solving Eq. (4.4) by the multilevel augmentation method. The key idea of the multilevel augmentation method is to solve the nonlinear system by inverting the nonlinear operator in a subspace of a much lower dimension with a compensation of high frequency by matrix–vector multiplications. To apply this idea to Eq. (4.4), we assume that $n:=2^{k+m},\,k,m\in \mathbb N ,$ where $k$ is fixed and denotes the initial level of approximation, and we split the matrices in this equation into “low frequency” and “high frequency” components. Specifically, we write the matrix $\widetilde{\mathbf{K }}_{n,N}$ in the block form

$$\begin{aligned} \widetilde{\mathbf{K }}_{n,N}=\left[ \begin{array}{cccc} \overline{K}_{00}&\overline{K}_{01}&\cdots&\overline{K}_{0m}\\ \overline{K}_{10}&\overline{K}_{11}&\cdots&\overline{K}_{1m}\\ \cdots&\cdots&\cdots&\cdots \\ \overline{K}_{m0}&\overline{K}_{m1}&\cdots&\overline{K}_{mm} \end{array}\right], \end{aligned}$$

where $\overline{K}_{00}$ has order $(2^{k+1}-1)\times (2^{k+1}-1),\,\overline{K}_{0q}$ has order $(2^{k+1}-1)\times 2^{k+q},\,\overline{K}_{q0}$ has order $2^{k+q}\times (2^{k+1}-1)$ for $q=1,2,\ldots ,m$ and $\overline{K}_{pq}$ has order $2^{k+p}\times 2^{k+q}$ for $p,q=1,2,\ldots ,m.$ For each $l=0,1,\ldots ,m,$ we denote by $\widetilde{\mathbf{K }}_{k,l,N}$ the submatrix of $\widetilde{\mathbf{K }}_{n,N}$ that has the form

$$\begin{aligned} \widetilde{\mathbf{K }}_{k,l,N}=\left[ \begin{array}{cccc} \overline{K}_{00}&\overline{K}_{01}&\cdots&\overline{K}_{0l}\\ \overline{K}_{10}&\overline{K}_{11}&\cdots&\overline{K}_{1l}\\ \cdots&\cdots&\cdots&\cdots \\ \overline{K}_{l0}&\overline{K}_{l1}&\cdots&\overline{K}_{ll} \end{array}\right], \end{aligned}$$

and split $\widetilde{\mathbf{K }}_{k,l,N}$ into its “low frequency” and “high frequency” components:

$$\begin{aligned} \widetilde{\mathbf{K }}_{k,l,N}^L=\left[ \begin{array}{cccc} \overline{K}_{00}&\overline{K}_{01}&\cdots&\overline{K}_{0l} \end{array}\right]\ \ \text{ and}\ \ \widetilde{\mathbf{K }}_{k,l,N}^H=\left[ \begin{array}{cccc} \overline{K}_{10}&\overline{K}_{11}&\cdots&\overline{K}_{1l}\\ \cdots&\cdots&\cdots&\cdots \\ \overline{K}_{l0}&\overline{K}_{l1}&\cdots&\overline{K}_{ll} \end{array}\right]. \end{aligned}$$

By the same way, we also introduce the submatrices and corresponding “low frequency” components and “high frequency” components for matrices $\mathbf{E}_{n}, \mathbf{A}_{n}$ and $\widetilde{\mathbf{B }}_{n,N}.$ In the light of the idea of the multilevel augmentation methods, we establish the following fast algorithm.

Algorithm 2: The Fast Multilevel Augmentation Method

Let $k$ be a fixed positive integer. Set $\mathbf{f}_{2^{k+m}} := [ \langle f,\text{ e}_{j}\rangle ,\langle f,\text{ e}_{-j}\rangle : j \in \mathbb Z _{2^{k+m}} ]^T.$

• Step 1: According to Algorithm 1, solve the nonlinear system

  $$\begin{aligned} (\mathbf E _{2^k}-\widetilde{\mathbf{K }}_{k,0,N})\mathbf u _{k,0,N}+ (\mathbf A _{2^k}+\widetilde{\mathbf{B }}_{k,0,N})\mathbf v _{k,0,N} =\mathbf f _{2^k}, \end{aligned}$$

  for the solution $\mathbf u _{k,0,N}=[(\mathbf u _{k,0,N})_j,(\mathbf u _{k,0,N})_{-j}:j\in \mathbb Z _{2^k}]^T,$ where

  $$\begin{aligned} \mathbf v _{k,0,N}:=\left[\left\langle \Psi \left(u_{k,0,N}\right),\text{ e}_j \right\rangle , \left\langle \Psi \left(u_{k,0,N} \right),\text{ e}_{-j} \right\rangle :j\in \mathbb Z _{2^k} \right]^T \end{aligned}$$

  and $u_{k,0,N}:=\sum _{|j|\in \mathbb Z _{2^k}}(\mathbf u _{k,0,N})_{j}\text{ e}_j.$ Set $l:=1.$

• Step 2: Set $\mathbf{f}_{{k,l}}:=[\langle f, \text{ e}_j\rangle ,\langle f, \text{ e}_{-j}\rangle : j\in \mathbb Z _{2^{k+l}}\setminus \mathbb Z _{2^{k}}]^T.$

  • Compute $\hat{\mathbf{v }}_{k,l,N}=\left[\left\langle \Psi \left(u_{k,l-1,N} \right), \text{ e}_j \right\rangle , \left\langle \Psi \left(u_{k,l-1,N} \right), \text{ e}_{-j} \right\rangle :j\in \mathbb Z _{2^{k+l}} \right]^T.$

  • Augment the matrices $\widetilde{\mathbf{K }}_{k,l-1,N}^H, \mathbf A _{k,l-1}^H$ and $\widetilde{\mathbf{B }}_{k,l-1,N}^H$ to form $\widetilde{\mathbf{K }}_{k,l,N}^H, \mathbf A _{k,l}^H$ and $\widetilde{\mathbf{B }}_{k,l,N}^H,$ respectively.

  • Augment the vector $\mathbf u _{k,l-1,N}$ by setting $\hat{\mathbf{u }}_{k,l,N}=\left[\begin{array}{c} \mathbf u _{k,l-1,N}\\ \mathbf 0 _{2^{k+l}\times 1} \end{array}\right].$

  • Compute

    $$\begin{aligned} \mathbf u _{k,l,N}^{H}:=\mathbf{f}_{{k,l}}+ \tilde{\mathbf{K}}_{{k,l,N}}^H \hat{\mathbf{u }}_{k,l,N} -\left(\mathbf A _{{k,l}}^H+\tilde{\mathbf{B}}_{{k,l,N}}^H \right)\hat{ \mathbf{v}}_{k,l,N}. \end{aligned}$$

    (4.5)

    Let $u_{k,l,N}^{H}:=\sum _{|j| \in \mathbb Z _{2^{k+l}}\backslash \mathbb Z _{2^k}} \left(\mathbf{u}_{k,l,N}^{H} \right)_{j} \text{ e}_j.$

• Step 3: Augment the matrices $\widetilde{\mathbf{K }}_{k,l-1,N}^L, \mathbf A _{k,l-1}^L$ and $\widetilde{\mathbf{B }}_{k,l-1,N}^L$ to form $\widetilde{\mathbf{K }}_{k,l,N}^L, \mathbf A _{k,l}^L$ and $\widetilde{\mathbf{B }}_{k,l,N}^L,$ respectively. According to Algorithm 1, solve the nonlinear system

  $$\begin{aligned} \left(\mathbf{E}^L_{{k,l}}-\widetilde{\mathbf{K}}^L_{k,l,N} \right)\left[\begin{array}{c} \mathbf{u}^L_{k,l,N}\\ \mathbf{u}^H_{k,l,N} \end{array}\right]+ \left(\mathbf{A}^L_{k,l}+\widetilde{\mathbf{B}}^L_{k,l,N} \right)\overline{\mathbf{v}}_{k,l,N}=\mathbf f _{2^k} \end{aligned}$$

  (4.6)

  for the solution $\mathbf{u}^L_{k,l,N}=[(\mathbf{u}^L_{k,l,N})_j,(\mathbf{u}^L_{k,l,N})_{-j}:j\in \mathbb Z _{2^{k}}]^T,$ where

  $$\begin{aligned} \overline{\mathbf{v}}_{k,l,N}:=\left[\left\langle \Psi \left(u^L_{k,l,N}+u_{k,l,N}^H \right), \text{ e}_{j} \right\rangle , \left\langle \Psi \left(u^L_{k,l,N}+u_{k,l,N}^H \right), \text{ e}_{-j} \right\rangle :j\in \mathbb Z _{2^{k+l}} \right]^T \end{aligned}$$

  and $u_{k,l,N}^L:=\sum _{|j|\in \mathbb Z _{2^k}}(\mathbf{u}^L_{k,l,N})_j \text{ e}_{j}.$ Define $\mathbf{u}_{k,l,N}:=\left[\begin{array}{c} \mathbf{u}^L_{k,l,N}\\ \mathbf{u}^H_{k,l,N} \end{array}\right]$ and $u_{k,l,N}:=u_{k,l,N}^L + u_{k,l,N}^H.$

• Step 4: Set $l \leftarrow l+1$ and go back to Step 2 until $l=m.$

We remark that in Algorithm 2, we use the fast Fourier transform to evaluate the vectors $\overline{\mathbf{v}}_{k,l,N}$ and $\hat{\mathbf{v }}_{k,l,N}.$ The output $\mathbf{u}_{k,m,N}$ of Algorithm 2 is regarded as an approximate solution of the nonlinear system (4.4). The next theorem gives an estimation of the computational cost required for Algorithm 2, which shows that the fully discrete Fourier-Galerkin method developed in this section is indeed a fast algorithm.

Theorem 4.1

If for each $(t,\tau )\in I^2,$ the number of multiplications used to evaluate $K(t,\tau )$ and $B(t,\tau )$ is constant, then the total number of multiplications required for obtaining $\mathbf{u}_{k,m,N}$ in Algorithm 2 is $\mathcal{O}((k+m)^3 2^{k+m}).$

Proof

The total number of multiplications required for obtaining $\mathbf{u}_{k,m,N}$ is composed of two parts. One involves the multiplication for generating the sparse matrices $\widetilde{\mathbf{K}}_{2^{k+m},N}$ and $\widetilde{\mathbf{B}}_{2^{k+m},N}.$ The other is that for carrying out the computing steps listed in Algorithm 2.

According to Theorem A.3 of Appendix in [15], the number of multiplications for generating ${\widetilde{\mathbf{K}}}_{2^{k+m},N}$ and ${\widetilde{\mathbf{B}}}_{2^{k+m},N}$ is $\mathcal{O}((k+m)^3 2^{k+m}).$ To carry out the computing steps listed in Algorithm 2, we need to compute only once of step 1 and update for $l=0,1,2,\ldots ,m$ in steps 2 and 3. The computational cost of step 1, used to provide an initial approximate solution, can be considered as a constant. In step 2, the number of multiplications used for computing $\hat{\mathbf{v }}_{k,l,N}$ by using the fast Fourier transform is $\mathcal{O}((k+l)2^{k+l}).$ An estimation of the numbers of nonzero entries of the truncated matrices $\tilde{\mathbf{K}}_{{k,l,N}}^H$ and $\tilde{\mathbf{B}}_{{k,l,N}}^H$ has been given in [5], that is, they are $\mathcal{O}((k+l)2^{k+l}).$ As a result, the number of multiplications in the matrix-vector multiplication is also $\mathcal{O }((k+l)2^{k+l}).$ In each iteration step of Newton’s method for solving (4.6), the number of multiplications for evaluating the Jacobian matrix can be obtained as $\mathcal{O }((k+l)2^{k+l})$ by a similar analysis used in step 2. Since the nonlinear system (4.6) has the same size as (4.1), we consider the computational cost for inverting the Jacobian matrix as a constant. So the total number of multiplications in step 3 is $\mathcal{O}((k+l)2^{k+l})$ since the number of iteration steps is finite.

Adding up the above estimates together, we get the desired result of this theorem. $\square$

4.2 Convergence Analysis

The convergence order of the approximate solution obtained by Algorithm 2 can be estimated by a similar analysis used in [7, 8] for estimating the multilevel augmentation method for the multiscale collocation method.

We first represent Algorithm 2 in an operator form. For $n:=2^{k+m}$ and $N:=k+m,$ we let $\mathcal{K}_{n}:=\mathcal{P}_{n}\mathcal{K}|_\mathbb{X _{n}}$ and $\tilde{\mathcal{K}}_{n,N}: \mathbb X _n\rightarrow \mathbb X _n$ be the linear operator such that its matrix representation under the Fourier basis is ${\tilde{\mathbf{K }}_{n,N}}.$ For each $l\in \mathbb Z _{m+1},$ we denote by $\tilde{\mathcal{K}}_{k,l,N}$ the linear operator from $\mathbb X _{2^{k+l}}$ to $\mathbb X _{2^{k+l}},$ which has $\tilde{\mathbf{K }}_{k,l,N}$ as its matrix representation. Similarly, we also define the operators $\mathcal{B}_{n}, \tilde{\mathcal{B}}_{n,N}$ and $\tilde{\mathcal{B}}_{k,l,N}$ and $\mathcal{A}_{k,l}, l\in \mathbb Z _{m+1}.$ For each $l\in \mathbb Z _{m+1},$ we split the operator $\tilde{\mathcal{K}}_{k,l,N}$ into its “lower frequency” and “higher frequency” components by letting

$$\begin{aligned} \widetilde{\mathcal{K}}^L_{k,l,N}:=\mathcal{P}_{2^k}\widetilde{\mathcal{K }}_{k,l,N}\mathcal{P}_{2^{k+l}},\quad \widetilde{\mathcal{K }}^H_{k,l,N}:=\left(\mathcal{P}_{2^{k+l}}-\mathcal{P}_{2^k} \right)\widetilde{\mathcal{K }}_{k,l,N}\mathcal{P}_{2^{k+l}}. \end{aligned}$$

It is clear that the matrices $\widetilde{\mathbf{K }}_{k,l,N}^L$ and $\widetilde{\mathbf{K }}_{k,l,N}^H$ are exactly the matrix representation of the operators $\widetilde{\mathcal{K}}^L_{k,l,N}$ and $\widetilde{\mathcal{K}}^H_{k,l,N},$ respectively. Likewise, by replacing $\widetilde{\mathcal{K}}_{k,l,N}$ with $\widetilde{\mathcal{B }}_{k,l,N}$ and $\mathcal{A}_{k,l},$ we also introduce $\widetilde{\mathcal{B}}_{k,l,N}^L, \widetilde{\mathcal{B}}_{k,l,N}^H, \mathcal{A}^L_{k,l}$ and $\mathcal{A}^H_{k,l}.$ We point out that for each $l\in \mathbb Z _{m+1},$ Eq. (4.5) is equivalent to

$$\begin{aligned} u_{k,l,N}^H = \left(\mathcal{P}_{2^{k+l}}-\mathcal{P}_{2^k} \right) f + \left[\tilde{\mathcal{K }}_{{k,l},N}^H - \left(\mathcal{A}_{k,l}^H+\tilde{\mathcal{B}}_{{k,l},N}^H \right)\mathcal{P }_{2^{k+l}} \Psi \right] u_{k,l-1,N}, \end{aligned}$$

and nonlinear system (4.6) is equivalent to

$$\begin{aligned} \left[\mathcal{P}_{2^k} - \tilde{\mathcal{K}}_{k,l,N}^L+ \left(\mathcal{A }_{k,l}^L+\tilde{\mathcal{B}}_{k,l,N}^L \right)\mathcal{P}_{2^{k+l}} \Psi \right] \left(u_{k,l,N}^L+u_{k,l,N}^H \right) = \mathcal{P}_{2^k} f. \end{aligned}$$

Moreover, it can be verified that the approximate solution $u_{k,l,N}, l\in \mathbb Z _{m+1},$ satisfy the nonlinear operator equations

$$\begin{aligned}&\left[\mathcal{I}-\tilde{\mathcal{K}}_{k,l,N}^L+\left(\mathcal{A}_{k,l}^L+\tilde{\mathcal{B }}_{k,l,N}^L \right)\mathcal{P}_{2^{k+l}} \Psi \right] u_{k,l,N}=\mathcal P _{2^{k+l}}f+ \tilde{\mathcal{K}}^H_{k,l,N}u_{k,l-1,N}\nonumber \\&\qquad -\left(\mathcal{A}_{k,l}^H+\tilde{\mathcal{B}}_{k,l,N}^H \right)\mathcal{P}_{2^{k+l}} \Psi u_{k,l-1,N},\ l\in \mathbb Z _{m+1}. \end{aligned}$$

(4.7)

We shall need to estimate the differences between $\mathcal{K}_{n}$ and $\tilde{\mathcal{K}}_{n,N}$ and also between $\mathcal{B}_{n}$ and $\tilde{\mathcal{B}}_{n,N}.$ To this end, we introduce two appropriate spaces of functions. For any $\alpha :=[\alpha _0,\alpha _1]\in \mathbb N _0^2,$ let $|\alpha |_\infty :=\max \{\alpha _0, \alpha _1\}$ and $|\alpha |:=|\alpha _0|+|\alpha _1|.$ For a function $f\in C^\sigma (I^2)$ and for $\alpha :=[\alpha _0,\alpha _1]\in \mathbb N _0^2,$ we write

$$\begin{aligned} f^{(\alpha )}(\mathbf x ):=\left(\frac{\partial ^{|\alpha |}}{\partial x^{\alpha _0}\partial y^{\alpha _1}}f\right)(\mathbf x ),\ \mathbf x :=[x,y]\in I^2 \end{aligned}$$

and define the space

$$\begin{aligned} X^\sigma (I^2):=\left\{ f:I^2\rightarrow \mathbb R : f^{(\alpha )}\in C(I^2), |\alpha |_\infty \le \sigma \right\} . \end{aligned}$$

For $\mu \ge 0,$ we also define the space $H^{\mu }(I^2)$ of functions $\phi \in L^2(I^2)$ whose Fourier coefficients $\{\phi _{k,l}:k,l\in \mathbb Z \}$ satisfy

$$\begin{aligned} \sum _{k\in \mathbb Z }\sum _{l\in \mathbb Z }\left(1+k^2 \right)^{\mu }\left(1+l^2 \right)^{\mu }|\phi _{k,l}|^2<\infty . \end{aligned}$$

According to Lemma 3.3 in [15], we have the desired result for the difference between $\mathcal{K}_{n}$ and $\tilde{\mathcal{K}}_{n,N}$ in the following lemma.

Lemma 4.2

If $N:=\lceil \log _2 n\rceil$ and $K\in X^\sigma (I^2)\cap H^{\mu }(I^2)$ with $\sigma \ge \mu +1/2+\epsilon , \mu \ge 0, \epsilon >0,$ then there exist a positive constant $c$ and $n_0\in \mathbb N$ such that for all $n\in \mathbb N$ with $n\ge n_0$ and for all $w\in L^2(I),$

$$\begin{aligned} || (\mathcal{K}_{n} - \tilde{\mathcal{K}}_{n,N}) \mathcal{P}_nw ||\le c|| w ||{n}^{-\mu }. \end{aligned}$$

(4.8)

For the difference between operators $\mathcal{B}_{n}$ and $\tilde{\mathcal{B }}_{n,N},$ we also have a similar estimate.

Lemma 4.3

If $N:=\lceil \log _2 n\rceil$ and $B\in X^\sigma (I^2)\cap H^{\mu }(I^2)$ with $\sigma \ge \mu +1/2+\epsilon , \mu \ge 0, \epsilon >0,$ then there exist a positive constant $c$ and $n_0\in \mathbb N$ such that for all $n\in \mathbb N$ with $n\ge n_0$ and for all $w\in L^2(I),$

$$\begin{aligned} || (\mathcal{B}_{n} - \tilde{\mathcal{B}}_{n,N}) \mathcal{P}_n \Psi w || \le c || w ||{n}^{-\mu }. \end{aligned}$$

(4.9)

Proof

By an estimate similar to that presented in Lemma 4.2, there exist a positive constant $c_1$ and $n_0\in \mathbb N$ such that for all $n\in \mathbb N$ with $n\ge n_0$ and for all $w\in L^2(I)$

$$\begin{aligned} || (\mathcal{B}_{n} - \tilde{\mathcal{B}}_{n,N}) \mathcal{P}_n \Psi w || \le c_1 || \Psi w ||{n}^{-\mu }. \end{aligned}$$

(4.10)

Since $g$ is continuously differentiable with respect to the second variable, it follows from the standard estimate for nonlinear operator (see, for Example, [23]) that there exists a positive constant $c_2$ such that for all $w\in L^2(I)$

$$\begin{aligned} || \Psi w || \le c_2 || w ||. \end{aligned}$$

(4.11)

Combining (4.11) and (4.10), we obtain that

$$\begin{aligned} || (\mathcal{B}_{n} - \tilde{\mathcal{B}}_{n,N}) \mathcal{P}_n \Psi w || \le c_1c_2 || w ||{n}^{-\mu }, \end{aligned}$$

which prove the estimation (4.9) by letting $c:=c_1c_2.$ $\square$

By making use of Lemmas 4.2 and 4.3, we estimate in the following theorem the error of the approximate solution generated by Algorithm 2.

Theorem 4.4

If kernel functions $K$ and $B\in X^\sigma (I^2)\cap H^{\mu }(I^2)$ with $\sigma \ge \mu +1/2+\epsilon ,\mu \ge 0, \epsilon >0$ and $u\in H^{\mu }(I),$ then there exist a positive constant $c$ and a positive integer $N_0,$ such that for all $k \ge N_0$ and for all $m \in \mathbb{N }_0,$

$$\begin{aligned} ||u_{k,m,N}-u||\le c2^{-\mu (k+m)}||u||_{\mu }, \end{aligned}$$

(4.12)

where $N=k+m.$

Proof

We prove this theorem by induction on $m.$ The proof for the case $m=0$ is trivial. We assume that (4.12) holds for the case of $m-1$ and consider the case of $m.$

Let $\hat{u}_{2^{k+m}}$ be the solution of Eq. (2.8) with $n=2^{k+m}.$ By the triangle inequality, we have that

$$\begin{aligned} ||u_{k,m,N}-u||\le ||\hat{u}_{2^{k+m}}-u||+||u_{k,m,N}-\hat{u}_{2^{k+m}}||. \end{aligned}$$

The first term in the right hand side of the above inequality can be estimated directly by Theorem 2.3, that is, there holds

$$\begin{aligned} ||u-\hat{u}_{2^{k+m}}||\le c_02^{-\mu (k+m)}||u||_{\mu }, \end{aligned}$$

(4.13)

for some positive constant $c_0.$ Hence, it remains to estimate the second term. For this purpose, we first present the difference $u_{k,m,N}-\hat{u}_{2^{k+m}}$ according to Eqs. (2.8) and (4.7). Letting

$$\begin{aligned} \mathcal{T}:=\left((\mathcal{A}_{k,m}+\tilde{\mathcal{B}}_{{k,m},N} )\mathcal{P }_{2^{k+m}}\Psi \right)^{\prime } \left(\hat{u}_{2^{k+m}} \right), \end{aligned}$$

we have that

$$\begin{aligned} \left(\mathcal{I}-\mathcal{P}_{2^{k+m}}(\tilde{\mathcal{K}}_{{k,m},N}-\mathcal{T }) \right) \left(u_{k,m,N}-\hat{u}_{2^{k+m}} \right)=u_\mathcal{K}+u_\mathcal{B}+\mathcal{P }_{2^{k+m}}\mathcal{R}\left(u_{k,m,N}, \hat{u}_{2^{k+m}} \right) \end{aligned}$$

where

$$\begin{aligned} u_\mathcal{K}:=\mathcal{P}_{2^{k+m}}\left(\tilde{\mathcal{K}}_{{k,m},N}-\mathcal{K }_{2^{k+m}} \right)\hat{u}_{2^{k+m}}+ \tilde{\mathcal{K }}_{{k,m},N}^H\left(u_{k,m-1,N}-u_{k,m,N} \right), \end{aligned}$$

$$\begin{aligned}&\displaystyle u_\mathcal{B}:=\mathcal{P}_{2^{k+m}}\left(\mathcal{B}_{2^{k+m}}-\tilde{\mathcal{B }}_{{k,m},N} \right)\mathcal{P}_{2^{k+m}} \Psi \left(\hat{u}_{2^{k+m}} \right)\\&\qquad \qquad \qquad \displaystyle +\left(\mathcal{A }_{2^{k+m}}^H+\tilde{\mathcal{B}}_{{k,m},N}^H \right)\mathcal{P}_{2^{k+m}}\left( \Psi (u_{k,m,N})-\Psi (u_{k,m-1,N}) \right) \end{aligned}$$

and

$$\begin{aligned} \mathcal{R}\left(u_{k,m,N}, \hat{u}_{2^ {k+m}} \right)&:= \left(\mathcal{A }_{k,m}+\tilde{\mathcal{B}}_{{k,m},N} \right)\mathcal{P}_{2^{k+m}}\left(\Psi (\hat{u}_{ 2^{k+m}})-\Psi (u_{k,m,N}) \right)\\&-\mathcal{T} \left(\hat{u}_{2^{k+m}}-u_{k,m,N} \right). \end{aligned}$$

Note that there exist positive constants $c_1$ and $c_2$ such that for sufficiently large integer $k,\,$

$$\begin{aligned} ||\left(I-\mathcal P _{2^{k+m}}(\tilde{\mathcal{K}}_{{k,m},N}-\mathcal T ) \right)^{-1}|| \le c_1 \end{aligned}$$

and

$$\begin{aligned} ||\mathcal R \left(u_{k,m,N},\hat{u}_{2^{k+m}} \right)|| \le c_2||u_{k,m,N}-\hat{u}_{2^{k+m}}||^2. \end{aligned}$$

By the last inequality and the fact that $||u_{k,m,N}-\hat{u}_{2^{k+m}}||\rightarrow 0$ uniformly for all $m,$ as $k\rightarrow \infty ,$ we conclude that for sufficiently large integer $k$ and for all $m$ there holds

$$\begin{aligned} ||\mathcal R \left(u_{k,m,N},\hat{u}_{2^{k+m}} \right)|| \le \frac{1}{4c_1}||u_{k,m,N}-\hat{u}_{2^{k+m}}||. \end{aligned}$$

(4.14)

According to Lemmas 4.2 and 4.3, there exists a constant $c_3$ such that

$$\begin{aligned} ||u_{ \mathcal{K}}||\le c_32^{-\mu (k+m)}||\hat{u}_{2^{k+m}}|| +||\tilde{\mathcal{K}}_{k,m,N}^H||\left(||u_{k,m-1,N}-\hat{u}_{2^{k+m}}||+ ||\hat{u}_{2^{k+m}}-u_{k,m,N}|| \right), \end{aligned}$$

and

$$\begin{aligned} ||u_\mathcal{B}|| \le c_32^{-\mu (k+m)}||\hat{u}_{2^{k+m}}||+||\tilde{\mathcal{B }}_{{k,m},N}^H||L \left(|| u_{k,m-1,N}- \hat{u}_{2^{k+m}}|| +|| \hat{u}_{2^{k+m}}- u_{k,m,N}|| \right), \end{aligned}$$

where $L$ is the Lipschitz constant. Let

$$\begin{aligned} \bar{\alpha }_{k,m}:=|| \tilde{\mathcal{K}}_{{k,m},N}^H|| + L||\tilde{\mathcal{B}}_{{k,m},N}^H||. \end{aligned}$$

Since $||\hat{u}_{2^{k+m}}-u||\rightarrow 0$ and $\bar{\alpha }_{k,m}\rightarrow 0$ uniformly for all $m,$ as $k\rightarrow \infty ,$ for sufficiently large integer $k$ and for all $m,$ there exists a constant $c_4$ such that

$$\begin{aligned} ||u_\mathcal{K}||+||u_\mathcal{B}||\le c_42^{-\mu (k+m)}||u||_{\mu }+\frac{1}{4c_1}\left(||u_{k,m-1,N}-\hat{u}_{2^{k+m}}|| +||\hat{u}_{2^{k+m}}-u_{k,m,N}|| \right). \nonumber \\ \end{aligned}$$

(4.15)

Combining the inequalities (4.14) and (4.15) with the induction hypothesis, we get that

$$\begin{aligned} \begin{array}{rl} || u_{k,m,N}-\hat{u}_{ 2^{k+m}} ||&\le c^{\prime }\left(2^{-\mu (k+m)}||u||_{\mu }+||u_{k,m-1,N}-\hat{u}_{2^{k+m}}|| \right)\\&\le c^{\prime }\left(2^{-\mu (k+m)}||u||_{\mu }+||u_{k,m-1,N}-u||+||u-\hat{u}_{2^{k+m}}|| \right)\\&\le c^{\prime \prime }2^{-\mu (k+m)}||u||_{\mu } \end{array} \end{aligned}$$

(4.16)

for some positive constants $c^{\prime }$ and $c^{\prime \prime }.$ By (4.13) and (4.16), we prove (4.12) for $m.$ $\square$

4.3 Numerical examples

In this subsection, we present two numerical examples to demonstrate the approximate accuracy and computational complexity of the proposed method.

We consider solving the same nonlinear boundary integral equation as in Example 3.2 by Algorithm 2. The difference is that we choose $g_0$ such that the given function $u$ with a specific regularity is the exact solution. To demonstrate the numerical results, we define the relative error “Err” and the approximation order “AO” respectively by

$$\begin{aligned} \text{ Err}:=\frac{||u-u_{k,m,k+m}||}{||u||}, \quad \text{ and} \quad \text{ AO}:=\log _2\frac{||u-u_{k,m,k+m}||}{||u-u_{k,m+1,k+m+1}||}, \end{aligned}$$

where $u_{k,m,k+m}$ is the approximate solution obtained by Algorithm 2. We also denote by “CT” the computing time measured in seconds, which is used for generating the sparse matrices $\widetilde{\mathbf{K }}_{n,N}, \widetilde{\mathbf{B }}_{n,N}$ and solving the nonlinear system (4.4) by Algorithm 2. To confirm the quasi-linear computational complexity, we define

$$\begin{aligned} \text{ CO}:=\log _2\frac{\text{ CT}\left(2^{k+m+1} \right)}{\text{ CT}\left(2^{k+m} \right)}. \end{aligned}$$

Example 4.5

We consider solving the nonlinear boundary integral equation by Algorithm 2. Here, the right-hand side function $g_0$ is chosen such that

$$\begin{aligned} u(t)=\left\{ \begin{array}{ll} t,&\quad 0\le t<\pi , \\ 2\pi -t,&\quad \pi \le t<2\pi , \end{array} \right. \end{aligned}$$

is the exact solution of the equation. We note that $u\in H^{0.5-\epsilon }(I)$ with $\epsilon >0$ being an arbitrary number.

In this experiment, we solve (4.4) by Algorithm 2 with the initial level $k=4.$ We report the numerical results in Table 2. The third and fourth columns in Table 2 list, respectively, the relative errors and approximation order of the approximate solution of (4.4) obtained by Algorithm 2. In the fifth and sixth columns, we present respectively the computing time for implementing Algorithm 2 and computed order of computational complexity. We observe from these results that the proposed method gives the optimal convergence order $0.5-\epsilon$ and the computing time is consistent with the quasi-linear computational complexity estimate.

Table 2 Numerical results of Algorithm 2 for Example 4.5

Example 4.6

In this example, we choose the right-hand side function $g_0$ such that

$$\begin{aligned} u(t)=\frac{1}{12}(3t^2-6\pi t+2\pi ^2), \quad \ t\in I, \end{aligned}$$

is the exact solution of the equation. Here, we have $u\in H^{1.5-\epsilon }(I)$ with $\epsilon >0$ being an arbitrary number.

In Table 3, we list the numerical results for this example when we solve (4.4) by Algorithm 2 with the initial level $k=4.$ Note that, since the exact solution $u\in H^{1.5-\epsilon },$ the theoretical convergence order is $1.5-\epsilon ,$ which is confirmed by the computed order of convergence. At the same time, the computing time is also consistent with the quasi-linear computational complexity estimate.

Table 3 Numerical results of Algorithm 2 for Example 4.6