### 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

cores.