Multifrontal non-negative matrix factorization

Piyush Sao; Ramakrishnan Kannan

doi:10.1007/978-3-030-43229-4_46

Multifrontal non-negative matrix factorization

Piyush Sao, Ramakrishnan Kannan

Discrete Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Non-negative matrix factorization (Nmf) is an important tool in high-performance large scale data analytics with applications ranging from community detection, recommender system, feature detection and linear and non-linear unmixing. While traditional Nmf works well when the data set is relatively dense, however, it may not extract sufficient structure when the data is extremely sparse. Specifically, traditional Nmf fails to exploit the structured sparsity of the large and sparse data sets resulting in dense factors. We propose a new algorithm for performing Nmf on sparse data that we call multifrontal Nmf (Mf-Nmf) since it borrows several ideas from the multifrontal method for unconstrained factorization (e.g. LU and QR). We also present an efficient shared memory parallel implementation of Mf-Nmf and discuss its performance and scalability. We conduct several experiments on synthetic and realworld datasets and demonstrate the usefulness of the algorithm by comparing it against standard baselines. We obtain a speedup of 1.2x to 19.5x on 24 cores with an average speed up of 10.3x across all the real world datasets.

Original language	English
Title of host publication	Parallel Processing and Applied Mathematics - 13th International Conference, PPAM 2019, Revised Selected Papers
Editors	Roman Wyrzykowski, Konrad Karczewski, Ewa Deelman, Jack Dongarra
Publisher	Springer
Pages	543-554
Number of pages	12
ISBN (Print)	9783030432287
DOIs	https://doi.org/10.1007/978-3-030-43229-4_46
State	Published - 2020
Event	13th International Conference on Parallel Processing and Applied Mathematics, PPAM 2019 - Bialystok, Poland Duration: Sep 8 2019 → Sep 11 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12043 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th International Conference on Parallel Processing and Applied Mathematics, PPAM 2019
Country/Territory	Poland
City	Bialystok
Period	09/8/19 → 09/11/19

Funding

This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. This research was funded by Oak Ridge National Laboratory-Laboratory Directed Research and Development (LDRD) and used resources of the Oak Ridge Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC05-00OR22725. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/ downloads/doe-public-access-plan). This manuscript has been authored by UT-Battelle, LLC under Contract No. DEAC05-00OR22725 with the U.S. Department of Energy. This research was funded by Oak Ridge National Laboratory-Laboratory Directed Research and Development (LDRD) and used resources of the Oak Ridge Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC05-00OR22725. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/ downloads/doe-public-access-plan).

Keywords

Data analysis
Multifrontal methods
Non-negative matrix factorization
Sparse matrix computations

Access to Document

10.1007/978-3-030-43229-4_46

Cite this

Sao, P., & Kannan, R. (2020). Multifrontal non-negative matrix factorization. In R. Wyrzykowski, K. Karczewski, E. Deelman, & J. Dongarra (Eds.), Parallel Processing and Applied Mathematics - 13th International Conference, PPAM 2019, Revised Selected Papers (pp. 543-554). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12043 LNCS). Springer. https://doi.org/10.1007/978-3-030-43229-4_46

Sao, Piyush ; Kannan, Ramakrishnan. / Multifrontal non-negative matrix factorization. Parallel Processing and Applied Mathematics - 13th International Conference, PPAM 2019, Revised Selected Papers. editor / Roman Wyrzykowski ; Konrad Karczewski ; Ewa Deelman ; Jack Dongarra. Springer, 2020. pp. 543-554 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d31bd65cb1d74fb1a06eceab6f9a1cae,

title = "Multifrontal non-negative matrix factorization",

abstract = "Non-negative matrix factorization (Nmf) is an important tool in high-performance large scale data analytics with applications ranging from community detection, recommender system, feature detection and linear and non-linear unmixing. While traditional Nmf works well when the data set is relatively dense, however, it may not extract sufficient structure when the data is extremely sparse. Specifically, traditional Nmf fails to exploit the structured sparsity of the large and sparse data sets resulting in dense factors. We propose a new algorithm for performing Nmf on sparse data that we call multifrontal Nmf (Mf-Nmf) since it borrows several ideas from the multifrontal method for unconstrained factorization (e.g. LU and QR). We also present an efficient shared memory parallel implementation of Mf-Nmf and discuss its performance and scalability. We conduct several experiments on synthetic and realworld datasets and demonstrate the usefulness of the algorithm by comparing it against standard baselines. We obtain a speedup of 1.2x to 19.5x on 24 cores with an average speed up of 10.3x across all the real world datasets.",

keywords = "Data analysis, Multifrontal methods, Non-negative matrix factorization, Sparse matrix computations",

