Authors:Young Ok Choi; Johannes Tausch Pages: 473 - 493 Abstract: Since the fundamental solution for transient Stokes flow in three dimensions is complicated it is difficult to implement discretization methods for boundary integral formulations. We derive a representation of the Stokeslet and stresslet in terms of incomplete gamma functions and investigate the nature of the singularity of the single- and double layer potentials. Further, we give analytical formulas for the time integration and develop Galerkin schemes with tensor product piecewise polynomial ansatz functions. Numerical results demonstrate optimal convergence rates. PubDate: 2017-06-01 DOI: 10.1007/s10444-016-9493-9 Issue No:Vol. 43, No. 3 (2017)

Authors:Sergey Voronin; Per-Gunnar Martinsson Pages: 495 - 516 Abstract: The manuscript describes efficient algorithms for the computation of the CUR and ID decompositions. The methods used are based on simple modifications to the classical truncated pivoted QR decomposition, which means that highly optimized library codes can be utilized for implementation. For certain applications, further acceleration can be attained by incorporating techniques based on randomized projections. Numerical experiments demonstrate advantageous performance compared to existing techniques for computing CUR factorizations. PubDate: 2017-06-01 DOI: 10.1007/s10444-016-9494-8 Issue No:Vol. 43, No. 3 (2017)

Authors:Jintao Cui; Thirupathi Gudi Pages: 517 - 535 Abstract: In this article, we study a finite element approximation for a model free boundary plasma problem. Using a mixed approach (which resembles an optimal control problem with control constraints), we formulate a weak formulation and study the existence and uniqueness of a solution to the continuous model problem. Using the same setting, we formulate and analyze the discrete problem. We derive optimal order energy norm a priori error estimates proving the convergence of the method. Further, we derive a reliable and efficient a posteriori error estimator for the adaptive mesh refinement algorithm. Finally, we illustrate the theoretical results by some numerical examples. PubDate: 2017-06-01 DOI: 10.1007/s10444-016-9495-7 Issue No:Vol. 43, No. 3 (2017)

Authors:Erich Novak; Mario Ullrich; Henryk Woźniakowski; Shun Zhang Pages: 537 - 553 Abstract: We analyze univariate oscillatory integrals defined on the real line for functions from the standard Sobolev space \(H^{s} (\mathbb {R})\) and from the space \(C^{s}(\mathbb {R})\) with an arbitrary integer s ≥ 1. We find tight upper and lower bounds for the worst case error of optimal algorithms that use n function values. More specifically, we study integrals of the form 1 $$ I_{k}^{\varrho} (f) = {\int}_{\mathbb{R}} f(x) \,\mathrm{e}^{-i\,kx} \varrho(x) \, \mathrm{d} x\ \ \ \text{for}\ \ f\in H^{s}(\mathbb{R})\ \ \text{or}\ \ f\in C^{s}(\mathbb{R}) $$ with \(k\in {\mathbb {R}}\) and a smooth density function ρ such as \( \rho (x) = \frac {1}{\sqrt {2 \pi }} \exp (-x^{2}/2)\) . The optimal error bounds are \({\Theta }((n+\max (1, k ))^{-s})\) with the factors in the Θ notation dependent only on s and ϱ. PubDate: 2017-06-01 DOI: 10.1007/s10444-016-9496-6 Issue No:Vol. 43, No. 3 (2017)

