Authors:A. Arrarás; K. J. in ’t Hout; W. Hundsdorfer; L. Portero Pages: 261 - 285 Abstract: We present modifications of the second-order Douglas stabilizing corrections method, which is a splitting method based on the implicit trapezoidal rule. Inclusion of an explicit term in a forward Euler way is straightforward, but this will lower the order of convergence. In the modifications considered here, explicit terms are included in a second-order fashion. For these modified methods, results on linear stability and convergence are derived. Stability holds for important classes of reaction–diffusion equations, and for such problems the modified Douglas methods are seen to be often more efficient than related methods from the literature. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0634-9 Issue No:Vol. 57, No. 2 (2017)

Authors:Zhong-Zhi Bai; Michele Benzi Pages: 287 - 311 Abstract: We propose a class of regularized Hermitian and skew-Hermitian splitting methods for the solution of large, sparse linear systems in saddle-point form. These methods can be used as stationary iterative solvers or as preconditioners for Krylov subspace methods. We establish unconditional convergence of the stationary iterations and we examine the spectral properties of the corresponding preconditioned matrix. Inexact variants are also considered. Numerical results on saddle-point linear systems arising from the discretization of a Stokes problem and of a distributed control problem show that good performance can be achieved when using inexact variants of the proposed preconditioners. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0636-7 Issue No:Vol. 57, No. 2 (2017)

Authors:John C. Butcher; Gulshad Imran; Helmut Podhaisky Pages: 313 - 328 Abstract: G-symplectic methods are an alternative to symplectic Runge–Kutta in that they have similar numerical behaviour but are less expensive computationally. In this paper, a new method is derived which is symmetric, G-symplectic, has zero parasitic growth factors and has order 6. Although there are five stages, two of these are explicit and the remaining three are diagonally implicit. The method is multivalue, with four quantities passed from step to step. No drift in the variation of the Hamiltonian is observed in numerical experiments for long time intervals if the stepsize is sufficiently small. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0630-0 Issue No:Vol. 57, No. 2 (2017)

Authors:Catterina Dagnino; Sara Remogna Pages: 329 - 350 Abstract: The aim of this paper is to present spline methods for the numerical solution of integral equations on surfaces of \(\mathbb {R}^3\) , by using optimal superconvergent quasi-interpolants defined on type-2 triangulations and based on the Zwart–Powell quadratic box spline. In particular we propose a modified version of the classical collocation method and two spline collocation methods with high order of convergence. We also deal with the problem of approximating the surface. Finally, we study the approximation error of the above methods together with their iterated versions and we provide some numerical tests. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0633-x Issue No:Vol. 57, No. 2 (2017)

Authors:G. Huang; A. Lanza; S. Morigi; L. Reichel; F. Sgallari Pages: 351 - 378 Abstract: A new majorization–minimization framework for \(\ell _p\) – \(\ell _q\) image restoration is presented. The solution is sought in a generalized Krylov subspace that is build up during the solution process. Proof of convergence to a stationary point of the minimized \(\ell _p\) – \(\ell _q\) functional is provided for both convex and nonconvex problems. Computed examples illustrate that high-quality restorations can be determined with a modest number of iterations and that the storage requirement of the method is not very large. A comparison with related methods shows the competitiveness of the method proposed. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0643-8 Issue No:Vol. 57, No. 2 (2017)

Authors:Hao Ji; Yaohang Li Pages: 379 - 403 Abstract: In this paper, we analyze all possible situations of rank deficiency that cause breakdown in block conjugate gradient (BCG) solvers. A simple solution, breakdown-free block conjugate gradient (BFBCG), is designed to address the rank deficiency problem. The rationale of the BFBCG algorithm is to derive new forms of parameter matrices based on the potentially reduced search subspace to handle rank deficiency. Orthogonality properties and convergence of BFBCG in case of rank deficiency are justified accordingly with mathematical rigor. BFBCG yields faster convergence than restarting BCG when breakdown occurs. Numerical examples suffering from rank deficiency are provided to demonstrate the robustness of BFBCG. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0631-z Issue No:Vol. 57, No. 2 (2017)

