tsnnls 2.0 - A fast block pivoting algorithm for sparse linear least squares
problems with non-negative variables designed to be embedded in applications
http://www.cs.duq.edu/~piatek/tsnnls/
http://ada.math.uga.edu/research/software/tsnnls/
Jason Cantarella, cantarel@math.uga.edu
Michael Piatek, piatek@mathcs.duq.edu
Eric Rawdon, ericrawdon@gmail.com
11 September 2007
Contents
0. What is tsnnls?
1. Building
2. License
3. Quick start
4. Supporting functions
5. References
0. tsnnls is a fast solver for least-squares problems in the form Ax
= b under the constraint that all entries in the solution vector x are
non-negative. The solver works for the case when the matrix A has full
column rank (and so there is a unique solution). The tsnnls code is
primarily designed for large sparse problems, but works well for dense
problems too. We designed tsnnls to be called from larger
applications, and are including it in a large simulation ourselves. We
would be interested to hear about your application for tsnnls-- please
feel free to write to us and tell us about your uses for the code!
The tsnnls library also includes a fast unconstrained least-squares
solver based on the method of normal equations. For well-conditioned
problems, this is a reasonable solution. For ill-conditioned problems,
you are probably better off with an iterative method like the Stanford
LSQR code, which is also freely available on the web.
The current implementation of tsnnls does not have direct support for
multiprocessor machines. For a more complete report on tsnnls, see our
paper "tsnnls: A solver for large sparse least squares problems with
non-negative variables", which is available on the web from the same
location as this library.
1. Building
See the file INSTALL in the main distribution directory.
Also note that included with our distribution is a limited version of
the TAUCS package for sparse matrix manipulation. Future updates to
this library may provide performance benefits for tsnnls. See
http://www.tau.ac.il/~stoledo/taucs/ for information on the TAUCS
library. We include source from version 2.2. A statement regarding the
TAUCS license and availability information is provided in
'TAUCS_LICENSE_AND_AVAILABILITY' in the same directory as this readme.
2. License
This software is distributed under the terms of the GNU GPL. A full
description of the terms of this license can be found in the file
'LICENSE' in the same directory as this readme, or the license can be
read on the web at http://www.gnu.org/licenses/gpl.txt
3. Quick start
Once you have built the library, the main functionality is exposed
through the header tsnnls.h. The functions of primary interest are:
taucs_ccs_matrix*
taucs_construct_sorted_ccs_matrix( double* values, int cols, int rows );
This function takes an array of double values in row major order
representing a dense matrix of size rows by cols and converts it into
a compressed column structure for use with our algorithm. For a
complete discussion of the taucs_ccs_matrix structure, see the
taucs.pdf documentation included with this package.
taucs_double* t_snnls( taucs_ccs_matrix *A_original_ordering,
taucs_double *b, double* outResidualNorm, double inRelErrTolerance,
int inPrintErrorWarnings );
This function solves the problem Ax = b in the least squares sense
subject to the contraint that x > 0. The value returned is an array of
doubles of size A->n, where A->n is the number of columns of the
matrix A. b must be of size A->m where A-> is the number of rows of
the matrix A. residualNorm is the 2-norm of the residual
b-Ax. inRelErrTolerance is the threshold for relative error (estimated
using (condition number)^2*(machine epsilon)) at which to use the more
numerically sensitive LSQR algorithm (see references). If you *never*
wish to use LSQR steps (for maximum speed) pass a value greater than 1
for this parameter. If you always want to perform a final LSQR step
(for maximum accuracy), pass a value less than 0 for this
parameter. The latter practice is recommended.
double* t_lsqr(taucs_ccs_matrix *A, taucs_double *b);
This function solves the unconstrained problem Ax=b in the least
squares sense using a Cholesky factorization.
For examples of how these functions can be used in practice, see the
tsnnls test application source in the file 'tsnnls_test.c' in the same
directory as this readme.
4. Supporting functions
A variety of debugging and support functions are included with tsnnls
that may be useful in your application. We describe several here:
double
taucs_rcond( taucs_ccs_matrix* A );
This function returns an estimate of the reciprocal condition number
of A as computed by LAPACK.
double*
taucs_convert_ccs_to_doubles( const taucs_ccs_matrix* A );
This function converts a sparse matrix A to an array of doubles in row
major order of size A->m*A->n.
taucs_ccs_matrix*
taucs_ccs_transpose( const taucs_ccs_matrix* A );
This function returns a sparse representation of the transpose of A.
void
taucs_print_ccs_matrix( const taucs_ccs_matrix* A );
This function prints a representation of the sparse matrix A on
stdout.
See the tsnnls.h header for a complete list of functions available
from the library.
5. References
Version 2.0 of tsnnls uses the block3 algorithm of Mikael Adlers. A
description of the algorithm can be found in his licentiat thesis
"Sparse Least Squares Problems with Box Constraints", available at
http://www.mai.liu.se/~milun/
The self-test code in tsnnls 2.0 and higher uses a problem generation
strategy proposed in
@article {MR95a:90059,
AUTHOR = {Portugal, Lu{\'{\i}}s F. and J{\'u}dice, Joaqu{\'{\i}}m J. and
Vicente, Lu{\'{\i}}s N.},
TITLE = {A comparison of block pivoting and interior-point algorithms
for linear least squares problems with nonnegative variables},
JOURNAL = {Math. Comp.},
FJOURNAL = {Mathematics of Computation},
VOLUME = {63},
YEAR = {1994},
NUMBER = {208},
PAGES = {625--643},
ISSN = {0025-5718},
CODEN = {MCMPAF},
MRCLASS = {90C20 (65K05)},
MRNUMBER = {95a:90059},
The paper is stored on JSTOR.
LSQR sparse unconstrained least squares algorithm:
http://www.stanford.edu/group/SOL/software.html
LAPACK and BLAS: http://www.netlib.org/lapack/
TAUCS library for sparse matrices: http://www.tau.ac.il/~stoledo/taucs/