Authors:Annie Cuyt; Wen-shin Lee Pages: 987 - 1002 Abstract: The problem of multivariate exponential analysis or sparse interpolation has received a lot of attention, especially with respect to the number of samples required to solve it unambiguously. In this paper we show how to bring the number of samples down to the absolute minimum of (d + 1)n where d is the dimension of the problem and n is the number of exponential terms. To this end we present a fundamentally different approach for the multivariate problem statement. We combine a one-dimensional exponential analysis method such as ESPRIT, MUSIC, the matrix pencil or any Prony-like method, with some linear systems of equations because the multivariate exponents are inner products and thus linear expressions in the parameters. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9570-8 Issue No:Vol. 44, No. 4 (2018)

Authors:Mira Bozzini; Christophe Rabut; Milvia Rossini Pages: 1003 - 1040 Abstract: The aim of the paper is to construct a multiresolution analysis of L2(IRd) based on generalized kernels which are fundamental solutions of differential operators of the form \(\boldsymbol {\prod }_{\ell = 1}^{m}(-{\Delta }+\kappa _{\ell }^{2}\,I)\) . We study its properties and provide a set of pre-wavelets associated with it, as well as the filters which are indispensable to perform decomposition and reconstruction of a given signal, being very useful in applied problems thanks to the presence of the tension parameters κℓ. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9571-7 Issue No:Vol. 44, No. 4 (2018)

Authors:Wenqing Wang; Xuehai Huang; Kai Tang; Ruiyue Zhou Pages: 1041 - 1061 Abstract: Two Morley-Wang-Xu element methods with penalty for the fourth order elliptic singular perturbation problem are proposed in this paper, including the interior penalty Morley-Wang-Xu element method and the super penalty Morley-Wang-Xu element method. The key idea in designing these two methods is combining the Morley-Wang-Xu element and penalty formulation for the Laplace operator. Robust a priori error estimates are derived under minimal regularity assumptions on the exact solution by means of some established a posteriori error estimates. Finally, we present some numerical results to demonstrate the theoretical estimates. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9572-6 Issue No:Vol. 44, No. 4 (2018)

Authors:Ali Kashefi; Anne E. Staples Pages: 1063 - 1090 Abstract: Coarse grid projection (CGP) methodology is a novel multigrid method for systems involving decoupled nonlinear evolution equations and linear elliptic Poisson equations. The nonlinear equations are solved on a fine grid and the linear equations are solved on a corresponding coarsened grid. Mapping operators execute data transfer between the grids. The CGP framework is constructed upon spatial and temporal discretization schemes. This framework has been established for finite volume/difference discretizations as well as explicit time integration methods. In this article we present for the first time a version of CGP for finite element discretizations, which uses a semi-implicit time integration scheme. The mapping functions correspond to the finite-element shape functions. With the novel data structure introduced, the mapping computational cost becomes insignificant. We apply CGP to pressure-correction schemes used for the incompressible Navier-Stokes flow computations. This version is validated on standard test cases with realistic boundary conditions using unstructured triangular meshes. We also pioneer investigations of the effects of CGP on the accuracy of the pressure field. It is found that although CGP reduces the pressure field accuracy, it preserves the accuracy of the pressure gradient and thus the velocity field, while achieving speedup factors ranging from approximately 2 to 30. The minimum speedup occurs for velocity Dirichlet boundary conditions, while the maximum speedup occurs for open boundary conditions. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9573-5 Issue No:Vol. 44, No. 4 (2018)

