The parallel solution of dense saddle-point linear systems arising in stochastic programming

Abstract

We present a novel approach for solving dense saddle-point linear systems in a distributed-memory environment. This work is motivated by an application in stochastic optimization problems with recourse, but the proposed approach can be used for a large family of dense saddle-point systems, in particular, for those arising in convex programming. Although stochastic optimization problems have many important applications, they can present serious computational difficulties. In particular, sample average approximation (SAA) problems with a large number of samples are often too big to solve on a single shared-memory system. Recent work has developed interior-point methods and specialized linear algebra to solve these problems in parallel, using a scenario-based decomposition that distributes the data, and work across computational nodes. Even for sparse SAA problems, the decomposition produces a dense and possibly very large saddle-point linear system that must be solved repeatedly. We developed a specialized parallel factorization procedure for these systems, together with a streamlined method for assembling the distributed dense matrix. Strong scaling tests indicate over 90% efficiency on 1024 cores on a stochastic unit commitment problem with 57 million variables. Stochastic unit commitment problems with up to 189 million variables are solved efficiently on up to 2048 cores.

Keywords:

• stochastic programming
• parallel computing
• parallel dense linear algebra
• saddle-point

AMS Subject Classification :

• 90C15
• 65F05
• 68W10

Acknowledgements

We are grateful to Jack Poulson, the main developer of Elemental, for his guidance in both implementation and development of the factorization procedure, and to Peter Strazdins for informative discussions. This work was supported by the US Department of Energy under contract DE-AC02-06CH11357.