Authors:Sui Tang Pages: 555 - 580 Abstract: We consider the problem of spatiotemporal sampling in a discrete infinite dimensional spatially invariant evolutionary process x (n) = A n x to recover an unknown convolution operator A given by a filter \(a \in \ell ^{1}(\mathbb {Z})\) and an unknown initial state x modeled as a vector in \(\ell ^{2}(\mathbb {Z})\) . Traditionally, under appropriate hypotheses, any x can be recovered from its samples on \(\mathbb {Z}\) and A can be recovered by the classical techniques of deconvolution. In this paper, we will exploit the spatiotemporal correlation and propose a new sampling scheme to recover A and x that allows us to sample the evolving states x,A x,⋯ ,A N−1 x on a sub-lattice of \(\mathbb {Z}\) , and thus achieve a spatiotemporal trade off. The spatiotemporal trade off is motivated by several industrial applications (Lu and Vetterli, 2249–2252, 2009). Specifically, we show that $\{x(m\mathbb {Z}), Ax(m\mathbb {Z}), \cdots , A^{N-1}x(m\mathbb {Z}): N \geq 2m\}$ contains enough information to recover a typical “low pass filter” a and x almost surely, thus generalizing the idea of the finite dimensional case in Aldroubi and Krishtal, arXiv:1412.1538 (2014). In particular, we provide an algorithm based on a generalized Prony method for the case when both a and x are of finite impulse response and an upper bound of their support is known. We also perform a perturbation analysis based on the spectral properties of the operator A and initial state x, and verify the results by several numerical experiments. Finally, we provide several other numerical techniques to stabilize the proposed method, with some examples to demonstrate the improvement. PubDate: 2017-06-01 DOI: 10.1007/s10444-016-9497-5 Issue No:Vol. 43, No. 3 (2017)

Authors:Q. T. Le Gia; I. H. Sloan; H. Wendland Pages: 581 - 606 Abstract: Because physical phenomena on Earth’s surface occur on many different length scales, it makes sense when seeking an efficient approximation to start with a crude global approximation, and then make a sequence of corrections on finer and finer scales. It also makes sense eventually to seek fine scale features locally, rather than globally. In the present work, we start with a global multiscale radial basis function (RBF) approximation, based on a sequence of point sets with decreasing mesh norm, and a sequence of (spherical) radial basis functions with proportionally decreasing scale centered at the points. We then prove that we can “zoom in” on a region of particular interest, by carrying out further stages of multiscale refinement on a local region. The proof combines multiscale techniques for the sphere from Le Gia, Sloan and Wendland, SIAM J. Numer. Anal. 48 (2010) and Applied Comp. Harm. Anal. 32 (2012), with those for a bounded region in ℝ d from Wendland, Numer. Math. 116 (2010). The zooming in process can be continued indefinitely, since the condition numbers of matrices at the different scales remain bounded. A numerical example illustrates the process. PubDate: 2017-06-01 DOI: 10.1007/s10444-016-9498-4 Issue No:Vol. 43, No. 3 (2017)

Authors:Vahagn Bayramyan; Hakop Hakopian Pages: 607 - 626 Abstract: In this paper we consider n-poised planar node sets, as well as more special ones, called G C n sets. For the latter sets each n-fundamental polynomial is a product of n linear factors as it always holds in the univariate case. A line ℓ is called k-node line for a node set \(\mathcal X\) if it passes through exactly k nodes. An (n + 1)-node line is called maximal line. In 1982 M. Gasca and J. I. Maeztu conjectured that every G C n set possesses necessarily a maximal line. Till now the conjecture is confirmed to be true for n ≤ 5. It is well-known that any maximal line M of \(\mathcal X\) is used by each node in \(\mathcal X\setminus M, \) meaning that it is a factor of the fundamental polynomial. In this paper we prove, in particular, that if the Gasca-Maeztu conjecture is true then any n-node line of G C n set \(\mathcal {X}\) is used either by exactly \(\binom {n}{2}\) nodes or by exactly \(\binom {n-1}{2}\) nodes. We prove also similar statements concerning n-node or (n − 1)-node lines in more general n-poised sets. This is a new phenomenon in n-poised and G C n sets. At the end we present a conjecture concerning any k-node line. PubDate: 2017-06-01 DOI: 10.1007/s10444-016-9499-3 Issue No:Vol. 43, No. 3 (2017)

Authors:A. Aimi; M. Diligenti; C. Guardasoni Pages: 627 - 651 Abstract: Time-dependent problems modeled by hyperbolic partial differential equations can be reformulated in terms of boundary integral equations and solved via the boundary element method. In this context, the analysis of damping phenomena that occur in many physics and engineering problems is a novelty. Starting from a recently developed energetic space-time weak formulation for the coupling of boundary integral equations and hyperbolic partial differential equations related to wave propagation problems, we consider here an extension for the damped wave equation in layered media. A coupling algorithm is presented, which allows a flexible use of finite element method and boundary element method as local discretization techniques. Stability and convergence, proved by energy arguments, are crucial in guaranteeing accurate solutions for simulations on large time intervals. Several numerical benchmarks, whose numerical results confirm theoretical ones, are illustrated and discussed. PubDate: 2017-06-01 DOI: 10.1007/s10444-016-9500-1 Issue No:Vol. 43, No. 3 (2017)

