2013/12/01 by Hyokun Yun, Yun, Hyokun, Hsiang‐Fu Yu +10 · 32 citations
Computer Science · Engineering · Mathematics · #Algorithm #Asynchronous communication #Blind Source Separation Techniques #Cellular Automata and Applications #Completion (oil and gas wells) #Computer network #Computer science #Distributed #Engineering #FOS: Computer and information sciences #Mathematical optimization #Mathematics #Matrix (chemical analysis) #Matrix Theory and Algorithms #Matrix completion #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1312.0193
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2013/12/01 · arxiv created 2014/04/24 · arxiv updated 2014/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop an efficient parallel distributed algorithm for matrix completion, named NOMAD (Non-locking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion). NOMAD is a decentralized algorithm with non-blocking communication between processors. One of the key features of NOMAD is that the ownership of a variable is asynchronously transferred between processors in a decentralized fashion. As a consequence it is a lock-free parallel algorithm. In spite of being an asynchronous algorithm, the variable updates of NOMAD are serializable, that is, there is an equivalent update ordering in a serial implementation. NOMAD outperforms synchronous algorithms which require explicit bulk synchronization after every iteration: our extensive empirical evaluation shows that not only does our algorithm perform well in distributed setting on commodity hardware, but also outperforms state-of-the-art algorithms on a HPC cluster both in multi-core and distributed memory settings.