A fast Fourier transform based direct solver for the Helmholtz problem

This article is devoted to the efficient numerical solution of the Helmholtz equation in a two‐ or three‐dimensional (2D or 3D) rectangular domain with an absorbing boundary condition (ABC). The Helmholtz problem is discretized by standard bilinear and trilinear finite elements on an orthogonal mesh yielding a separable system of linear equations. The main key to high performance is to employ the fast Fourier transform (FFT) within a fast direct solver to solve the large separable systems. The computational complexity of the proposed FFT‐based direct solver is $\mathrm{??}(N\log N)$ operations. Numerical results for both 2D and 3D problems are presented confirming the efficiency of the method discussed.     

A fast direct solver for elliptic problems with a divergence constraint

A fast direct solution method for a discretized vector‐valued elliptic partial differential equation with a divergence constraint is considered. Such problems are typical in many disciplines such as fluid dynamics, elasticity and electromagnetics. The method requires the problem to be posed in a rectangle and boundary conditions to be either periodic boundary conditions or the so‐called slip boundary conditions in one co‐ordinate direction. The arising saddle‐point matrix has a separable form when bilinear finite elements are used in the discretization. Based on a result for so‐called p‐circulant matrices, the saddle‐point matrix can be transformed into a block‐diagonal form by fast Fourier transformations. Thus, the fast direct solver has the same structure as methods for scalar‐valued problems which are based on Fourier analysis and, therefore, it has the same computational cost ??(N log N). Numerical experiments demonstrate the good efficiency and accuracy of the proposed method. Copyright © 2002 John Wiley & Sons, Ltd.     

Jacobi spectral Galerkin method for elliptic Neumann problems

This paper is concerned with fast spectral-Galerkin Jacobi algorithms for solving one- and two-dimensional elliptic equations with homogeneous and nonhomogeneous Neumann boundary conditions. The paper extends the algorithms proposed by Shen (SIAM J Sci Comput 15:1489–1505, 1994) and Auteri et al. (J Comput Phys 185:427–444, 2003), based on Legendre polynomials, to Jacobi polynomials with arbitrary α and β. The key to the efficiency of our algorithms is to construct appropriate basis functions with zero slope at the endpoints, which lead to systems with sparse matrices for the discrete variational formulations. The direct solution algorithm developed for the homogeneous Neumann problem in two-dimensions relies upon a tensor product process. Nonhomogeneous Neumann data are accounted for by means of a lifting. Numerical results indicating the high accuracy and effectiveness of these algorithms are presented.     

Fast direct solver for Poisson equation in a 2D elliptical domain

In this article, we extend our previous work 3 for developing some fast Poisson solvers on 2D polar and spherical geometries to an elliptical domain. Instead of solving the equation in an irregular Cartesian geometry, we formulate the equation in elliptical coordinates. The solver relies on representing the solution as a truncated Fourier series, then solving the differential equations of Fourier coefficients by finite difference discretizations. Using a grid by shifting half mesh away from the pole and incorporating the derived numerical boundary value, the difficulty of coordinate singularity can be elevated easily. Unlike the case of 2D disk domain, the present difference equation for each Fourier mode is coupled with its conjugate mode through the numerical boundary value near the pole; thus, those two modes are solved simultaneously. Both second‐ and fourth‐order accurate schemes for Dirichlet and Neumann problems are presented. In particular, the fourth‐order accuracy can be achieved by a three‐point compact stencil which is in contrast to a five‐point long stencil for the disk case. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 72–81, 2004     

GPU implementation of a Helmholtz Krylov solver preconditioned by a shifted Laplace multigrid method

A Helmholtz equation in two dimensions discretized by a second order finite difference scheme is considered. Krylov methods such as Bi-CGSTAB and IDR(s) have been chosen as solvers. Since the convergence of the Krylov solvers deteriorates with increasing wave number, a shifted Laplace multigrid preconditioner is used to improve the convergence. The implementation of the preconditioned solver on CPU (Central Processing Unit) is compared to an implementation on GPU (Graphics Processing Units or graphics card) using CUDA (Compute Unified Device Architecture). The results show that preconditioned Bi-CGSTAB on GPU as well as preconditioned IDR(s) on GPU is about 30 times faster than on CPU for the same stopping criterion.     

A fast collocation method for acoustic scattering in shallow oceans