Authors:Z. Dadi Pages: 653 - 676 Abstract: We consider the system of delay differential equations (DDE) representing the models containing two cells with time-delayed connections. We investigate global, local stability and the bifurcations of the trivial solution under some generic conditions on the Taylor coefficients of the DDE. Regarding eigenvalues of the connection matrix as bifurcation parameters, we obtain codimension one bifurcations (including pitchfork, transcritical and Hopf bifurcation) and Takens-Bogdanov bifurcation as a codimension two bifurcation. For application purposes, this is important since one can now identify the possible asymptotic dynamics of the DDE near the bifurcation points by computing quantities which depend explicitly on the Taylor coefficients of the original DDE. Finally, we show that the analytical results agree with numerical simulations. PubDate: 2017-06-01 DOI: 10.1007/s10444-016-9501-0 Issue No:Vol. 43, No. 3 (2017)

Abstract: This paper studies inf-sup stable finite element discretizations of the evolutionary Navier–Stokes equations with a grad-div type stabilization. The analysis covers both the case in which the solution is assumed to be smooth and consequently has to satisfy nonlocal compatibility conditions as well as the practically relevant situation in which the nonlocal compatibility conditions are not satisfied. The constants in the error bounds obtained do not depend on negative powers of the viscosity. Taking into account the loss of regularity suffered by the solution of the Navier–Stokes equations at the initial time in the absence of nonlocal compatibility conditions of the data, error bounds of order \(\mathcal O(h^{2})\) in space are proved. The analysis is optimal for quadratic/linear inf-sup stable pairs of finite elements. Both the continuous-in-time case and the fully discrete scheme with the backward Euler method as time integrator are analyzed. PubDate: 2017-05-25

Authors:Caroline Moosmüller Abstract: We propose a new adaption of linear Hermite subdivision schemes to the manifold setting. Our construction is intrinsic, as it is based solely on geodesics and on the parallel transport operator of the manifold. The resulting nonlinear Hermite subdivision schemes are analyzed with respect to convergence and C 1 smoothness. Similar to previous work on manifold-valued subdivision, this analysis is carried out by proving that a so-called proximity condition is fulfilled. This condition allows to conclude convergence and smoothness properties of the manifold-valued scheme from its linear counterpart, provided that the input data are dense enough. Therefore the main part of this paper is concerned with showing that our nonlinear Hermite scheme is “close enough”, i.e., in proximity, to the linear scheme it is derived from. PubDate: 2017-05-16 DOI: 10.1007/s10444-017-9516-1

Authors:Liqun Wang; Songming Hou; Liwei Shi Abstract: Elliptic interface problems with multi-domains have wide applications in engineering and science. However, it is challenging for most existing methods to solve three-dimensional elliptic interface problems with multi-domains due to local geometric complexity, especially for problems with matrix coefficient and sharp-edged interface. There are some recent work in two dimensions for multi-domains and in three dimensions for two domains. However, the extension to three dimensional multi-domain elliptic interface problems is non-trivial. In this paper, we present an efficient non-traditional finite element method with non-body-fitting grids for three-dimensional elliptic interface problems with multi-domains. Numerical experiments show that this method achieves close to second order accurate in the L ∞ norm for piecewise smooth solutions. PubDate: 2017-05-12 DOI: 10.1007/s10444-017-9539-7

