Scalability and fault tolerance of the alternating direction method of multipliers for sparse grids

Valeriy Khakhutskyy*, Dirk Pflüger, Markus Hegland

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Citation (Scopus)


    In this work we investigate the alternating direction method of multipliers (ADMM) for the solution of regression problems using sparse grids on parallel and distributed systems. This method was successfully used in a number of applications for the parallel processing of large datasets. While the method allows for both parallelization in the data and in the degrees of freedom, research was mostly focused on the first approach so far. In this work we consider and compare both approaches. On the one hand, we present the grid-splitting algorithm for hierarchical sparse grids which we employ to deal with vast datasets and high dimensions. The hierarchical basis of sparse grids is inherently difficult to parallelize in the degrees of freedom as ignoring the hierarchical structure affects stability. Here we use the property that a regular sparse grid with the maximum level n in d dimensions can be split into two d-dimensional grids with level n-1 and one d-1-dimensional grid with level n. The method also converges if asynchronous one-sided communication is used. It thus increases the robustness of the algorithm and introduces fault tolerance-the essential properties of parallel algorithms for next-generation supercomputers. On the other hand, we study the data parallelization of the sparse grid ADMM algorithm using one-sided communication. While the reduction of the parallel runtime is lower than for grid splitting, this method does not require changes of the sparse grid learning algorithm and can be used with existing software. Due to its fast convergence the method is suited for dealing with large datasets.

    Original languageEnglish
    Title of host publicationParallel Computing
    Subtitle of host publicationAccelerating Computational Science and Engineering (CSE)
    PublisherIOS Press BV
    Number of pages10
    ISBN (Print)9781614993803
    Publication statusPublished - 2014

    Publication series

    NameAdvances in Parallel Computing
    ISSN (Print)0927-5452


    Dive into the research topics of 'Scalability and fault tolerance of the alternating direction method of multipliers for sparse grids'. Together they form a unique fingerprint.

    Cite this