Authors:Hendrik Speleers Pages: 235 - 255 Abstract: Abstract A local approximation study is presented for hierarchical spline spaces. Such spaces are composed of a hierarchy of nested spaces and provide a flexible framework for local refinement in any dimensionality. We provide approximation estimates for general hierarchical quasi-interpolants expressed in terms of the truncated hierarchical basis. Under some mild assumptions, we prove that such hierarchical quasi-interpolants and their derivatives possess optimal local approximation power in the general q-norm with \(1\leq q\leq \infty \) . In addition, we detail a specific family of hierarchical quasi-interpolants defined on uniform hierarchical meshes in any dimensionality. The construction is based on cardinal B-splines of degree p and central factorial numbers of the first kind. It guarantees polynomial reproduction of degree p and it requires only function evaluations at grid points (odd p) or half-grid points (even p). This results in good approximation properties at a very low cost, and is illustrated with some numerical experiments. PubDate: 2017-04-01 DOI: 10.1007/s10444-016-9483-y Issue No:Vol. 43, No. 2 (2017)

Authors:Mazen Ali; Kristina Steih; Karsten Urban Pages: 257 - 294 Abstract: Abstract We use asymptotically optimal adaptive numerical methods (here specifically a wavelet scheme) for snapshot computations within the offline phase of the Reduced Basis Method (RBM). The resulting discretizations for each snapshot (i.e., parameter-dependent) do not permit the standard RB ‘truth space’, but allow for error estimation of the RB approximation with respect to the exact solution of the considered parameterized partial differential equation. The residual-based a posteriori error estimators are computed by an adaptive dual wavelet expansion, which allows us to compute a surrogate of the dual norm of the residual. The resulting adaptive RBM is analyzed. We show the convergence of the resulting adaptive greedy method. Numerical experiments for stationary and instationary problems underline the potential of this approach. PubDate: 2017-04-01 DOI: 10.1007/s10444-016-9485-9 Issue No:Vol. 43, No. 2 (2017)

Authors:Kanghui Guo; Demetrio Labate Pages: 295 - 318 Abstract: Abstract Edges and surface boundaries are often the most relevant features in images and multidimensional data. It is well known that multiscale methods including wavelets and their more sophisticated multidimensional siblings offer a powerful tool for the analysis and detection of such sets. Among such methods, the continuous shearlet transform has been especially successful. This method combines anisotropic scaling and directional sensitivity controlled by shear transformations in order to precisely identify not only the location of edges and boundary points but also edge orientation and corner points. In this paper, we show that this framework can be made even more flexible by controlling the scaling parameter of the anisotropic dilation matrix and considering non-parabolic scaling. We prove that, using ‘higher-than-parabolic’ scaling, the modified shearlet transform is also able to estimate the degree of local flatness of an edge or surface boundary, providing more detailed information about the geometry of edge and boundary points. PubDate: 2017-04-01 DOI: 10.1007/s10444-016-9486-8 Issue No:Vol. 43, No. 2 (2017)

Authors:Tongke Wang; Zhiyue Zhang; Zhifang Liu Pages: 319 - 350 Abstract: Abstract A general framework is constructed for efficiently and stably evaluating the Hadamard finite-part integrals by composite quadrature rules. Firstly, the integrands are assumed to have the Puiseux expansions at the endpoints with arbitrary algebraic and logarithmic singularities. Secondly, the Euler-Maclaurin expansion of a general composite quadrature rule is obtained directly by using the asymptotic expansions of the partial sums of the Hurwitz zeta function and the generalized Stieltjes constant, which shows that the standard numerical integration formula is not convergent for computing the Hadamard finite-part integrals. Thirdly, the standard quadrature formula is recast in two steps. In step one, the singular part of the integrand is integrated analytically and in step two, the regular integral of the remaining part is evaluated using the standard composite quadrature rule. In this stage, a threshold is introduced such that the function evaluations in the vicinity of the singularity are intentionally excluded, where the threshold is determined by analyzing the roundoff errors caused by the singular nature of the integrand. Fourthly, two practical algorithms are designed for evaluating the Hadamard finite-part integrals by applying the Gauss-Legendre and Gauss-Kronrod rules to the proposed framework. Practical error indicator and implementation involved in the Gauss-Legendre rule are addressed. Finally, some typical examples are provided to show that the algorithms can be used to effectively evaluate the Hadamard finite-part integrals over finite or infinite intervals. PubDate: 2017-04-01 DOI: 10.1007/s10444-016-9487-7 Issue No:Vol. 43, No. 2 (2017)