Authors:Robert Stephen Jones Abstract: The classic eigenvalue problem of the Laplace operator inside a variety of polygons is numerically solved by using a method nearly identical to that used by Fox, Henrici, and Moler in their 1967 paper. It is demonstrated that such eigenvalue calculations can be extended to unprecedented precision, often to well over a hundred digits, or even thousands of digits. To work well, geometric symmetry must be exploited. The de-symmetrized fundamental domains (usually triangular) considered here have at most one non-analytic vertex. Dirichlet, Neumann, and periodic-type edge conditions are independently imposed on each symmetry-reduced polygon edge. The method of particular solutions is used whereby an eigenfunction is expanded in an N-term Fourier-Bessel series about the non-analytic vertex and made to match at a set of N points on the boundary. Under the right conditions, the so-called point-matching determinant has roots that approximate eigenvalues. A key observation is that by increasing the number of terms in the expansion, the approximate eigenvalue may be made to alternate above and below, while approaching what is presumed to be the exact eigenvalue. This alternation effectively provides a new method to bound eigenvalues, by inspection. Specific examples include Dirichlet and Neumann eigenvalues within polygons with re-entrant angles (L-shape, cut-square, 5-point star) and the regular polygons. Thousand-digit results are reported for the lowest Dirichlet eigenvalues of the L-shape, and regular pentagon and hexagon. PubDate: 2017-05-02 DOI: 10.1007/s10444-017-9527-y

Authors:Chang-Yeol Jung; Thien Binh Nguyen Abstract: The two-dimensional Riemann problem with polytropic gas is considered. By a restriction on the constant states of each quadrant of the computational domain such that there is only one planar centered wave connecting two adjacent quadrants, there are nineteen genuinely different initial configurations of the problem. The configurations are numerically simulated on a fine grid and compared by the 5th-order WENO-Z5, 6th-order WENO-ðœƒ6, and 7th-order WENO-Z7 schemes. The solutions are very well approximated with high resolution of waves interactions phenomena and different types of Mach shock reflections. Kelvin-Helmholtz instability-like secondary-scaled vortices along contact continuities are well resolved and visualized. Numerical solutions show that WENO-ðœƒ6 outperforms the comparing WENO-Z5 and WENO-Z7 in terms of shock capturing and small-scaled vortices resolution. A catalog of the numerical solutions of all nineteen configurations obtained from the WENO-ðœƒ6 scheme is listed. Thanks to their excellent resolution and sharp shock capturing, the numerical solutions presented in this work can be served as reference solutions for both future numerical and theoretical analyses of the 2D Riemann problem. PubDate: 2017-04-24 DOI: 10.1007/s10444-017-9538-8

Authors:Mingchao Cai; Peiqi Huang; Mo Mu Abstract: In this work, several multilevel decoupled algorithms are proposed for a mixed Navier-Stokes/Darcy model. These algorithms are based on either successively or parallelly solving two linear subdomain problems after solving a coupled nonlinear coarse grid problem. Error estimates are given to demonstrate the approximation accuracy of the algorithms. Experiments based on both the first order and the second order discretizations are presented to show the effectiveness of the decoupled algorithms. PubDate: 2017-04-20 DOI: 10.1007/s10444-017-9537-9

Authors:Gary Pui-Tung Choi; Lok Ming Lui Abstract: Surface parameterization is widely used in computer graphics and geometry processing. It simplifies challenging tasks such as surface registrations, morphing, remeshing and texture mapping. In this paper, we present an efficient algorithm for computing the disk conformal parameterization of simply-connected open surfaces. A double covering technique is used to turn a simply-connected open surface into a genus-0 closed surface, and then a fast algorithm for parameterization of genus-0 closed surfaces can be applied. The symmetry of the double covered surface preserves the efficiency of the computation. A planar parameterization can then be obtained with the aid of a Möbius transformation and the stereographic projection. After that, a normalization step is applied to guarantee the circular boundary. Finally, we achieve a bijective disk conformal parameterization by a composition of quasi-conformal mappings. Experimental results demonstrate a significant improvement in the computational time by over 60%. At the same time, our proposed method retains comparable accuracy, bijectivity and robustness when compared with the state-of-the-art approaches. Applications to texture mapping are presented for illustrating the effectiveness of our proposed algorithm. PubDate: 2017-04-20 DOI: 10.1007/s10444-017-9536-x

Authors:Tahar Z. Boulmezaoud; Keltoum Kaliche; Nabil Kerdid 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: 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: 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: 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