Authors:Hongjin He; Liusheng Hou; Hong-Kun Xu Pages: 1091 - 1115 Abstract: During the last decade, the state-of-the-art alternating direction method of multipliers (ADMM) has successfully been used to solve many two-block separable convex minimization problems arising from several applied areas such as signal/image processing and statistical and machine learning. It however remains an interesting problem of how to implement ADMM to three-block separable convex minimization problems as required by the situation where many objective functions in the above-mentioned areas are actually more conveniently decomposed to the sum of three convex functions, due also to the observation that the straightforward extension of ADMM from the two-block case to the three-block case is apparently not convergent. In this paper, we shall introduce a new algorithm that is called a partially isochronous splitting algorithm (PISA) in order to implement ADMM for the three-block separable model. The main idea of our algorithm is to incorporate only one proximal term into the last subproblem of the extended ADMM so that the resulting algorithm maximally inherits the promising properties of ADMM. A remarkable superiority over the extended ADMM is that we can simultaneously solve two of the subproblems, thereby taking advantages of the separable structure and parallel architectures. Theoretically, we will establish the global convergence of our algorithm under standard conditions, and also the O(1/t) rate of convergence in both ergodic and nonergodic senses, where t is the iteration counter. The computational competitiveness of our algorithm is shown by numerical experiments on an application to the well-tested robust principal component analysis model. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9574-4 Issue No:Vol. 44, No. 4 (2018)

Authors:Hongjin He; Liusheng Hou; Hong-Kun Xu Pages: 1117 - 1118 Abstract: The original publication of this article has an error. PubDate: 2018-08-01 DOI: 10.1007/s10444-018-9591-y Issue No:Vol. 44, No. 4 (2018)

Authors:Doghonay Arjmand; Mikhail Poluektov; Gunilla Kreiss Pages: 1119 - 1151 Abstract: In this article, a few problems related to multiscale modelling of magnetic materials at finite temperatures and possible ways of solving these problems are discussed. The discussion is mainly centred around two established multiscale concepts: the partitioned domain and the upscaling-based methodologies. The major challenge for both multiscale methods is to capture the correct value of magnetisation length accurately, which is affected by a random temperature-dependent force. Moreover, general limitations of these multiscale techniques in application to spin systems are discussed. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9575-3 Issue No:Vol. 44, No. 4 (2018)

Authors:Biswarup Biswas; Ritesh Kumar Dubey Pages: 1153 - 1181 Abstract: A low dissipative framework is given to construct high order entropy stable flux by addition of suitable numerical diffusion operator into entropy conservative flux. The framework is robust in the sense that it allows the use of high order reconstructions which satisfy the sign property only across the discontinuities. The third order weighted essentially non-oscillatory (WENO) interpolations and high order total variation diminishing (TVD) reconstructions are shown to satisfy the sign property across discontinuities. Third order accurate entropy stable schemes are constructed by using third order WENO and high order TVD reconstructions procedures in the diffusion operator. These schemes are efficient and less diffusive since the diffusion is actuated only in the sign stability region of the used reconstruction which includes discontinuities. Numerical results with constructed schemes for various test problems are given which show the third order accuracy and less dissipative nature of the schemes. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9576-2 Issue No:Vol. 44, No. 4 (2018)

Authors:Emil Solsbæk Ottosen; Morten Nielsen Pages: 1183 - 1203 Abstract: We consider sparseness properties of adaptive time-frequency representations obtained using nonstationary Gabor frames (NSGFs). NSGFs generalize classical Gabor frames by allowing for adaptivity in either time or frequency. It is known that the concept of painless nonorthogonal expansions generalizes to the nonstationary case, providing perfect reconstruction and an FFT based implementation for compactly supported window functions sampled at a certain density. It is also known that for some signal classes, NSGFs with flexible time resolution tend to provide sparser expansions than can be obtained with classical Gabor frames. In this article we show, for the continuous case, that sparseness of a nonstationary Gabor expansion is equivalent to smoothness in an associated decomposition space. In this way we characterize signals with sparse expansions relative to NSGFs with flexible time resolution. Based on this characterization we prove an upper bound on the approximation error occurring when thresholding the coefficients of the corresponding frame expansions. We complement the theoretical results with numerical experiments, estimating the rate of approximation obtained from thresholding the coefficients of both stationary and nonstationary Gabor expansions. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9577-1 Issue No:Vol. 44, No. 4 (2018)

