Abstract  We present a novel approach for solving dense saddlepoint 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
saddlepoint systems, in particular 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 sharedmemory system. Recent work has developed interior
point methods and specialized linear algebra to solve these problems
in parallel. A Schurcomplement technique is used to obtain a
scenariobased decomposition that allows the data and the work to be
distributed across computational nodes. Even when sparse SAA problems
are solved, combining the results from the scenarios in many cases
produces a very large dense saddlepoint linear system, which 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.
