  Non-negative matrix factorization (NMF) is the problem of determining two
non-negative low rank factors $W$ and $H$, for the given input matrix $A$, such
that $A \approx W H$. NMF is a useful tool for many applications in different
domains such as topic modeling in text mining, background separation in video
analysis, and community detection in social networks. Despite its popularity in
the data mining community, there is a lack of efficient parallel software to
solve the problem for big datasets. Existing distributed-memory algorithms are
limited in terms of performance and applicability, as they are implemented
using Hadoop and are designed only for sparse matrices.
  We propose a distributed-memory parallel algorithm that computes the
factorization by iteratively solving alternating non-negative least squares
(NLS) subproblems for $W$ and $H$. To our knowledge, our algorithm is the first
high-performance parallel algorithm for NMF. It maintains the data and factor
matrices in memory (distributed across processors), uses MPI for interprocessor
communication, and, in the dense case, provably minimizes communication costs
(under mild assumptions). As opposed to previous implementations, our algorithm
is also flexible: (1) it performs well for dense and sparse matrices, and (2)
it allows the user to choose from among multiple algorithms for solving local
NLS subproblems within the alternating iterations. We demonstrate the
scalability of our algorithm and compare it with baseline implementations,
showing significant performance improvements.