Authors:Keaton Hamm; Jeff Ledford Pages: 1205 - 1233 Abstract: This article pertains to interpolation of Sobolev functions at shrinking lattices \(h\mathbb {Z}^{d}\) from L p shift-invariant spaces associated with cardinal functions related to general multiquadrics, ϕ α, c (x) := ( x 2 + c 2) α . The relation between the shift-invariant spaces generated by the cardinal functions and those generated by the multiquadrics themselves is considered. Additionally, L p error estimates in terms of the dilation h are considered for the associated cardinal interpolation scheme. This analysis expands the range of α values which were previously known to give such convergence rates (i.e. O(h k ) for functions with derivatives of order up to k in L p , \(1<p<\infty \) ). Additionally, the analysis here demonstrates that some known best approximation rates for multiquadric approximation are obtained by their cardinal interpolants. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9578-0 Issue No:Vol. 44, No. 4 (2018)

Authors:Na Liu; Wei Jiang Pages: 1235 - 1248 Abstract: In this article, we proposed a new numerical method to obtain the approximation solution for the time-fractional Schrödinger equation based on reproducing kernel theory and collocation method. In order to overcome the weak singularity of typical solutions, we apply the integral operator to both sides of differential equation and yield a integral equation. We divided the solution of this kind equation into two parts: imaginary part and real part, and then derived the approximate solutions of the two parts in the form of series with easily computable terms in the reproducing kernel space. New bases of reproducing kernel spaces are constructed and the existence of approximate solution is proved. Numerical examples are given to show the accuracy and effectiveness of our approach. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9579-z Issue No:Vol. 44, No. 4 (2018)

Authors:Alan E. Lindsay; Bryan Quaife; Laura Wendelberger Pages: 1249 - 1273 Abstract: We consider the bi-Laplacian eigenvalue problem for the modes of vibration of a thin elastic plate with a discrete set of clamped points. A high-order boundary integral equation method is developed for efficient numerical determination of these modes in the presence of multiple localized defects for a wide range of two-dimensional geometries. The defects result in eigenfunctions with a weak singularity that is resolved by decomposing the solution as a superposition of Green’s functions plus a smooth regular part. This method is applied to a variety of regular and irregular domains and two key phenomena are observed. First, careful placement of clamping points can entirely eliminate particular eigenvalues and suggests a strategy for manipulating the vibrational characteristics of rigid bodies so that undesirable frequencies are removed. Second, clamping of the plate can result in partitioning of the domain so that vibrational modes are largely confined to certain spatial regions. This numerical method gives a precision tool for tuning the vibrational characteristics of thin elastic plates. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9580-6 Issue No:Vol. 44, No. 4 (2018)

Authors:Denis Khleborodov Pages: 1275 - 1293 Abstract: This article presents two methods for developing algorithms of computing scalar multiplication in groups of points on an elliptic curve over finite fields. Two new effective algorithms have been presented: one of them is based on a binary Non-Adjacent Form of scalar representation and another one on a binary of scalar representation method. All algorithms were developed based on simple and composite operations with point and also based on affine and Jacobi coordinates systems taking into account the latest achievements in computing cost reduction. Theorems concerning their computational complexity are formulated and proved for these new algorithms. In the end of this article comparative analysis of both new algorithms among themselves and previously known algorithms are represented. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9581-5 Issue No:Vol. 44, No. 4 (2018)

Authors:Xiaojing Dong; Yinnian He; Hongbo Wei; Yuhong Zhang Pages: 1295 - 1319 Abstract: Based on the partition of unity method (PUM), a local and parallel finite element method is designed and analyzed for solving the stationary incompressible magnetohydrodynamics (MHD). The key idea of the proposed algorithm is to first solve the nonlinear system on a coarse mesh, divide the globally fine grid correction into a series of locally linearized residual problems on some subdomains derived by a class of partition of unity, then compute the local subproblems in parallel, and obtain the globally continuous finite element solution by assembling all local solutions together by the partition of unity functions. The main feature of the new method is that the partition of unity provide a flexible and controllable framework for the domain decomposition. Finally, the efficiency of our theoretical analysis is tested by numerical experiments. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9582-4 Issue No:Vol. 44, No. 4 (2018)

Authors:F. Lara Pages: 1321 - 1323 Abstract: In this note, the notion of admissible sets contained in the strictly positive orthant introduced in Micchelli et al. (Adv. Comp. Math. 38(3), 455–489 2013) is analyzed. This notion was used to generalize theoretical results and optimization methods for structured sparsity. Unfortunately, we will prove that there is no generalization using admissible sets. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9583-3 Issue No:Vol. 44, No. 4 (2018)

