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:Giampaolo Mele; Elias Jarlebring Abstract: An efficient and robust restart strategy is important for any Krylov-based method for eigenvalue problems. The tensor infinite Arnoldi method (TIAR) is a Krylov-based method for solving nonlinear eigenvalue problems (NEPs). This method can be interpreted as an Arnoldi method applied to a linear and infinite dimensional eigenvalue problem where the Krylov basis consists of polynomials. We propose new restart techniques for TIAR and analyze efficiency and robustness. More precisely, we consider an extension of TIAR which corresponds to generating the Krylov space using not only polynomials, but also structured functions, which are sums of exponentials and polynomials, while maintaining a memory efficient tensor representation. We propose two restarting strategies, both derived from the specific structure of the infinite dimensional Arnoldi factorization. One restarting strategy, which we call semi-explicit TIAR restart, provides the possibility to carry out locking in a compact way. The other strategy, which we call implicit TIAR restart, is based on the Krylov–Schur restart method for the linear eigenvalue problem and preserves its robustness. Both restarting strategies involve approximations of the tensor structured factorization in order to reduce the complexity and the required memory resources. We bound the error introduced by some of the approximations in the infinite dimensional Arnoldi factorization showing that those approximations do not substantially influence the robustness of the restart approach. We illustrate the effectiveness of the approaches by applying them to solve large scale NEPs that arise from a delay differential equation and a wave propagation problem. The advantages in comparison to other restart methods are also illustrated. PubDate: 2017-07-13 DOI: 10.1007/s10543-017-0671-z
Authors:Patrick Zulian; Teseo Schneider; Kai Hormann; Rolf Krause Abstract: The discretization of the computational domain plays a central role in the finite element method. In the standard discretization the domain is triangulated with a mesh and its boundary is approximated by a polygon. The boundary approximation induces a geometry-related error which influences the accuracy of the solution. To control this geometry-related error, iso-parametric finite elements and iso-geometric analysis allow for high order approximation of smooth boundary features. We present an alternative approach which combines parametric finite elements with smooth bijective mappings leaving the choice of approximation spaces free. Our approach allows to represent arbitrarily complex geometries on coarse meshes with curved edges, regardless of the domain boundary complexity. The main idea is to use a bijective mapping for automatically warping the volume of a simple parameterization domain to the complex computational domain, thus creating a curved mesh of the latter. Numerical examples provide evidence that our method has lower approximation error for domains with complex shapes than the standard finite element method, because we are able to solve the problem directly on the exact domain without having to approximate it. PubDate: 2017-07-04 DOI: 10.1007/s10543-017-0669-6
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
Hybrid journal (It can contain Open Access articles)
[2355 journals]