Authors:Adrianna Gillman Pages: 351 - 364 Abstract: Abstract This paper presents an integral formulation for Helmholtz problems with mixed boundary conditions. Unlike most integral equation techniques for mixed boundary value problems, the proposed method uses a global boundary charge density. As a result, Calderón identities can be utilized to avoid the use of hypersingular integral operators. Numerical results illustrate the performance of the proposed solution technique. PubDate: 2017-04-01 DOI: 10.1007/s10444-016-9488-6 Issue No:Vol. 43, No. 2 (2017)

Authors:Rishi Kumar Pandey; Hradyesh Kumar Mishra Pages: 365 - 383 Abstract: Abstract In this article, we apply the newly introduced numerical method which is a combination of Sumudu transforms and Homotopy analysis method for the solution of time fractional third order dispersive type PDE equations. It is also discussed generalized algorithm, absolute convergence and analytic result of the finite number of independent variables including time variable. PubDate: 2017-04-01 DOI: 10.1007/s10444-016-9489-5 Issue No:Vol. 43, No. 2 (2017)

Authors:Zhendong Gu Pages: 385 - 409 Abstract: Abstract The main purpose of this paper is to investigate the piecewise spectral collocation method for system of Volterra integral equations. The provided convergence analysis shows that the presented method performs better than global spectral collocation method and piecewise polynomial collocation method. Numerical experiments are carried out to confirm these theoretical results. PubDate: 2017-04-01 DOI: 10.1007/s10444-016-9490-z Issue No:Vol. 43, No. 2 (2017)

Authors:Vladimir Kazeev; Ivan Oseledets; Maxim Rakhuba; Christoph Schwab Pages: 411 - 442 Abstract: Abstract Tensor-compressed numerical solution of elliptic multiscale-diffusion and high frequency scattering problems is considered. For either problem class, solutions exhibit multiple length scales governed by the corresponding scale parameter: the scale of oscillations of the diffusion coefficient or smallest wavelength, respectively. As is well-known, this imposes a scale-resolution requirement on the number of degrees of freedom required to accurately represent the solutions in standard finite-element (FE) discretizations. Low-order FE methods are by now generally perceived unsuitable for high-frequency coefficients in diffusion problems and high wavenumbers in scattering problems. Accordingly, special techniques have been proposed instead (such as numerical homogenization, heterogeneous multiscale method, oversampling, etc.) which require, in some form, a-priori information on the microstructure of the solution. We analyze the approximation properties of tensor-formatted, conforming first-order FE methods for scale resolution in multiscale problems without a-priori information. The FE methods are based on the dynamic extraction of principal components from stiffness matrices, load and solution vectors by the quantized tensor train (QTT) decomposition. For prototypical model problems, we prove that this approach, by means of the QTT reparametrization of the FE space, allows to identify effective degrees of freedom to replace the degrees of freedom of a uniform “virtual” (i.e. never directly accessed) mesh, whose number may be prohibitively large to realize computationally. Precisely, solutions of model elliptic homogenization and high-frequency acoustic scattering problems are proved to admit QTT-structured approximations whose number of effective degrees of freedom required to reach a prescribed approximation error scales polylogarithmically with respect to the reciprocal of the target Sobolev-norm accuracy ε with only a mild dependence on the scale parameter. No a-priori information on the nature of the problems and intrinsic length scales of the solution is required in the numerical realization of the presently proposed QTT-structured approach. Although only univariate model multiscale problems are analyzed in the present paper, QTT structured algorithms are applicable also in several variables. Detailed numerical experiments confirm the theoretical bounds. As a corollary of our analysis, we prove that for the mentioned model problems, the Kolmogorov n-widths of solution sets are exponentially small for analytic data, independently of the problems’ scale parameters. That implies, in particular, the exponential convergence of reduced basis techniques which is scale-robust, i.e., independent of the scale parameter in the problem. PubDate: 2017-04-01 DOI: 10.1007/s10444-016-9491-y Issue No:Vol. 43, No. 2 (2017)

Authors:Ole Christensen; Marzieh Hasannasab; Jakob Lemvig Pages: 443 - 472 Abstract: Abstract Generalized shift-invariant (GSI) systems, originally introduced by Hernández et al. and Ron and Shen, provide a common frame work for analysis of Gabor systems, wavelet systems, wave packet systems, and other types of structured function systems. In this paper we analyze three important aspects of such systems. First, in contrast to the known cases of Gabor frames and wavelet frames, we show that for a GSI system forming a frame, the Calderón sum is not necessarily bounded by the lower frame bound. We identify a technical condition implying that the Calderón sum is bounded by the lower frame bound and show that under a weak assumption the condition is equivalent with the local integrability condition introduced by Hernández et al. Second, we provide explicit and general constructions of frames and dual pairs of frames having the GSI-structure. In particular, the setup applies to wave packet systems and in contrast to the constructions in the literature, these constructions are not based on characteristic functions in the Fourier domain. Third, our results provide insight into the local integrability condition (LIC). PubDate: 2017-04-01 DOI: 10.1007/s10444-016-9492-x Issue No:Vol. 43, No. 2 (2017)

