A Framework for the Solution of Tree-Coupled Saddle-Point Systems

2024/10/30 by Hansknecht, Christoph, Heinzelreiter, Bernhard, Pearson, John W. +1 · 1 citation
#FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2410.23385

Abstract

We consider the solution of saddle-point systems with a tree-based block structure, introducing a parallelizable direct method for their solution. As our key contribution, we then propose several structure-exploiting preconditioners to be used during applications of the MINRES and GMRES algorithms and analyze their properties. We adapt several concepts originating in the field of multigrid methods, obtaining a variety of problem-adapted multi-level methods. We analyze the complexity of all algorithms, and derive a number of results on eigenvalues of the preconditioned system and convergence of iterative methods. We validate our theoretical findings through a range of numerical experiments.

Cited by

• Rake-Compress Riccati Recursions for Parallel Scenario-Tree Model Predictive Control

Related

• Symbol based convergence analysis in multigrid methods for saddle point problems
• On Symmetric Positive Definite Preconditioners for Multiple Saddle-Point Systems
• A preconditioned iteration method for solving saddle point problems
• Variants of the PSS preconditioner for generalized saddle point problems from the Navier-Stokes equations
• A new relaxed HSS preconditioner for saddle point problems