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:Yuji Nakatsukasa Abstract: The standard approach to computing an approximate SVD of a large-scale matrix is to project it onto lower-dimensional trial subspaces from both sides, compute the SVD of the small projected matrix, and project it back to the original space. This results in a low-rank approximate SVD to the original matrix, and we can then obtain approximate left and right singular subspaces by extracting subsets from the approximate SVD. In this work we assess the quality of the extraction process in terms of the accuracy of the approximate singular subspaces, measured by the angle between the exact and extracted subspaces (relative to the angle between the exact and trial subspaces). The main message is that the extracted approximate subspaces are optimal usually to within a modest constant. PubDate: 2017-06-19 DOI: 10.1007/s10543-017-0665-x

Authors:M. Irene Falcão; Fernando Miranda; Ricardo Severino; M. Joana Soares Abstract: In this paper we focus on computational aspects associated with polynomial problems in the ring of one-sided quaternionic polynomials. The complexity and error bounds of quaternion arithmetic are considered and several evaluation schemes are analyzed from their complexity point of view. The numerical stability of generalized Horner’s and Goertzel’s algorithms to evaluate polynomials with quaternion floating-point coefficients is addressed. Numerical tests illustrate the behavior of the algorithms from the point of view of performance and accuracy. PubDate: 2017-06-19 DOI: 10.1007/s10543-017-0667-8

Authors:Mohammad Asadzadeh; Christoffer Standar Abstract: This paper concerns a posteriori error analysis for the streamline diffusion (SD) finite element method for the one and one-half dimensional relativistic Vlasov–Maxwell system. The SD scheme yields a weak formulation, that corresponds to an add of extra diffusion to, e.g. the system of equations having hyperbolic nature, or convection-dominated convection diffusion problems. The a posteriori error estimates rely on dual formulations and yield error controls based on the computable residuals. The convergence estimates are derived in negative norms, where the error is split into an iteration and an approximation error and the iteration procedure is assumed to converge. PubDate: 2017-06-16 DOI: 10.1007/s10543-017-0666-9

Authors:Xinyan Niu; Jianbo Cui; Jialin Hong; Zhihui Liu Abstract: We construct stochastic pseudo-symplectic methods and analyze their pseudo-symplectic orders for stochastic Hamiltonian systems with additive noises in this paper. All of these methods are explicit so that the numerical implementations become much easier than implicit methods. Through the numerical experiments, we find that these methods have desired properties in accuracy and stability as well as the preservation of the symplectic structure of the systems. PubDate: 2017-06-15 DOI: 10.1007/s10543-017-0668-7

Authors:Tomoaki Okayama Abstract: A Sinc-collocation method was proposed by Stenger, who also gave a theoretical analysis of the method in the case of a “scalar” equation. This paper extends the theoretical results to the case of a “system” of equations. Furthermore, this paper proposes a more efficient method by replacing the variable transformation employed in Stenger’s method. The efficiency was confirmed by both a theoretical analysis and some numerical experiments. In addition to the existing and newly proposed Sinc-collocation methods, this paper also gives similar theoretical results for the Sinc-Nyström methods proposed by Nurmuhammad et al. In terms of computational cost, the newly proposed Sinc-collocation method is the most efficient among these methods. PubDate: 2017-06-08 DOI: 10.1007/s10543-017-0663-z

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