author = "Piyush Sao and Ramakrishnan Kannan",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.; 13th International Conference on Parallel Processing and Applied Mathematics, PPAM 2019 ; Conference date: 08-09-2019 Through 11-09-2019",

year = "2020",

doi = "10.1007/978-3-030-43229-4_46",

language = "English",

isbn = "9783030432287",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "543--554",

editor = "Roman Wyrzykowski and Konrad Karczewski and Ewa Deelman and Jack Dongarra",

booktitle = "Parallel Processing and Applied Mathematics - 13th International Conference, PPAM 2019, Revised Selected Papers",

}

Sao, P & Kannan, R 2020, Multifrontal non-negative matrix factorization. in R Wyrzykowski, K Karczewski, E Deelman & J Dongarra (eds), Parallel Processing and Applied Mathematics - 13th International Conference, PPAM 2019, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12043 LNCS, Springer, pp. 543-554, 13th International Conference on Parallel Processing and Applied Mathematics, PPAM 2019, Bialystok, Poland, 09/8/19. https://doi.org/10.1007/978-3-030-43229-4_46

Multifrontal non-negative matrix factorization. / Sao, Piyush ; Kannan, Ramakrishnan.
Parallel Processing and Applied Mathematics - 13th International Conference, PPAM 2019, Revised Selected Papers. ed. / Roman Wyrzykowski; Konrad Karczewski; Ewa Deelman; Jack Dongarra. Springer, 2020. p. 543-554 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12043 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Multifrontal non-negative matrix factorization

AU - Sao, Piyush

AU - Kannan, Ramakrishnan

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020.

PY - 2020

Y1 - 2020

N2 - Non-negative matrix factorization (Nmf) is an important tool in high-performance large scale data analytics with applications ranging from community detection, recommender system, feature detection and linear and non-linear unmixing. While traditional Nmf works well when the data set is relatively dense, however, it may not extract sufficient structure when the data is extremely sparse. Specifically, traditional Nmf fails to exploit the structured sparsity of the large and sparse data sets resulting in dense factors. We propose a new algorithm for performing Nmf on sparse data that we call multifrontal Nmf (Mf-Nmf) since it borrows several ideas from the multifrontal method for unconstrained factorization (e.g. LU and QR). We also present an efficient shared memory parallel implementation of Mf-Nmf and discuss its performance and scalability. We conduct several experiments on synthetic and realworld datasets and demonstrate the usefulness of the algorithm by comparing it against standard baselines. We obtain a speedup of 1.2x to 19.5x on 24 cores with an average speed up of 10.3x across all the real world datasets.

AB - Non-negative matrix factorization (Nmf) is an important tool in high-performance large scale data analytics with applications ranging from community detection, recommender system, feature detection and linear and non-linear unmixing. While traditional Nmf works well when the data set is relatively dense, however, it may not extract sufficient structure when the data is extremely sparse. Specifically, traditional Nmf fails to exploit the structured sparsity of the large and sparse data sets resulting in dense factors. We propose a new algorithm for performing Nmf on sparse data that we call multifrontal Nmf (Mf-Nmf) since it borrows several ideas from the multifrontal method for unconstrained factorization (e.g. LU and QR). We also present an efficient shared memory parallel implementation of Mf-Nmf and discuss its performance and scalability. We conduct several experiments on synthetic and realworld datasets and demonstrate the usefulness of the algorithm by comparing it against standard baselines. We obtain a speedup of 1.2x to 19.5x on 24 cores with an average speed up of 10.3x across all the real world datasets.

KW - Data analysis

KW - Multifrontal methods

KW - Non-negative matrix factorization

KW - Sparse matrix computations

UR - http://www.scopus.com/inward/record.url?scp=85084000767&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-43229-4_46

DO - 10.1007/978-3-030-43229-4_46

M3 - Conference contribution

AN - SCOPUS:85084000767

SN - 9783030432287

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 543

EP - 554

BT - Parallel Processing and Applied Mathematics - 13th International Conference, PPAM 2019, Revised Selected Papers

A2 - Wyrzykowski, Roman

A2 - Karczewski, Konrad

A2 - Deelman, Ewa

A2 - Dongarra, Jack

PB - Springer

T2 - 13th International Conference on Parallel Processing and Applied Mathematics, PPAM 2019

Y2 - 8 September 2019 through 11 September 2019

ER -

Sao P , Kannan R. Multifrontal non-negative matrix factorization. In Wyrzykowski R, Karczewski K, Deelman E, Dongarra J, editors, Parallel Processing and Applied Mathematics - 13th International Conference, PPAM 2019, Revised Selected Papers. Springer. 2020. p. 543-554. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-43229-4_46

Multifrontal non-negative matrix factorization

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this