An official website of the United States government
Abstract A transformed primal-dual (TPD) flow is developed for a class of nonlinear smooth saddle point system. The flow for the dual variable contains a Schur complement which is strongly convex. Exponential stability of the saddle point is obtained by showing the strong Lyapunov property. Several TPD iterations are derived by implicit Euler, explicit Euler, implicit-explicit and Gauss-Seidel methods with accelerated overrelaxation of the TPD flow. Generalized to the symmetric TPD iterations, linear convergence rate is preserved for convex-concave saddle point systems under assumptions that the regularized functions are strongly convex. The effectiveness of augmented Lagrangian methods can be explained as a regularization of the non-strongly convexity and a preconditioning for the Schur complement. The algorithm and convergence analysis depends crucially on appropriate inner products of the spaces for the primal variable and dual variable. A clear convergence analysis with nonlinear inexact inner solvers is also developed.
more »
« less
Efficient and effective algebraic splitting‐based solvers for nonlinear saddle point problems
The incremental Picard Yosida (IPY) method has recently been developed as an iteration for nonlinear saddle point problems that is as effective as Picard but more efficient. By combining ideas from algebraic splitting of linear saddle point solvers with incremental Picard‐type iterations and grad‐div stabilization, IPY improves on the standard Picard method by allowing for easier linear solves at each iteration—but without creating more total nonlinear iterations compared to Picard. This paper extends the IPY methodology by studying it together with Anderson acceleration (AA). We prove that IPY for Navier–Stokes and regularized Bingham fits the recently developed analysis framework for AA, which implies that AA improves the linear convergence rate of IPY by scaling the rate with the gain of the AA optimization problem. Numerical tests illustrate a significant improvement in convergence behavior of IPY methods from AA, for both Navier–Stokes and regularized Bingham.
more »
« less
- Award ID(s):
- 2011490
- PAR ID:
- 10482321
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Mathematical Methods in the Applied Sciences
- Volume:
- 47
- Issue:
- 1
- ISSN:
- 0170-4214
- Format(s):
- Medium: X Size: p. 451-474
- Size(s):
- p. 451-474
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)State-of-the-art seismic imaging techniques treat inversion tasks such as full-waveform inversion (FWI) and least-squares reverse time migration (LSRTM) as partial differential equation-constrained optimization problems. Due to the large-scale nature, gradient-based optimization algorithms are preferred in practice to update the model iteratively. Higher-order methods converge in fewer iterations but often require higher computational costs, more line-search steps, and bigger memory storage. A balance among these aspects has to be considered. We have conducted an evaluation using Anderson acceleration (AA), a popular strategy to speed up the convergence of fixed-point iterations, to accelerate the steepest-descent algorithm, which we innovatively treat as a fixed-point iteration. Independent of the unknown parameter dimensionality, the computational cost of implementing the method can be reduced to an extremely low dimensional least-squares problem. The cost can be further reduced by a low-rank update. We determine the theoretical connections and the differences between AA and other well-known optimization methods such as L-BFGS and the restarted generalized minimal residual method and compare their computational cost and memory requirements. Numerical examples of FWI and LSRTM applied to the Marmousi benchmark demonstrate the acceleration effects of AA. Compared with the steepest-descent method, AA can achieve faster convergence and can provide competitive results with some quasi-Newton methods, making it an attractive optimization strategy for seismic inversion.more » « less
-
Abstract This paper develops an efficient and robust solution technique for the steady Boussinesq model of non-isothermal flow using Anderson acceleration applied to a Picard iteration. After analyzing the fixed point operator associated with the nonlinear iteration to prove that certain stability and regularity properties hold, we apply the authors’ recently constructed theory for Anderson acceleration, which yields a convergence result for the Anderson accelerated Picard iteration for the Boussinesq system. The result shows that the leading term in the residual is improved by the gain in the optimization problem, but at the cost of additional higher order terms that can be significant when the residual is large. We perform numerical tests that illustrate the theory, and show that a 2-stage choice of Anderson depth can be advantageous. We also consider Anderson acceleration applied to the Newton iteration for the Boussinesq equations, and observe that the acceleration allows the Newton iteration to converge for significantly higher Rayleigh numbers that it could without acceleration, even with a standard line search.more » « less
-
The starting point of analysis of state space models is investigating existence, uniqueness and solution properties such as the semigroup property, and various formulas for the solutions. Several concepts such as the state transition matrix, the matrix exponential, the variations of constants formula (the Cauchy formula), the Peano-Baker series, and the Picard iteration are used to characterize solutions. In this note, a tutorial treatment is given where all of these concepts are shown to be various manifestations of a single abstract method, namely solving equations using an operator Neumann series involving the Volterra operator of forward integration. The matrix exponential, the Peano-Baker series, the Picard iteration, and the Cauchy formula can be "discovered" naturally from this Neumann series. The convergence of the series and iterations is a consequence of the key property of asymptotic nilpotence of the Volterra operator. This property is an asymptotic version of the nilpotence property of a strictly-lower-triangular matrix.more » « less
-
We present a GPU algorithm for deformable simulation. Our method offers good computational efficiency and penetration-free guarantee at the same time, which are not common with existing techniques. The main idea is an algorithmic integration of projective dynamics (PD) and incremental potential contact (IPC). PD is a position-based simulation framework, favored for its robust convergence and convenient implementation. We show that PD can be employed to handle the variational optimization with the interior point method e.g., IPC. While conceptually straightforward, this requires a dedicated rework over the collision resolution and the iteration modality to avoid incorrect collision projection with improved numerical convergence. IPC exploits a barrier-based formulation, which yields an infinitely large penalty when the constraint is on the verge of being violated. This mechanism guarantees intersection-free trajectories of deformable bodies during the simulation, as long as they are apart at the rest configuration. On the downside, IPC brings a large amount of nonlinearity to the system, making PD slower to converge. To mitigate this issue, we propose a novel GPU algorithm named A-Jacobi for faster linear solve at the global step of PD. A-Jacobi is based on Jacobi iteration, but it better harvests the computation capacity on modern GPUs by lumping several Jacobi steps into a single iteration. In addition, we also re-design the CCD root finding procedure by using a new minimum-gradient Newton algorithm. Those saved time budgets allow more iterations to accommodate stiff IPC barriers so that the result is both realistic and collision-free. Putting together, our algorithm simulates complicated models of both solids and shells on the GPU at an interactive rate or even in real time.more » « less