Authors:Ya-Ru Fan; Alessandro Buccini; Marco Donatelli; Ting-Zhu Huang Abstract: Compressive sensing (CS) aims at reconstructing high dimensional data from a small number of samples or measurements. In this paper, we propose the minimization of a non-convex functional for the solution of the CS problem. The considered functional incorporates information on the self-similarity of the image by measuring the rank of some appropriately constructed matrices of fairly small dimensions. However, since the rank minimization is a NP hard problem, we consider, as a surrogate function for the rank, a non-convex, but smooth function. We provide a theoretical analysis of the proposed functional and develop an iterative algorithm to compute one of its stationary points. We prove the convergence of such algorithm and show, with some selected numerical experiments, that the proposed approach achieves good performances, even when compared with the state of the art. PubDate: 2018-08-09 DOI: 10.1007/s10444-018-9627-3

Authors:Sina Bittens; Ruochuan Zhang; Mark A. Iwen Abstract: In this paper, a deterministic sparse Fourier transform algorithm is presented which breaks the quadratic-in-sparsity runtime bottleneck for a large class of periodic functions exhibiting structured frequency support. These functions include, e.g., the often considered set of block frequency sparse functions of the form $$f(x) = \sum\limits^{n}_{j = 1} \sum\limits^{B-1}_{k = 0} c_{\omega_{j} + k} e^{i(\omega_{j} + k)x},~~\{ \omega_{1}, \dots, \omega_{n} \} \subset \left( -\left\lceil \frac{N}{2}\right\rceil, \left\lfloor \frac{N}{2}\right\rfloor\right]\cap\mathbb{Z}$$ as a simple subclass. Theoretical error bounds in combination with numerical experiments demonstrate that the newly proposed algorithms are both fast and robust to noise. In particular, they outperform standard sparse Fourier transforms in the rapid recovery of block frequency sparse functions of the type above. PubDate: 2018-08-09 DOI: 10.1007/s10444-018-9626-4

Authors:Roland Herzog; John W. Pearson; Martin Stoll Abstract: Optimal transport problems pose many challenges when considering their numerical treatment. We investigate the solution of a PDE-constrained optimisation problem subject to a particular transport equation arising from the modelling of image metamorphosis. We present the nonlinear optimisation problem, and discuss the discretisation and treatment of the nonlinearity via a Gauss–Newton scheme. We then derive preconditioners that can be used to solve the linear systems at the heart of the (Gauss–)Newton method. PubDate: 2018-08-07 DOI: 10.1007/s10444-018-9625-5

Authors:Burak Aksoylu; Fatih Celiker; Orsan Kilicer Abstract: We present novel nonlocal governing operators in 2D/3D for wave propagation and diffusion. The operators are inspired by peridynamics. They agree with the original peridynamics operator in the bulk of the domain and simultaneously enforce local boundary conditions (BC). The main ingredients are periodic, antiperiodic, and mixed extensions of separable kernel functions together with even and odd parts of bivariate functions on rectangular/box domains. The operators are bounded and self-adjoint. We present all possible 36 different types of BC in 2D which include pure and mixed combinations of Neumann, Dirichlet, periodic, and antiperiodic BC. Our construction is systematic and easy to follow. We provide numerical experiments that verify our theoretical findings. We also compare the solutions of the classical wave and heat equations to their nonlocal counterparts. PubDate: 2018-08-02 DOI: 10.1007/s10444-018-9624-6

Authors:Yuanyuan Zhang; Min Yang; Chuanjun Chen Abstract: In this paper, we construct and analyze a nonconforming finite volume method (FVM) for solving the elliptic boundary value problems on quadrilateral meshes: the hybrid Wilson FVM. Under the mesh assumption that the underlying mesh is an h2-parallelogram mesh, we show that the scheme possesses first order in the mesh-dependent H1-norm and second order in the L2-norm error estimates, the same optimal convergence orders as those of the corresponding Wilson finite element method (FEM). Numerical results are presented to demonstrate the theoretical results on the convergence order of the method. PubDate: 2018-07-26 DOI: 10.1007/s10444-018-9623-7