  


On the parallel solution of dense saddlepoint linear systems arising in stochastic programming
Miles Lubin(mlubinuchicago.edu) Abstract: We present a novel approach for solving dense saddlepoint linear systems in a distributedmemory 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, using a scenariobased decomposition that distributes the data and work across computational nodes. Even for sparse SAA problems, the decomposition produces a dense and possibly very large saddlepoint 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 1,024 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 2,048 cores. Keywords: stochastic programming, parallel computing, parallel dense linear algebra, saddlepoint Category 1: Stochastic Programming Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 3: Optimization Software and Modeling Systems (Parallel Algorithms ) Citation: Preprint ANL/MCSP17981010, Argonne National Laboratory, 2010. Download: [PDF] Entry Submitted: 10/26/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  