HFTI(3)

SYNOPSIS
SUBROUTINE HFTI (A, MDA, M, N, B, MDB, NB, TAU, KRANK, RNORM, H, + G, IP)

NAME
hfti - Solve a linear least squares problems by performing a QR factorization of the matrix using Householder transformations.

LIBRARY
SLATEC

CATEGORY
D9

TYPE
SINGLE PRECISION (HFTI-S, DHFTI-D)

KEYWORDS
CURVE FITTING, LINEAR LEAST SQUARES, QR FACTORIZATION

AUTHOR
Lawson, C. L., (JPL) Hanson, R. J., (SNLA)

DESCRIPTION
DIMENSION A(MDA,N),(B(MDB,NB) or B(M)),RNORM(NB),H(N),G(N),IP(N) This subroutine solves a linear least squares problem or a set of linear least squares problems having the same matrix but different right-side vectors. The problem data consists of an M by N matrix A, an M by NB matrix B, and an absolute tolerance parameter TAU whose usage is described below. The NB column vectors of B represent right-side vectors for NB distinct linear least squares problems. This set of problems can also be written as the matrix least squares problem AX = B, where X is the N by NB solution matrix. Note that if B is the M by M identity matrix, then X will be the pseudo-inverse of A. This subroutine first transforms the augmented matrix (A B) to a matrix (R C) using premultiplying Householder transformations with column interchanges. All subdiagonal elements in the matrix R are zero and its diagonal elements satisfy ABS(R(I,I)).GE.ABS(R(I+1,I+1)), I = 1,...,L-1, where L = MIN(M,N). The subroutine will compute an integer, KRANK, equal to the number of diagonal terms of R that exceed TAU in magnitude. Then a solution of minimum Euclidean length is computed using the first KRANK rows of (R C). To be specific we suggest that the user consider an easily computable matrix norm, such as, the maximum of all column sums of magnitudes. Now if the relative uncertainty of B is EPS, (norm of uncertainty/ norm of B), it is suggested that TAU be set approximately equal to EPS*(norm of A). The user must dimension all arrays appearing in the call list.. A(MDA,N),(B(MDB,NB) or B(M)),RNORM(NB),H(N),G(N),IP(N). This permits the solution of a range of problems in the same array space. The entire set of parameters for HFTI are INPUT.. A(*,*),MDA,M,N The array A(*,*) initially contains the M by N matrix A of the least squares problem AX = B. The first dimensioning parameter of the array A(*,*) is MDA, which must satisfy MDA.GE.M Either M.GE.N or M.LT.N is permitted. There is no restriction on the rank of A. The condition MDA.LT.M is considered an error. B(*),MDB,NB If NB = 0 the subroutine will perform the orthogonal decomposition but will make no references to the array B(*). If NB.GT.0 the array B(*) must initially contain the M by NB matrix B of the least squares problem AX = B. If NB.GE.2 the array B(*) must be doubly subscripted with first dimensioning parameter MDB.GE.MAX(M,N). If NB = 1 the array B(*) may be either doubly or singly subscripted. In the latter case the value of MDB is arbitrary but it should be set to some valid integer value such as MDB = M. The condition of NB.GT.1.AND.MDB.LT. MAX(M,N) is considered an error. TAU Absolute tolerance parameter provided by user for pseudorank determination. H(*),G(*),IP(*) Arrays of working space used by HFTI. OUTPUT.. A(*,*) The contents of the array A(*,*) will be modified by the subroutine. These contents are not generally required by the user. B(*) On return the array B(*) will contain the N by NB solution matrix X. KRANK Set by the subroutine to indicate the pseudorank of A. RNORM(*) On return, RNORM(J) will contain the Euclidean norm of the residual vector for the problem defined by the J-th column vector of the array B(*,*) for J = 1,...,NB. H(*),G(*) On return these arrays respectively contain elements of the pre- and post-multiplying Householder transformations used to compute the minimum Euclidean length solution. IP(*) Array in which the subroutine records indices describing the permutation of column vectors. The contents of arrays H(*),G(*) and IP(*) are not generally required by the user.

REFERENCES
C. L. Lawson and R. J. Hanson, Solving Least Squares Problems, Prentice-Hall, Inc., 1974, Chapter 14.

ROUTINES CALLED
H12, R1MACH, XERMSG

REVISION HISTORY (YYMMDD)
790101 DATE WRITTEN
890531 Changed all specific intrinsics to generic. (WRB)
891006 Cosmetic changes to prologue. (WRB)
891006 REVISION DATE from Version 3.2
891214 Prologue converted to Version 4.0 format. (BAB)
900315 CALLs to XERROR changed to CALLs to XERMSG. (THJ)
901005 Replace usage of DIFF with usage of R1MACH. (RWC)
920501 Reformatted the REFERENCES section. (WRB)