Authors:Kent-André Mardal; Bjørn Fredrik Nielsen; Magne Nordaas Pages: 405 - 431 Abstract: Regularization robust preconditioners for PDE-constrained optimization problems have been successfully developed. These methods, however, typically assume observation data and control throughout the entire domain of the state equation. For many inverse problems, this is an unrealistic assumption. In this paper we propose and analyze preconditioners for PDE-constrained optimization problems with limited observation data, e.g. observations are only available at the boundary of the solution domain. Our methods are robust with respect to both the regularization parameter and the mesh size. That is, the condition number of the preconditioned optimality system is uniformly bounded, independently of the size of these two parameters. The method does, however, require extra regularity. We first consider a prototypical elliptic control problem and thereafter more general PDE-constrained optimization problems. Our theoretical findings are illuminated by several numerical results. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0635-8 Issue No:Vol. 57, No. 2 (2017)

Authors:Ross McKenzie; John Pryce Pages: 433 - 462 Abstract: The signature matrix structural analysis method developed by Pryce provides more structural information than the commonly used Pantelides method and applies to differential-algebraic equations (DAEs) of arbitrary order. It is useful to consider how existing methods using the Pantelides algorithm can benefit from such structural analysis. The dummy derivative method is a technique commonly used to solve DAEs that can benefit from such exploitation of underlying DAE structures and information found in the Signature Matrix method. This paper gives a technique to find structurally necessary dummy derivatives and how to use different block triangular forms effectively when performing the dummy derivative method and then provides a brief complexity analysis of the proposed approach. We finish by outlining an approach that can simplify the task of dummy pivoting. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0642-9 Issue No:Vol. 57, No. 2 (2017)

Authors:Kaspar Nipp; Daniel Stoffer Pages: 463 - 497 Abstract: It is well known that the stiff van der Pol equation has a strongly attractive limit cycle. In this paper it is shown that the Euler method applied to the van der Pol equation with small step size, small compared to the perturbation parameter, admits an attractive invariant closed curve close to the limit cycle. To describe closed curves in the vicinity of the limit cycle, 14 charts are introduced. A general graph transform result is derived and applied in these charts. The proof of the main result relies on the contraction principle in a suitable function space. Estimates are given for the distance of the invariant curve to the limit cycle. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0638-5 Issue No:Vol. 57, No. 2 (2017)

Authors:Rosemary A. Renaut; Michael Horst; Yang Wang; Douglas Cochran; Jakob Hansen Pages: 499 - 529 Abstract: The solution, \(\varvec{x}\) , of the linear system of equations \(A\varvec{x}\approx \varvec{b}\) arising from the discretization of an ill-posed integral equation \(g(s)=\int H(s,t) f(t) \,dt\) with a square integrable kernel H(s, t) is considered. The Tikhonov regularized solution \(\varvec{x}(\lambda )\) approximating the Galerkin coefficients of f(t) is found as the minimizer of \(J(\varvec{x})=\{ \Vert A \varvec{x} -\varvec{b}\Vert _2^2 + \lambda ^2 \Vert L \varvec{x}\Vert _2^2\}\) , where \(\varvec{b}\) is given by the Galerkin coefficients of g(s). \(\varvec{x}(\lambda )\) depends on the regularization parameter \(\lambda \) that trades off between the data fidelity and the smoothing norm determined by L, here assumed to be diagonal and invertible. The Galerkin method provides the relationship between the singular value expansion of the continuous kernel and the singular value decomposition of the discrete system matrix for square integrable kernels. We prove that the kernel maintains square integrability under left and right multiplication by bounded functions and thus the relationship also extends to appropriately weighted kernels. The resulting approximation of the integral equation permits examination of the properties of the regularized solution \(\varvec{x}(\lambda )\) independent of the sample size of the data. We prove that consistently down sampling both the system matrix and the data provides a small scale system that preserves the dominant terms of the right singular subspace of the system and can then be used to estimate the regularization parameter for the original system. When g(s) is directly measured via its Galerkin coefficients the regularization parameter is preserved across resolutions. For measurements of g(s) a scaling argument is required to move across resolutions of the systems when the regularization parameter is found using a regularization parameter estimation technique that depends on the knowledge of the variance in the data. Numerical results illustrate the theory and demonstrate the practicality of the approach for regularization parameter estimation using generalized cross validation, unbiased predictive risk estimation and the discrepancy principle applied to both the system of equations, and to the regularized system of equations. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0637-6 Issue No:Vol. 57, No. 2 (2017)

