Effective and accurate high-degree spline interpolation is still a challenging task in today’s applications. Higher degree spline interpolation is not so commonly used, because it requires the knowledge of higher order derivatives at the nodes of a function on a given mesh.

In this article, our goal is to demonstrate the continuity of the piecewise polynomials and their derivatives at the connecting points, obtained with a method initially developed by Beaudoin (1998, 2003) and Beauchemin (2003). This new method, involving the discrete Fourier transform (DFT/FFT), leads to higher degree spline interpolation for equally spaced data on an interval $[0,T]$. To do this, we analyze the singularities that may occur when solving the system of equations that enables the construction of splines of any degree. We also note an important difference between the odd-degree splines and even-degree splines. These results prove that Beaudoin and Beauchemin’s method leads to spline interpolation of any degree and that this new method could eventually be used to improve the accuracy of spline interpolation in traditional problems.

In 2005 Bourgain gave the first explicit construction of a two-source extractor family with min-entropy rate less than $1/2$. His approach combined Fourier analysis with innovative but inefficient tools from arithmetic combinatorics and yielded an unspecified min-entropy rate which was greater than $0.499$. This remained essentially the state of the art until a 2015 breakthrough by Chattopadhyay and Zuckerman in which they gave an alternative approach which produced extractors with arbitrarily small min-entropy rate. In the current work, we revisit the Fourier analytic approach. We give an improved analysis of one of Bourgain’s extractors which shows that it in fact extracts from sources with min-entropy rate near $\frac{21}{44}=0.477\ldots .$ Moreover, we construct a variant of this extractor which we show extracts from sources with min-entropy rate near $4/9=0.444\ldots .$ While this min-entropy rate is inferior to Chattopadhyay and Zuckerman’s construction, our extractors have the advantage of exponential small error, which is important in some applications. The key ingredient in these arguments is recent progress connected to the restriction theory of the finite field paraboloid by Rudnev and Shkredov. This in turn relies on a Rudnev’s point–plane incidence estimate, which in turn relies on Kollár’s generalization of the Guth–Katz incidence theorem.

This study makes the first attempt to accelerate the singular boundary method (SBM) by the precorrected-FFT (PFFT) for large-scale three-dimensional potential problems. The SBM with the GMRES solver requires computational complexity, where N is the number of the unknowns. To speed up the SBM, the PFFT is employed to accelerate the SBM matrix-vector multiplication at each iteration step of the GMRES. Consequently, the computational complexity can be reduced to . Several numerical examples are presented to validate the developed PFFT accelerated SBM (PFFT-SBM) scheme, and the results are compared with those of the SBM without the PFFT and the analytical solutions. It is clearly found that the present PFFT-SBM is very efficient and suitable for 3D large-scale potential problems.

In this paper, we develop a novel energy-preserving wavelet collocation method for solving general multi-symplectic formulations of Hamiltonian PDEs. Based on the autocorrelation functions of Daubechies compactly supported scaling functions, the wavelet collocation method is conducted for spatial discretization. The obtained semi-discrete system is shown to be a finite-dimensional Hamiltonian system, which has an energy conservation law. Then, the average vector field method is used for time integration, which leads to an energy-preserving method for multi-symplectic Hamiltonian PDEs. The proposed method is illustrated by the nonlinear Schrödinger equation and the Camassa-Holm equation. Since differentiation matrix obtained by the wavelet collocation method is a cyclic matrix, we can apply Fast Fourier transform to solve equations in numerical calculation. Numerical experiments show the high accuracy, effectiveness and conservation properties of the proposed method.

We propose efficient and accurate numerical methods for computing the ground state and dynamics of the dipolar Bose-Einstein condensates utilising a newly developed dipole-dipole interaction (DDI) solver that is implemented with the non-uniform fast Fourier transform (NUFFT) algorithm. We begin with the three-dimensional (3D) Gross-Pitaevskii equation (GPE) with a DDI term and present the corresponding two-dimensional (2D) model under a strongly anisotropic confining potential. Different from existing methods, the NUFFT based DDI solver removes the singularity by adopting the spherical/polar coordinates in the Fourier space in 3D/2D, respectively, thus it can achieve spectral accuracy in space and simultaneously maintain high efficiency by making full use of FFT and NUFFT whenever it is necessary and/or needed. Then, we incorporate this solver into existing successful methods for computing the ground state and dynamics of GPE with a DDI for dipolar BEC. Extensive numerical comparisons with existing methods are carried out for computing the DDI, ground states and dynamics of the dipolar BEC. Numerical results show that our new methods outperform existing methods in terms of both accuracy and efficiency.

High-dimensional two-sided space fractional diffusion equations with variable diffusion coefficients are discussed. The problems can be solved by an implicit finite difference scheme that is proven to be uniquely solvable, unconditionally stable and first-order convergent in the infinity norm. A nonsingular multilevel circulant pre-conditoner is proposed to accelerate the convergence rate of the Krylov subspace linear system solver efficiently. The preconditoned matrix for fast convergence is a sum of the identity matrix, a matrix with small norm, and a matrix with low rank under certain conditions. Moreover, the preconditioner is practical, with an O(N logN) operation cost and O(N) memory requirement. Illustrative numerical examples are also presented.

