Efficient high-precision dense matrix algebra on parallel architectures for nonlinear discrete optimization
Abstract: We provide a proof point for the idea that matrix-based algorithms for discrete optimization problems, mainly conceived for proving theoretical efficiency, can be easily and efficiently implemented on massively-parallel architectures by exploiting scalable and efficient parallel implementations of algorithms for ultra high-precision dense linear algebra. We have successfully implemented our algorithm on the Blue Gene/L computer at IBM's T.J. Watson Research Center. Additionally, we have delineated the necessary algorithmic and coding changes required in order to address problems several orders of magnitude larger, dealing with the limits of scalability from memory footprint, computational, reliability, and interconnect perspectives.
Keywords: Nonlinear matroid optimization, model fitting, polynomial model, matrix algebra, Vandemonde system, Stirling numbers, extended precision arithmetic, distributed reduction, parallel Cholesky, limits of scalability, Blue Gene.
Category 1: Combinatorial Optimization
Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )
Category 3: Combinatorial Optimization (Graphs and Matroids )
Citation: IBM Research Report RC24682, 10/29/2008
Entry Submitted: 11/10/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|