In this paper, we investigate the numerical solution of the integral equation of the second kind reduced by acoustic scattering in shallow oceans with Dirichlet condition. Based on analyzing the singularity of the truncating kernel with a sum of infinite series, using our trigonometric interpolatory wavelets and collocation method, we obtain the numerical solution which possesses a fast convergence rate like o(2^−j). Moreover, the entries of the stiffness matrix can be obtained by FFT, which lead the computational complexity to decrease obviously.     

Application of the discrete Fourier transform to solving the Cauchy integral equation

The uniquely solvable system of the Cauchy integral equation of the first kind and index 1 and an additional integral condition is treated. Such a system arises, for example, when solving the skew derivative problem for the Laplace equation outside an open arc in a plane. This problem models the electric current from a thin electrode in a semiconductor film placed in a magnetic field. A fast and accurate numerical method based on the discrete Fourier transform is proposed. Some computational tests are given. It is shown that the convergence is close to exponential.     

MFCAV近似Riemann解法器在相容拉氏方法中的熵条件分析

 对基于MFCAV(Multi Fluid Channel on Averaged Volume)近似Riemann解法器的相容拉氏方法的熵条件进行了分析. 结果表明与满足声学形式Riemann解法器的熵不同, 前者只能在每个网格边界左、右两侧网格的熵随时间变化的和保证大于零, 即能保证整体熵增, 但不保证传统意义上的在每个网格中的熵增;而后者不仅保证整体熵增, 而且还满足传统意义上的熵增. 因此MFCAV的熵增相对声学形式解法器而言要弱一些, 由此表明其熵增可能要小些, 使得格式的耗散可能要小些.数值算例也验证了分析的正确性.     

Fourier Moment Method with Regularization for the Cauchy Problem of Helmholtz Equation

In this paper, we consider the reconstruction of the wave field in a bounded domain. By choosing a special family of functions, the Cauchy problem can be transformed into a Fourier moment problem. This problem is ill-posed. We propose a regularization method for obtaining an approximate solution to the wave field on the unspecified boundary. We also give the convergence analysis and error estimate of the numerical algorithm. Finally, we present some numerical examples to show the effectiveness of this method.     

A multigrid solver to the Helmholtz equation with a point source based on travel time and amplitude

The Helmholtz equation arises when modeling wave propagation in the frequency domain. The equation is discretized as an indefinite linear system, which is difficult to solve at high wave numbers. In many applications, the solution of the Helmholtz equation is required for a point source. In this case, it is possible to reformulate the equation as two separate equations: one for the travel time of the wave and one for its amplitude. The travel time is obtained by a solution of the factored eikonal equation, and the amplitude is obtained by solving a complex‐valued advection–diffusion–reaction equation. The reformulated equation is equivalent to the original Helmholtz equation, and the differences between the numerical solutions of these equations arise only from discretization errors. We develop an efficient multigrid solver for obtaining the amplitude given the travel time, which can be efficiently computed. This approach is advantageous because the amplitude is typically smooth in this case and, hence, more suitable for multigrid solvers than the standard Helmholtz discretization. We demonstrate that our second‐order advection–diffusion–reaction discretization is more accurate than the standard second‐order discretization at high wave numbers, as long as there are no reflections or caustics. Moreover, we show that using our approach, the problem can be solved more efficiently than using the common shifted Laplacian multigrid approach.     

Approximation of the Singularities of a Bounded Function by the Partial Sums of Its Differentiated Fourier Series

In our earlier work we developed an algorithm for approximating the locations of discontinuities and the magnitudes of jumps of a bounded function by means of its truncated Fourier series. The algorithm is based on some asymptotic expansion formulas. In the present paper we give proofs for those formulas.     

On the Cauchy problem for a semilinear fractional elliptic equation

We study, for the first time in the literature on the subject, the Cauchy problem for a semilinear fractional elliptic equation. Under an a priori assumption on the solution, we propose the Fourier truncation method for stabilizing the ill-posed problem. A stability estimate of logarithmic type is established.     

On the finite element method for elliptic problems with degenerate and singular coefficients

We consider Dirichlet boundary value problems for second order elliptic equations over polygonal domains. The coefficients of the equations under consideration degenerate at an inner point of the domain, or behave singularly in the neighborhood of that point. This behavior may cause singularities in the solution. The solvability of the problems is proved in weighted Sobolev spaces, and their approximation by finite elements is studied. This study includes regularity results, graded meshes, and inverse estimates. Applications of the theory to some problems appearing in quantum mechanics are given. Numerical results are provided which illustrate the theory and confirm the predicted rates of convergence of the finite element approximations for quasi-uniform meshes.

     

