Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPseudo-linear Convergence of an Additive Schwarz Method for Dual Total Variation Minimization
297
0
0.0
(
0
)
Added by
Jongho Park
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Jongho Park
Ask ChatGPT about the research
No Arabic abstract
In this paper, we propose an overlapping additive Schwarz method for total variation minimization based on a dual formulation. The $O(1/n)$-energy convergence of the proposed method is proven, where $n$ is the number of iterations. In addition, we introduce an interesting convergence property called pseudo-linear convergence of the proposed method; the energy of the proposed method decreases as fast as linearly convergent algorithms until it reaches a particular value. It is shown that such the particular value depends on the overlapping width $delta$, and the proposed method becomes as efficient as linearly convergent algorithms if $delta$ is large. As the latest domain decomposition methods for total variation minimization are sublinearly convergent, the proposed method outperforms them in the sense of the energy decay. Numerical experiments which support our theoretical results are provided.
rate research
Read More
This paper gives a unified convergence analysis of additive Schwarz methods for general convex optimization problems. Resembling to the fact that additive Schwarz methods for linear problems are preconditioned Richardson methods, we prove that additive Schwarz methods for general convex optimization are in fact gradient methods. Then an abstract framework for convergence analysis of additive Schwarz methods is proposed. The proposed framework applied to linear elliptic problems agrees with the classical theory. We present applications of the proposed framework to various interesting convex optimization problems such as nonlinear elliptic problems, nonsmooth problems, and nonsharp problems.
The discretization of surface intrinsic PDEs has challenges that one might not face in the flat space. The closest point method (CPM) is an embedding method that represents surfaces using a function that maps points in the flat space to their closest points on the surface. This mapping brings intrinsic data onto the embedding space, allowing us to numerically approximate PDEs by the standard methods in the tubular neighborhood of the surface. Here, we solve the surface intrinsic positive Helmholtz equation by the CPM paired with finite differences which usually yields a large, sparse, and non-symmetric system. Domain decomposition methods, especially Schwarz methods, are robust algorithms to solve these linear systems. While there have been substantial works on Schwarz methods, Schwarz methods for solving surface differential equations have not been widely analyzed. In this work, we investigate the convergence of the CPM coupled with Schwarz method on 1-manifolds in d-dimensional space of real numbers.
The randomized sparse Kaczmarz method was recently proposed to recover sparse solutions of linear systems. In this work, we introduce a greedy variant of the randomized sparse Kaczmarz method by employing the sampling Kaczmarz-Motzkin method, and prove its linear convergence in expectation with respect to the Bregman distance in the noiseless and noisy cases. This greedy variant can be viewed as a unification of the sampling Kaczmarz-Motzkin method and the randomized sparse Kaczmarz method, and hence inherits the merits of these two methods. Numerically, we report a couple of experimental results to demonstrate its superiority
In this article, we analyse the convergence behaviour and scalability properties of the one-level Parallel Schwarz method (PSM) for domain decomposition problems in which the boundaries of many subdomains lie in the interior of the global domain. Such problems arise, for instance, in solvation models in computational chemistry. Existing results on the scalability of the one-level PSM are limited to situations where each subdomain has access to the external boundary, and at most only two subdomains have a common overlap. We develop a systematic framework that allows us to bound the norm of the Schwarz iteration operator for domain decomposition problems in which subdomains may be completely embedded in the interior of the global domain and an arbitrary number of subdomains may have a common overlap.
This work is devoted to the development and analysis of a linearization algorithm for microscopic elliptic equations, with scaled degenerate production, posed in a perforated medium and constrained by the homogeneous Neumann-Dirichlet boundary conditions. This technique plays two roles: to guarantee the unique weak solvability of the microscopic problem and to provide a fine approximation in the macroscopic setting. The scheme systematically relies on the choice of a stabilization parameter in such a way as to guarantee the strong convergence in $H^1$ norm for both the microscopic and macroscopic problems. In the standard variational setting, we prove the $H^1$-type contraction at the micro-scale based on the energy method. Meanwhile, we adopt the classical homogenization result in line with corrector estimate to show the convergence of the scheme at the macro-scale. In the numerical section, we use the standard finite element method to assess the efficiency and convergence of our proposed algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
