Optimization Online


Efficient Serial and Parallel Coordinate Descent Methods for Huge-Scale Truss Topology Design

Peter Richtarik(peter.richtarik***at***ed.ac.uk)
Martin Takac(m.takac***at***sms.ed.ac.uk)

Abstract: In this work we propose solving huge-scale instances of the truss topology design problem with coordinate descent methods. We develop four efficient codes: serial and parallel implementations of randomized and greedy rules for the selection of the variable (potential bar) to be updated in the next iteration. Both serial methods enjoy an O(n/k) iteration complexity guarantee, where n is the number of potential bars and k the iteration counter. Our parallel implementations, written in CUDA and running on a graphical processing unit (GPU), are capable of speedups of up to two orders of magnitude when compared to their serial counterparts. Numerical experiments were performed on instances with up to 30 million potential bars.

Keywords: coordinate descent, huge scale optimization, parallel programming, GPU, huge scale optimization

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Applications -- Science and Engineering (Civil and Environmental Engineering )

Citation: Technical Report ERGO 11-012, School of Mathematics, University of Edinburgh, June 2011

Download: [PDF]

Entry Submitted: 08/02/2011
Entry Accepted: 08/02/2011
Entry Last Modified: 08/02/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society