A fast numerical method for a natural boundary integral equation for the Helmholtz equation

A Neumann boundary value problem of the Helmholtz equation in the exterior circular domain is reduced into an equivalent natural boundary integral equation. Using our trigonometric wavelets and the Galerkin method, the obtained stiffness matrix is symmetrical and circulant, which lead us to a fast numerical method based on fast Fourier transform. Furthermore, we do not need to compute the entries of the stiffness matrix. Especially, our method is also efficient when the wave number k in the Helmholtz equation is very large.     

The multi-symplectic Fourier pseudospectral method for solving two-dimensional Hamiltonian PDEs

In this paper, the multi-symplectic Fourier pseudospectral (MSFP) method is generalized to solve two-dimensional Hamiltonian PDEs with periodic boundary conditions. Using the Fourier pseudospectral method in the space of the two-dimensional Hamiltonian PDE (2D-HPDE), the semi-discrete system obtained is proved to have semi-discrete multi-symplectic conservation laws and a global symplecticity conservation law. Then, the implicit midpoint rule is employed for time integration to obtain the MSFP method for the 2D-HPDE. The fully discrete multi-symplectic conservation laws are also obtained. In addition, the proposed method is applied to solve the Zakharov-Kuznetsov (ZK) equation and the Kadomtsev-Petviashvili (KP) equation. Numerical experiments on soliton solutions of the ZK equation and the KP equation show the high accuracy and effectiveness of the proposed method.     

求解椭圆方程柯西问题的修正吉洪诺夫正则化方法

研究了一类变系数椭圆方程的柯西问题,这类问题出现在很多实际问题领域.由于问题的不适定性,不可能通过经典的数值方法来求解上述问题,必须引入正则化手段.采用了一种修正吉洪诺夫正则化方法来求解上述问题.在一种先验和一种后验参数选取准则下,分别获得了问题的误差估计.数值例子进一步显示方法是稳定有效的.     

A fourth‐order Hermitian box‐scheme with fast solver for the Poisson problem in a cube

We present a fourth‐order Hermitian box‐scheme (HB‐scheme) for the Poisson problem in a cube. A single‐nonstaggered regular grid is used supporting the discrete unknowns u and . The scheme is fourth‐order accurate for u and in norm. The fast numerical resolution uses a matrix capacitance method, resulting in a computational complexity of . Numerical results are reported on several examples including nonseparable problems. The present scheme is the extension to the three‐dimensional case of the HB‐scheme presented in Abbas and Croisille [J Sci Comp 49 (2011), 239–267]. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 609–629, 2015     

广义Benjamin-Bona-Mahony方程Fourier谱方法的大时间误差估计

§ 1　ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅＢｅｎｊａｍｉｎ Ｂｏｎａ Ｍａｈｏｎｙｅｑｕａｔｉｏｎｕｔ+ｕｘ+ｕｕｘ -ｕｘｘ-ｕｘｘｔ =0 ( 1 .1 )ｉｎｃｏｒｐｏｒａｔｅｓｎｏｎｌｉｎｅａｒｄｉｓｐｅｒｓｉｖｅａｎｄｄｉｓｓｉｐａｔｉｖｅｅｆｆｅｃｔｓ ,ａｎｄｈａｓｂｅｅｎｐｒｏｐｏｓｅｄａｓａｍｏｄｅｌｆｏｒｂｏｔｈｔｈｅｂｏｒｅｐｒｏｐａｇａｔｉｏｎａｎｄｔｈｅｗａｔｅｒｗａｖｅｓ[1,2 ] .Ｔｈｅｅｘｉｓｔｅｎｃｅａｎｄｕｎｉｑｕｅｎｅｓｓｏｆｓｏｌｕｔｉｏｎｓｆｏｒｔｈｉｓｅｑｕａｔｉｏｎｈａｖｅｂｅｅ…     

On a Construction of Fast Direct Solvers

Fast direct solvers for the Poisson equation with homogeneous Dirichlet and Neumann boundary conditions on special triangles and tetrahedra are constructed. The domain given is extended by symmetrization or skew symmetrization onto a rectangle or a rectangular parallelepiped and a fast direct solver is used there. All extendable domains are found. Eigenproblems are also considered.