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 language||English (US)|
|Number of pages||10|
|Journal||Procedia Computer Science|
|State||Published - 2017|
|Event||International Conference on Computational Science ICCS 2017 - Zurich, Switzerland|
Duration: Jun 12 2017 → Jun 14 2017
Bibliographical notePublisher Copyright:
© 2017 The Authors. Published by Elsevier B.V.
- active set
- non-negative least squares
- preconditioned conjugate gradient
- rock magnetism