Authors:Hermann Schichl; Ferenc Domes; Tiago Montanher; Kevin Kofler Pages: 531 - 556 Abstract: This paper introduces interval union arithmetic, a new concept which extends the traditional interval arithmetic. Interval unions allow to manipulate sets of disjoint intervals and provide a natural way to represent the extended interval division. Considering interval unions lead to simplifications of the interval Newton method as well as of other algorithms for solving interval linear systems. This paper does not aim at describing the complete theory of interval union analysis, but rather at giving basic definitions and some fundamental properties, as well as showing theoretical and practical usefulness of interval unions in a few selected areas. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0632-y Issue No:Vol. 57, No. 2 (2017)

Authors:Xiaojie Wang; Ruisheng Qi; Fengze Jiang Pages: 557 - 585 Abstract: This article offers sharp spatial and temporal mean-square regularity results for a class of semi-linear parabolic stochastic partial differential equations (SPDEs) driven by infinite dimensional fractional Brownian motion with the Hurst parameter greater than one-half. In addition, the mean-square numerical approximations of such problems are investigated, performed by the spectral Galerkin method in space and the linear implicit Euler method in time. The obtained sharp regularity properties of the problems enable us to identify optimal mean-square convergence rates of the full discrete scheme. These theoretical findings are accompanied by several numerical examples. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0639-4 Issue No:Vol. 57, No. 2 (2017)

Authors:Chaoxia Yang Pages: 587 - 606 Abstract: We analyze linearly implicit BDF methods for the time discretization of a nonlinear parabolic interface problem, where the computational domain is divided into two subdomains by an interface, and the nonlinear diffusion coefficient is discontinuous across the interface. We prove optimal-order error estimates without assuming any growth conditions on the nonlinear diffusion coefficient and without restriction on the stepsize. Due to the existence of the interface and the lack of global Lipschitz continuity of the diffusion coefficient, we use a special type of test functions to analyze high-order \(A(\alpha )\) -stable BDF methods. Such test functions avoid any interface terms upon integration by parts and are used to derive error estimates in the piecewise \(H^2\) norm. PubDate: 2017-06-01 DOI: 10.1007/s10543-016-0641-x Issue No:Vol. 57, No. 2 (2017)

Authors:Caterina Fenu; Lothar Reichel; Giuseppe Rodriguez; Hassane Sadok Abstract: Tikhonov regularization is commonly used for the solution of linear discrete ill-posed problems with error-contaminated data. A regularization parameter that determines the quality of the computed solution has to be chosen. One of the most popular approaches to choosing this parameter is to minimize the Generalized Cross Validation (GCV) function. The minimum can be determined quite inexpensively when the matrix A that defines the linear discrete ill-posed problem is small enough to rapidly compute its singular value decomposition (SVD). We are interested in the solution of linear discrete ill-posed problems with a matrix A that is too large to make the computation of its complete SVD feasible, and show how upper and lower bounds for the numerator and denominator of the GCV function can be determined fairly inexpensively for large matrices A by computing only a few of the largest singular values and associated singular vectors of A. These bounds are used to determine a suitable value of the regularization parameter. Computed examples illustrate the performance of the proposed method. PubDate: 2017-05-18 DOI: 10.1007/s10543-017-0662-0

