Karoline Horgmo Jæger, Aslak Tveito · Simula SpringerBriefs on computing · 2023
Abstract In mathematics, a common approach to solving a new problem is to break down the problem into sub-problems that you know how to solve and then try to glue the pieces together to yield a solution of the new problem. This approach is also very useful in software development; well-tested pieces of software can be glued together in order to obtain solutions to a wider class of problems. Operator splitting is a technique that illustrates this principle very well. Rather complex equations can be broken down into more familiar problems and solved individually. It’s a miracle that it works, but it does. And it’s no miracle because there are proofs of convergence. Anyway, we will illustrate operator splitting with two examples and then come back to this technique when the equations become more challenging.
Cited by 0Open access
Joost Vennekens, David Gilis, Marc Denecker · Lecture notes in computer science · 2004
Cited by 12Open access
Jürgen Geiser · edoc Publication server (Humboldt University of Berlin) · 2011
In this paper we describe a technique for closed formulation of an iterative operator-splitting method and embed the method in the classical exponential splitting methods. Since iterative operator splitting have been developed, an abstract framework to relate the method to other classical splitting methods is needed. Here an abstract framework considering the iterative splitting method as waveform-relaxation or ex- ponential splitting method is devised. This is achieved by basing the analysis on semi-groups and fixed-point schemes. Abstract results illustrate differential equations with constant and time- dependent coefficients.
Cited by 0Open access
Geiser, Jürgen · edoc Publication server (Humboldt University of Berlin) · 2011
In this paper we describe an iterative operator-splitting method for bounded operators. The contribution is a novel iterative method, that can be applied as a splitting method for ordinary and partial differential equations. A simple relation between the number of iterative steps and the order of the splitting scheme, can made it as an alternative method to consider it as a time decomposition method. The iterative splitting scheme is interested on physical problem, while the original problem is not divided as in standard splitting schemes. We present error bounds for the iterative splitting methods in the presence of bounded operators. We discuss efficient algorithms to compute the integral formulation of the splitting scheme. In experiments, we consider the benefits of the novel splitting method with respect to their number of iterations and time steps. Ordinary differential equations and convection-diffusion-reaction equations are presented in the numerical results.
Cited by 0Open access
Amir-Massoud Farahmand, Mohammad Ghavamzadeh, Amin Rakhsha et al. · 2022
Cited by 0
Amin Rakhsha, Andrew Wang, Mohammad Ghavamzadeh et al. · arXiv (Cornell University) · 2022
We introduce new planning and reinforcement learning algorithms for discounted MDPs that utilize an approximate model of the environment to accelerate the convergence of the value function. Inspired by the splitting approach in numerical linear algebra, we introduce Operator Splitting Value Iteration (OS-VI) for both Policy Evaluation and Control problems. OS-VI achieves a much faster convergence rate when the model is accurate enough. We also introduce a sample-based version of the algorithm called OS-Dyna. Unlike the traditional Dyna architecture, OS-Dyna still converges to the correct value function in presence of model approximation error.
Cited by 1Open access
Fabián Pedregosa, Gauthier Gidel · arXiv (Cornell University) · 2018
We propose and analyze an adaptive step-size variant of the Davis-Yin three operator splitting. This method can solve optimization problems composed by a sum of a smooth term for which we have access to its gradient and an arbitrary number of potentially non-smooth terms for which we have access to their proximal operator. The proposed method sets the step-size based on local information of the objective --hence allowing for larger step-sizes--, only requires two extra function evaluations per iteration and does not depend on any step-size hyperparameter besides an initial estimate. We provide an iteration complexity analysis that matches the best known results for the non-adaptive variant: sublinear convergence for general convex functions and linear convergence under strong convexity of the smooth term and smoothness of one of the proximal terms. Finally, an empirical comparison with related methods on 6 different problems illustrates the computational advantage of the proposed method.
Cited by 7Open access
K. Murawski, M. Goossens · Journal of Geophysical Research Atmospheres · 1994
Operator splitting and direct time integration of the ideal MHD equations are compared by using a finite difference flux‐corrected transport method. The comparison is made for impulsively generated nonlinear waves in a coronal plasma. It suggests that operator splitting and direct time integration both lead to physically acceptable results and provide a good agreement with results obtained with the fast Fourier transform method.
Cited by 4
Minh N. Bùi, Patrick L. Combettes · arXiv (Cornell University) · 2019
We establish the convergence of the forward-backward splitting algorithm based on Bregman distances for the sum of two monotone operators in reflexive Banach spaces. Even in Euclidean spaces, the convergence of this algorithm has so far been proved only in the case of minimization problems. The proposed framework features Bregman distances that vary over the iterations and a novel assumption on the single-valued operator that captures various properties scattered in the literature. In the minimization setting, we obtain rates that are sharper than existing ones.
Cited by 0Open access
Petra Csomós, Gregor Nickel · Computers & Mathematics with Applications · 2008
Cited by 16
Giorgos Stathopoulos, Harsh Shukla, Alexander Szűcs et al. · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2016
The significant progress that has been made in recent years both in hardware implementations and in numerical computing has rendered real-time optimization-based control a viable option when it comes to advanced industrial applications. More recently, the need for control of a process in the presence of a limited amount of hardware resources has triggered research in the direction of embedded optimization-based control. Operator Splitting Methods in Control focuses on systems with linear dynamics, giving rise to convex control problems. It provides a comprehensive survey of a family of first order methods known as decomposition schemes or operator splitting methods and shows the behavior of such algorithms as solvers of control related convex problems from tens to a few hundreds of variables. This compact survey gives the reader a state-of-the-art overview of the topic with examples of applications in aerospace and building control.
Cited by 25Open access
Xin Jiang, Lieven Vandenberghe · arXiv (Cornell University) · 2022
The paper presents primal-dual proximal splitting methods for convex optimization, in which generalized Bregman distances are used to define the primal and dual proximal update steps. The methods extend the primal and dual Condat-Vu algorithms and the primal-dual three-operator (PD3O) algorithm. The Bregman extensions of the Condat-Vu algorithms are derived from the Bregman proximal point method applied to a monotone inclusion problem. Based on this interpretation, a unified framework for the convergence analysis of the two methods is presented. We also introduce a line search procedure for stepsize selection in the Bregman dual Condat-Vu algorithm applied to equality-constrained problems. Finally, we propose a Bregman extension of PD3O and analyze its convergence.
Cited by 0Open access
Giorgos Stathopoulos, Harsh Shukla, Alexander Szűcs et al. · Foundations and Trends® in Systems and Control · 2016
The significant progress that has been made in recent years both in hardware implementations and in numerical computing has rendered real-time optimization-based control a viable option when it comes to advanced industrial applications. More recently, the need for control of a process in the presence of a limited amout of hardware resources has triggered research in the direction of embedded optimization-based control. At the same time, and standing at the other side of the spectrum, the field of big data has emerged, seeking for solutions to problems that classical optimization algorithms are incapable to provide. This triggered some interest to revisit the family of first order methods commonly known as decomposition schemes or operator splitting methods. Although it is established that splitting methods are quite beneficial when applied to large-scale problems, their potential in solving small to medium scale embedded optimization problems has not been studied so extensively. Our purpose is to study the behavior of such algorithms as solvers of control-related problems of that scale. Our effort focuses on identifying special characteristics of these problems and how they can be exploited by some popular splitting methods.
Cited by 31
Minh N. Bùi, Patrick L. Combettes · Set-Valued and Variational Analysis · 2020
Cited by 4Open access
Mitchell, Jonathan, Sumner, Jeremy, Holland, Barbara · Figshare · 2018
Online-only appendix describing the mathematical details of the splitting operator and how to generate rate matrices.
Cited by 0Open access
Rodney G. Downey, Richard A. Shore · Annals of Pure and Applied Logic · 1998
We investigate the relationship of (jumps of) the degrees of splittings of a computably enumerable set and the degree of the set. We prove that there is a high computably enumerable set whose only proper splittings are low2.
Cited by 9Open access
Vabiščevič, P.N.
Cited by 0
Rossitza S. Marinova, Tadayasu Takahashi, Hideaki Aiso et al. · Journal of Computational and Applied Mathematics · 2003
Cited by 2
Tassilo Kugelstadt, Dan Koschier, Jan Bender · Computer Graphics Forum · 2018
Abstract In this paper we present a novel operator splitting approach for corotated FEM simulations. The deformation energy of the corotated linear material model consists of two additive terms. The first term models stretching in the individual spatial directions and the second term describes resistance to volume changes. By formulating the backward Euler time integration scheme as an optimization problem, we show that the first term is invariant to rotations. This allows us to use an operator splitting approach and to solve both terms individually with different numerical methods. The stretching part is solved accurately with an optimization integrator, which can be done very efficiently because the system matrix is constant over time such that its Cholesky factorization can be precomputed. The volume term is solved approximately by using the compliant constraints method and Gauss‐Seidel iterations. Further, we introduce the analytic polar decomposition which allows us to speed up the extraction of the rotational part of the deformation gradient and to recover inverted elements. Finally, this results in an extremely fast and robust simulation method with high visual quality that outperforms standard corotated FEMs by more than two orders of magnitude and even the fast but inaccurate PBD and shape matching methods by more than one order of magnitude without having their typical drawbacks. This enables a very efficient simulation of complex scenes containing more than a million elements.
Cited by 33
Helge Holden, Kenneth H. Karlsen, Nils Henrik Risebro et al. · ArXiv.org · 2009
We provide a new analytical approach to operator splitting for equations of the type $u_t=Au+B(u)$ where $A$ is a linear operator and $B$ is quadratic. A particular example is the Korteweg-de Vries (KdV) equation $u_t-u u_x+u_{xxx}=0$. We show that the Godunov and Strang splitting methods converge with the expected rates if the initial data are sufficiently regular.
Cited by 0Open access