Authors:Tahar Z. Boulmezaoud; Keltoum Kaliche; Nabil Kerdid Abstract: Abstract We use inverted finite element method (IFEM) for computing three-dimensional vector potentials and for solving div-curl systems in the whole space \(\mathbb {R}^{3}\) . IFEM is substantially different from the existing approaches since it is a non truncature method which preserves the unboundness of the domain. After developping the method, we analyze its convergence in term of weighted norms. We then give some three-dimensional numerical results which demonstrate the efficiency and the accuracy of the method and confirm its convergence. PubDate: 2017-04-14 DOI: 10.1007/s10444-017-9532-1

Authors:Thomas Führer; Norbert Heuer Abstract: Abstract We present and analyze a preconditioner of the additive Schwarz type for the mortar boundary element method. As a basic splitting, on each subdomain we separate the degrees of freedom related to its boundary from the inner degrees of freedom. The corresponding wirebasket-type space decomposition is stable up to logarithmic terms. For the blocks that correspond to the inner degrees of freedom standard preconditioners for the hypersingular integral operator on open boundaries can be used. For the boundary and interface parts as well as the Lagrangian multiplier space, simple diagonal preconditioners are optimal. Our technique applies to quasi-uniform and non-uniform meshes of shape-regular elements. Numerical experiments on triangular and quadrilateral meshes confirm theoretical bounds for condition and MINRES iteration numbers. PubDate: 2017-04-14 DOI: 10.1007/s10444-017-9534-z

Authors:Pedro G. Massey; Noelia B. Rios; Demetrio Stojanoff Abstract: Abstract Let \(\mathcal {F}_{0}=\{f_{i}\}_{i\in \mathbb {I}_{n_{0}}}\) be a finite sequence of vectors in \(\mathbb {C}^{d}\) and let \(\mathbf {a}=(a_{i})_{i\in \mathbb {I}_{k}}\) be a finite sequence of positive numbers, where \(\mathbb {I}_{n}=\{1,\ldots , n\}\) for \(n\in \mathbb {N}\) . We consider the completions of \(\mathcal {F}_{0}\) of the form \(\mathcal {F}=(\mathcal {F}_{0},\mathcal {G})\) obtained by appending a sequence \(\mathcal {G}=\{g_{i}\}_{i\in \mathbb {I}_{k}}\) of vectors in \(\mathbb {C}^{d}\) such that ∥g i ∥2 = a i for \(i\in \mathbb {I}_{k}\) , and endow the set of completions with the metric \(d(\mathcal {F},\tilde {\mathcal {F}}) =\max \{ \,\ g_{i}-\tilde {g}_{i}\ : \ i\in \mathbb {I}_{k}\}\) where \(\tilde {\mathcal {F}}=(\mathcal {F}_{0},\,\tilde {\mathcal {G}})\) . In this context we show that local minimizers on the set of completions of a convex potential P φ , induced by a strictly convex function φ, are also global minimizers. In case that φ(x) = x 2 then P φ is the so-called frame potential introduced by Benedetto and Fickus, and our work generalizes several well known results for this potential. We show that there is an intimate connection between frame completion problems with prescribed norms and frame operator distance (FOD) problems. We use this connection and our results to settle in the affirmative a generalized version of Strawn’s conjecture on the FOD. PubDate: 2017-04-12 DOI: 10.1007/s10444-017-9535-y

Authors:Axel Flinth Abstract: Abstract This paper concerns solving the sparse deconvolution and demixing problem using ℓ 1,2-minimization. We show that under a certain structured random model, robust and stable recovery is possible. The results extend results of Ling and Strohmer (Inverse Probl. 31, 115002 2015), and in particular theoretically explain certain experimental findings from that paper. Our results do not only apply to the deconvolution and demixing problem, but to recovery of column-sparse matrices in general. PubDate: 2017-04-10 DOI: 10.1007/s10444-017-9533-0