Authors:Ching-Sung Liu; Che-Rung Lee Abstract: In this paper, we present the inexact structure preserving Arnoldi methods for structured eigenvalue problems. They are called structure preserving because the computed eigenvalues and eigenvectors can preserve the desirable properties of the structures of the original matrices, even with large errors involved in the computation of matrix-vector products. A backward error matrix is called structured if it has the same structure as the original matrix. We derive a common form for the structured backward errors that can be used for different structure preserving processes, and prove the derived form has the minimum Frobenius norm among all possible backward errors. Furthermore, we employ the derived backward errors for some specific structure preserving processes to estimate the accuracy of the solutions obtained by inexact Arnoldi methods for eigenvalue problems. We aim to give, wherever possible, formulae that are inexpensive to compute so that they can be used routinely in practice. Numerical experiments are provided to support the theoretical results. PubDate: 2017-05-08 DOI: 10.1007/s10543-017-0660-2

Authors:Jin Zhang; Xiaowei Liu Abstract: In this paper, we present a pointwise convergence analysis for a streamline diffusion finite element method (SDFEM) on a Shishkin triangular mesh. We prove that the method is uniformly convergent with a pointwise accuracy of order almost 7/4 (up to a logarithmic factor) away from the subdomain where the layers intersect. Finally, numerical experiments support our theoretical results. PubDate: 2017-05-08 DOI: 10.1007/s10543-017-0661-1

Authors:Davoud Mirzaei Abstract: In this paper a direct approximation method on the sphere, constructed by generalized moving least squares, is presented and analyzed. It is motivated by numerical solution of partial differential equations on spheres and other manifolds. The new method generalizes the finite difference methods, someway, for scattered data points on each local subdomain. As an application, the Laplace–Beltrami equation is solved and the theoretical and experimental results are given. The new approach eliminates some drawbacks of the previous methods. PubDate: 2017-05-03 DOI: 10.1007/s10543-017-0659-8

Authors:Marko Lange; Siegfried M. Rump Abstract: Standard Wilkinson-type error estimates of floating-point algorithms involve a factor \(\gamma _k:=k\mathbf {u}/(1-k\mathbf {u})\) for \(\mathbf {u}\) denoting the relative rounding error unit of a floating-point number system. Recently, it was shown that, for many standard algorithms such as matrix multiplication, LU- or Cholesky decomposition, \(\gamma _k\) can be replaced by \(k\mathbf {u}\) , and the restriction on k can be removed. However, the arguments make heavy use of specific properties of both the underlying set of floating-point numbers and the corresponding arithmetic. In this paper, we derive error estimates for the summation of real numbers where each sum is afflicted with some perturbation. Recent results on floating-point summation follow as a corollary, in particular error estimates for rounding to nearest and for directed rounding. Our new estimates are sharp and unveil the necessary properties of floating-point schemes to allow for a priori estimates of summation with a factor omitting higher order terms. PubDate: 2017-05-03 DOI: 10.1007/s10543-017-0658-9

Authors:Tiago Montanher; Ferenc Domes; Hermann Schichl; Arnold Neumaier Abstract: An interval union is a finite set of closed and disjoint intervals. In this paper we introduce the interval union Gauss–Seidel procedure to rigorously enclose the solution set of linear systems with uncertainties given by intervals or interval unions. We also present the interval union midpoint and Gauss–Jordan preconditioners. The Gauss–Jordan preconditioner is used in a mixed strategy to improve the quality and efficiency of the algorithm. Numerical experiments on interval linear systems generated at random show the capabilities of our approach. PubDate: 2017-04-22 DOI: 10.1007/s10543-017-0657-x

Authors:Georg Muntingh Abstract: Pseudo-splines form a family of subdivision schemes that provide a natural blend between interpolating schemes and approximating schemes, including the Dubuc–Deslauriers schemes and B-spline schemes. Using a generating function approach, we derive expressions for the symbols of the symmetric m-ary pseudo-spline subdivision schemes. We show that their masks have positive Fourier transform, making it possible to compute the exact Hölder regularity algebraically as a logarithm of the spectral radius of a matrix. We apply this method to compute the regularity explicitly in some special cases, including the symmetric binary, ternary, and quarternary pseudo-spline schemes. PubDate: 2017-04-13 DOI: 10.1007/s10543-017-0656-y