LANS Publications

"The Parallel Solution of Dense Saddle-Point Linear Systems Arising in Stochastic Programming"

M. Lubin, C. G. Petra, and M. Anitescu

Optimization Methods and Software, . Also Preprint ANL/MCS-P1798-1010

Preprint Version: [pdf]

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 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. A Schur-complement technique is used to obtain a
scenario-based 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 saddle-point 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