LAWSON
Least Squares Routines

LAWSON is a FORTRAN77 library for solving least squares problems.

The most common least squares problems considers an overdetermined M by N linear system A*X=B. A least squares solution X is sought which has the property that, although it generally is not a solution of the system, it is the best approximation to a solution, in the sense that it minimizes the L2 norm of the residual R=A*X-B.

In some cases, a unique solution to the system A*X=B will exist, and in that case the least squares solution will coincide with what is ordinarily meant by a solution.

In underdetermined cases, where multiple solutions exist, the least squares solution is usually taken to be that solution X which has minimum L2 norm, that is, which minimizes ||X||.

The original FORTRAN77 source code is available through NETLIB at
http://www.netlib.org/lawson-hanson/index.html.

Related Data and Programs:

BRENT is a FORTRAN77 library which contains Richard Brent's routines for finding the zero, local minimizer, or global minimizer of a scalar function of a scalar argument, without the use of derivative information.

DQED is a FORTRAN77 library which solves constrained least squares problems.

NL2SOL is a FORTRAN77 library which implements an adaptive nonlinear least-squares algorithm.

PRAXIS is a FORTRAN77 library which minimizes a scalar function of several variables.

TOMS611 is a FORTRAN77 library which seeks the minimizer of a scalar functional of multiple variables.

Reference:

1. Charles Lawson, Richard Hanson,
   Solving Least Squares Problems,
   Revised edition,
   SIAM, 1995,
   ISBN: 0898713560,
   LC: QA275.L38.

Source Code:

• lawson.f, the source code.
• lawson.csh, commands to compile the source code.

Examples and Tests:

LAWSON_PRB1 demonstrates algorithms HFTI and HS1 for solving least squares problems, and algorithm COV for computing the associated covariance matrix.

• lawson_prb1.f, a sample problem.
• lawson_prb1.csh, commands to compile, link and run the sample problem.
• lawson_prb1_output.txt, the output file.

LAWSON_PRB2 demonstrates algorithms HFTI for solving least squares problems, and algorithm COV for computing the associated unscaled covariance matrix.

• lawson_prb2.f, a sample problem.
• lawson_prb2.csh, commands to compile, link and run the sample problem.
• lawson_prb2_output.txt, the output file.

LAWSON_PRB3 demonstrates the use of routine SVDRS to compute the singular value decomposition of a matrix, and to solve a related least squares linear system.

• lawson_prb3.f, a sample problem.
• lawson_prb3.csh, commands to compile, link and run the sample problem.
• lawson_prb3_output.txt, the output file.

LAWSON_PRB4 demonstrates singular value analysis with SVA.

• lawson_prb4.f, a sample problem.
• lawson_prb4.csh, commands to compile, link and run the sample problem.
• lawson_prb4_input.txt, the input file.
• lawson_prb4_output.txt, the output file.

LAWSON_PRB5 demonstrates the BNDACC and BNDSOL routines to handle least squares problems with a banded matrix.

• lawson_prb5.f, a sample problem.
• lawson_prb5.csh, commands to compile, link and run the sample problem.
• lawson_prb5_output.txt, the output file.

LAWSON_PRB6 demonstrates the LDP routine.

• lawson_prb6.f, a sample problem.
• lawson_prb6.csh, commands to compile, link and run the sample problem.
• lawson_prb6_output.txt, the output file.

List of Routines:

• BNDACC accumulates information for a banded least squares problem.
• BNDSOL solves a banded least squares problem accumulated by BNDACC.
• DIFF is used in tests that depend on machine precision.
• G1 computes an orthogonal rotation matrix.
• G2 applies a rotation matrix to a vector (X,Y).
• GEN generates numbers for construction of test cases.
• H12 constructs or applies a Householder transformation.
• HFTI Householder forward triangulation with column interchanges.
• LDP implements least distance programming
• MFEOUT labeled matrix output for use with singular value analysis.
• NNLS implements the nonnegative least squares algorithm.
• QRBD uses the QR algorithm for the singular values of a bidiagonal matrix.
• SVA carries out a singular value analysis.
• SVDRS singular value decomposition also treating right side vector.

You can go up one level to the FORTRAN77 source codes.