Authors:Roberto Iacono; John P. Boyd Abstract: Abstract The Lambert W-function is the solution to the transcendental equation W(x)e W(x) = x. It has two real branches, one of which, for x ∈ [−1/e, ∞], is usually denoted as the principal branch. On this branch, the function grows from − 1 to infinity, logarithmically at large x. The present work is devoted to the construction of accurate approximations for the principal branch of the W-function. In particular, a simple, global analytic approximation is derived that covers the whole branch with a maximum relative error smaller than 5 × 10−3. Starting from it, machine precision accuracy is reached everywhere with only three steps of a quadratically convergent iterative scheme, here examined for the first time, which is more efficient than standard Newton’s iteration at large x. Analytic bounds for W are also constructed, for x > e, which are much tighter than those currently available. It is noted that the exponential of the upper bounding function yields an upper bound for the prime counting function π(n) that is better than the well-known Chebyshev’s estimates at large n. Finally, the construction of accurate approximations to W based on Chebyshev spectral theory is discussed; the difficulties involved are highlighted, and methods to overcome them are presented. PubDate: 2017-04-01 DOI: 10.1007/s10444-017-9530-3

Authors:Lina Wang; Lijun Yi Abstract: Abstract We consider an h-p version of the continuous Petrov-Galerkin time stepping method for Volterra integro-differential equations with proportional delays. We derive a priori error bounds in the L 2-, H 1- and L ∞-norm that are explicit in the local time steps, the local approximation orders, and the local regularity of the exact solution. Numerical experiments are presented to illustrate the theoretical results. PubDate: 2017-03-27 DOI: 10.1007/s10444-017-9531-2

Authors:Paolo Ghelardoni; Cecilia Magherini Abstract: Abstract A matrix method for the solution of direct fractional Sturm-Liouville problems (SLPs) on bounded domains is proposed where the fractional derivative is defined in the Riesz sense. The scheme is based on the application of the Galerkin spectral method of orthogonal polynomials. The order of convergence of the eigenvalue approximations with respect to the matrix size is studied. Some numerical examples that confirm the theory and prove the competitiveness of the approach are finally presented. PubDate: 2017-03-24 DOI: 10.1007/s10444-017-9529-9

Authors:Wenwu Gao; Zongmin Wu Abstract: Abstract The paper provides an approach for constructing multivariate radial kernels satisfying higher-order generalized Strang-Fix conditions from a given univariate generator. There are three key features of the approach. First, the kernels are explicitly expressed only by the derivatives of the f-form of the generator without computing any Fourier transforms. Second, it includes the radial kernels with the highest-order generalized Strang-Fix conditions. Finally, it requires only computing univariate derivatives of the f-form. Therefore, the approach is simple, efficient and easy to implement. As examples, the paper constructs radial kernels from some commonly used generators, including the Gaussian functions, the inverse multiquadric functions and compactly supported positive definite functions. PubDate: 2017-03-24 DOI: 10.1007/s10444-017-9528-x

Authors:Lin Mu; Xiu Ye Abstract: Abstract The goal of this paper is to introduce a simple finite element method to solve the Stokes equations. This method is in primal velocity-pressure formulation and is so simple such that both velocity and pressure are approximated by piecewise constant functions. Implementation issues as well as error analysis are investigated. A basis for a divergence free subspace of the velocity field is constructed so that the original saddle point problem can be reduced to a symmetric and positive definite system with much fewer unknowns. The numerical experiments indicate that the method is accurate. PubDate: 2017-03-21 DOI: 10.1007/s10444-017-9526-z

Authors:Ghulam Mustafa; Rabia Hameed Abstract: Abstract Families of parameter dependent univariate and bivariate subdivision schemes are presented in this paper. These families are new variants of the Lane-Riesenfeld algorithm. So the subdivision algorithms consist of both refining and smoothing steps. In refining step, we use the quartic B-spline based subdivision schemes. In smoothing step, we average the adjacent points. The bivariate schemes are the non-tensor product version of our univariate schemes. Moreover, for odd and even number of smoothing steps, we get the primal and dual schemes respectively. Higher regularity of the schemes can be achieved by increasing the number of smoothing steps. These schemes can be nicely generalized to contain local shape parameters that allow the user to adjust locally the shape of the limit curve/surface. PubDate: 2017-03-13 DOI: 10.1007/s10444-017-9519-y

Authors:Pietro Dell’Acqua Abstract: Abstract In recent years, several efforts were made in order to introduce boundary conditions for deblurring problems that allow to get accurate reconstructions. This resulted in the birth of Reflective, Anti-Reflective and Mean boundary conditions, which are all based on the idea of guaranteeing the continuity of the signal/image outside the boundary. Here we propose new boundary conditions that are obtained by suitably combining Taylor series and finite difference approximations. Moreover, we show that also Anti-Reflective and Mean boundary conditions can be attributed to the same framework. Numerical results show that, in case of low levels of noise and blurs able to perform a suitable smoothing effect on the original image (e.g. Gaussian blur), the proposed boundary conditions lead to a significant improvement of the restoration accuracy with respect to those available in the literature. PubDate: 2017-03-10 DOI: 10.1007/s10444-017-9525-0