TNT-NN: A Fast Active Set Method for Solving Large Non-Negative Least Squares Problems

J. M. Myre, E. Frahm, D. J. Lilja, M. O. Saar

Research output: Contribution to journalConference article

6 Scopus citations

Abstract

In 1974 Lawson and Hanson produced a seminal active set strategy to solve least-squares problems with non-negativity constraints that remains popular today. In this paper we present TNT-NN, a new active set method for solving non-negative least squares (NNLS) problems. TNT-NN uses a different strategy not only for the construction of the active set but also for the solution of the unconstrained least squares sub-problem. This results in dramatically improved performance over traditional active set NNLS solvers, including the Lawson and Hanson NNLS algorithm and the Fast NNLS (FNNLS) algorithm, allowing for computational investigations of new types of scientific and engineering problems. For the small systems tested (5000 × 5000 or smaller), it is shown that TNT-NN is up to 95 × faster than FNNLS. Recent studies in rock magnetism have revealed a need for fast NNLS algorithms to address large problems (on the order of 105 × 105 or larger). We apply the TNT-NN algorithm to a representative rock magnetism inversion problem where it is 60× faster than FNNLS. We also show that TNT-NN is capable of solving large (45000 × 45000) problems more than 150 × faster than FNNLS. These large test problems were previously considered to be unsolvable, due to the excessive execution time required by traditional methods.

Original languageEnglish (US)
Pages (from-to)755-764
Number of pages10
JournalProcedia Computer Science
Volume108
DOIs
StatePublished - Jan 1 2017
EventInternational Conference on Computational Science ICCS 2017 - Zurich, Switzerland
Duration: Jun 12 2017Jun 14 2017

    Fingerprint

Keywords

  • active set
  • non-negative least squares
  • preconditioned conjugate gradient
  • rock magnetism

Cite this