More Like this

1. Comparisons of some iterative algorithms for Biot equations

   Mingchao, Cai; Guoping, Zhang (January 2017, International journal of evolution equations)

   In this paper, we aim at solving the Biot model under stabilized finite element discretizations. To solve the resulting generalized saddle point linear systems, some iterative methods are proposed and compared. In the first method, we apply the GMRES algorithm as the outer iteration. In the second method, the Uzawa method with variable relaxation parameters is employed as the outer iteration method. In the third approach, Uzawa method is treated as a fixed-point iteration, the outer solver is the so-called Anderson acceleration. In all these methods, the inner solvers are preconditioners for the generalized saddle point problem. In the preconditioners, the Schur complement approximation is derived by using Fourier analysis approach. These preconditioners are implemented exactly or inexactly. Extensive experiments are given to justify the performance of the proposed preconditioners and to compare all the algorithms. 

   more » « less
2. Transformed primal-dual methods for nonlinear saddle point systems

   https://doi.org/10.1515/jnma-2022-0056  

   Chen, Long; Wei, Jingrong (January 2023, Journal of Numerical Mathematics)

   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
3. Stable Heteroclinic Channel-Based Movement Primitives: Tuning Trajectories Using Saddle Parameters

   https://doi.org/10.3390/app14062523  

   Rouse, Natasha; Daltorio, Kathryn (March 2024, Applied Sciences)

   Dynamic systems which underlie controlled systems are expected to increase in complexity as robots, devices, and connected networks become more intelligent. While classical stable systems converge to a stable point (a sink), another type of stability is to consider a stable path rather than a single point. Such stable paths can be made of saddle points that draw in trajectories from certain regions, and then push the trajectory toward the next saddle point. These chains of saddles are called stable heteroclinic channels (SHCs) and can be used in robotic control to represent time sequences. While we have previously shown that each saddle is visualizable as a trajectory waypoint in phase space, how to increase the fidelity of the trajectory was unclear. In this paper, we hypothesized that the waypoints can be individually modified to locally vary fidelity. Specifically, we expected that increasing the saddle value (ratio of saddle eigenvalues) causes the trajectory to slow to more closely approach a particular saddle. Combined with other parameters that control speed and magnitude, a system expressed with an SHC can be modified locally, point by point, without disrupting the rest of the path, supporting their use in motion primitives. While some combinations can enable a trajectory to better reach into corners, other combinations can rotate, distort, and round the trajectory surrounding the modified saddle. Of the system parameters, the saddle value provides the most predictable tunability across 3 orders of magnitude. 

   more » « less
4. A Schur Complement Cheeger Inequality

   https://doi.org/10.4230/LIPIcs.ITCS.2019.65  

   Schild, Aaron (January 2019, 10th Innovations in Theoretical Computer Science Conference)

   Cheeger's inequality shows that any undirected graph G with minimum normalized Laplacian eigenvalue lambda_G has a cut with conductance at most O(sqrt{lambda_G}). Qualitatively, Cheeger's inequality says that if the mixing time of a graph is high, there is a cut that certifies this. However, this relationship is not tight, as some graphs (like cycles) do not have cuts with conductance o(sqrt{lambda_G}). To better approximate the mixing time of a graph, we consider a more general object. Specifically, instead of bounding the mixing time with cuts, we bound it with cuts in graphs obtained by Schur complementing out vertices from the graph G. Combinatorially, these Schur complements describe random walks in G restricted to a subset of its vertices. As a result, all Schur complement cuts have conductance at least Omega(lambda_G). We show that unlike with cuts, this inequality is tight up to a constant factor. Specifically, there is a Schur complement cut with conductance at most O(lambda_G). 

   more » « less
5. Uniform block-diagonal preconditioners for divergence-conforming HDG Methods for the generalized Stokes equations and the linear elasticity equations

   https://doi.org/10.1093/imanum/drac021  

   Fu, Guosheng; Kuang, Wenzheng (June 2022, IMA Journal of Numerical Analysis)

   Abstract We propose a uniform block-diagonal preconditioner for condensed $$H$$(div)-conforming hybridizable discontinuous Galerkin schemes for parameter-dependent saddle point problems, including the generalized Stokes equations and the linear elasticity equations. An optimal preconditioner is obtained for the stiffness matrix on the global velocity/displacement space via the auxiliary space preconditioning technique (Xu (1994) The Auxiliary Space Method and Optimal Multigrid Preconditioning Techniques for Unstructured Grids, vol. 56. International GAMM-Workshop on Multi-level Methods (Meisdorf), pp. 215–235). A spectrally equivalent approximation to the Schur complement on the element-wise constant pressure space is also constructed, and an explicit computable exact inverse is obtained via the Woodbury matrix identity. Finally, the numerical results verify the robustness of our proposed preconditioner with respect to model parameters and mesh size. 

   more » « less