%0 Journal Article
%J Optimization Methods and Software
%D 2011
%T The Parallel Solution of Dense Saddle-Point Linear Systems Arising in Stochastic Programming
%A M. Lubin
%A C. G. Petra
%A Mihai Anitescu
%X 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.
%B Optimization Methods and Software
%8 10/2011
%G eng
%U http://www.tandfonline.com/doi/abs/10.1080/10556788.2011.602976
%1 http://www.mcs.anl.gov/papers/denseLA.pdf