We have developed efficient numerical algorithms for solving 3D steady-state Poisson-Nernst-Planck (PNP) equations with excess chemical potentials described by the classical density functional theory (cDFT). The coupled PNP equations are discretized by a finite difference scheme and solved iteratively using the Gummel method with relaxation. The Nernst-Planck equations are transformed into Laplace equations through the Slotboom transformation. Then, the algebraic multigrid method is applied to efficiently solve the Poisson equation and the transformed Nernst-Planck equations. A novel strategy for calculating excess chemical potentials through fast Fourier transforms is proposed, which reduces computational complexity from O(N2) to O(NlogN), where N is the number of grid points. Integrals involving the Dirac delta function are evaluated directly by coordinate transformation, which yields more accurate results compared to applying numerical quadrature to an approximated delta function. Numerical results for ion and electron transport in solid electrolyte for lithiumion (Li-ion) batteries are shown to be in good agreement with the experimental data and the results from previous studies.

We study the computation of ground states and time dependent solutions of the Schrödinger-Poisson system (SPS) on a bounded domain in 2D (i.e. in two space dimensions). On a disc-shaped domain, we derive exact artificial boundary conditions for the Poisson potential based on truncated Fourier series expansion in θ, and propose a second order finite difference scheme to solve the r-variable ODEs of the Fourier coefficients. The Poisson potential can be solved within (MNlogN) arithmetic operations where M,N are the number of grid points in r-direction and the Fourier bases. Combined with the Poisson solver, a backward Euler and a semi-implicit/leap-frog method are proposed to compute the ground state and dynamics respectively. Numerical results are shown to confirm the accuracy and efficiency. Also we make it clear that backward Euler sine pseudospectral (BESP) method in [33] can not be applied to 2D SPS simulation.

In this paper, we derive a multi-symplectic Fourier pseudospectral scheme for the Kawahara equation with special attention to the relationship between the spectral differentiation matrix and discrete Fourier transform. The relationship is crucial for implementing the scheme efficiently. By using the relationship, we can apply the Fast Fourier transform to solve the Kawahara equation. The effectiveness of the proposed methods will be demonstrated by a number of numerical examples. The numerical results also confirm that the global energy and momentum are well preserved.

The alternating direction method of multipliers (ADMM) is applied to a constrained linear least-squares problem, where the objective function is a sum of two least-squares terms and there are box constraints. The original problem is decomposed into two easier least-squares subproblems at each iteration, and to speed up the inner iteration we linearize the relevant subproblem whenever it has no known closed-form solution. We prove the convergence of the resulting algorithm, and apply it to solve some image deblurring problems. Its efficiency is demonstrated, in comparison with Newton-type methods.

A high-order discretization consisting of a tensor product of the Fourier collocation and discontinuous Galerkin methods is presented for numerical modeling of magma dynamics. The physical model is an advection-reaction type system consisting of two hyperbolic equations and one elliptic equation. The high-order solution basis allows for accurate and efficient representation of compaction-dissolution waves that are predicted from linear theory. The discontinuous Galerkin method provides a robust and efficient solution to the eigenvalue problem formed by linear stability analysis of the physical system. New insights into the processes of melt generation and segregation, such as melt channel bifurcation, are revealed from two-dimensional time-dependent simulations.

Homogeneous isotropic turbulence has been playing a key role in the research of turbulence theory. And the pseudo-spectral method is the most popular numerical method to simulate this type of flow fields in a periodic box, where fast Fourier transform (FFT) is mostly effective. However, the bottle-neck in this method is the memory of computer, which motivates us to construct a memory-saving algorithm for spectral method in present paper. Inevitably, more times of FFT are needed as compensation. In the most memory-saving situation, only 6 three-dimension arrays are employed in the code. The cost of computation is increased by a factor of 4, and that 38 FFTs are needed per time step instead of the previous 9 FFTs. A simulation of isotropic turbulence on 20483 grid can be implemented on a 256G distributed memory clusters through this method.

We present a fast Poisson solver on spherical shells. With a special change of variable, the radial part of the Laplacian transforms to a constant coefficient differential operator. As a result, the Fast Fourier Transform can be applied to solve the Poisson equation with operations. Numerical examples have confirmed the accuracy and robustness of the new scheme.

In this paper we present a robust numerical method to compute the scale function W(q)(x) of a general spectrally negative Lévy process (X, P). The method is based on the Esscher transform of measure Pν under which X is taken and the scale function is determined. This change of measure makes it possible for the scale function to be bounded and, hence, makes numerical computation easy, fast, and stable. Working under the new measure Pν and using the method of Abate and Whitt (1992) and Choudhury, Lucantoni, and Whitt (1994), we give a fast stable numerical algorithm for the computation of W(q)(x).