LSBRR
Solves a linear least-squares problem with iterative refinement.
Required Arguments
A — Real NRA by NCA matrix containing the coefficient matrix of the least-squares system to be solved. (Input)
B — Real vector of length NRA containing the right-hand side of the least-squares system. (Input)
X — Real vector of length NCA containing the solution vector with components corresponding to the columns not used set to zero. (Output)
Optional Arguments
NRA — Number of rows of A. (Input)
Default: NRA = size (A,1).
Default: NRA = size (A,1).
NCA — Number of columns of A. (Input)
Default: NCA = size (A,2).
Default: NCA = size (A,2).
LDA — Leading dimension of A exactly as specified in the dimension statement of the calling program. (Input)
Default: LDA = size (A,1).
Default: LDA = size (A,1).
TOL — Real scalar containing the nonnegative tolerance used to determine the subset of columns of A to be included in the solution. (Input)
If TOL is zero, a full complement of min(NRA, NCA) columns is used. See Comments.
Default: TOL = 0.0
If TOL is zero, a full complement of min(NRA, NCA) columns is used. See Comments.
Default: TOL = 0.0
RES — Real vector of length NRA containing the residual vector B - AX. (Output)
KBASIS — Integer scalar containing the number of columns used in the solution. (Output)
FORTRAN 90 Interface
Generic: CALL LSBRR (A, B, X [, …])
Specific: The specific interface names are S_LSBRR and D_LSBRR.
FORTRAN 77 Interface
Single: CALL LSBRR (NRA, NCA, A, LDA, B, TOL, X, RES, KBASIS)
Double: The double precision name is DLSBRR.
Description
Routine LSBRR solves the linear least-squares problem using iterative refinement. The iterative refinement algorithm is due to Björck (1967, 1968). It is also described by Golub and Van Loan (1983, pages 182−183).
Comments
1. Workspace may be explicitly provided, if desired, by use of L2BRR/DL2BRR. The reference is:
CALL L2BRR (NRA, NCA, A, LDA, B, TOL, X, RES, KBASIS, QR, BRRUX,
IPVT, WK)
IPVT, WK)
The additional arguments are as follows:
QR — Work vector of length NRA * NCA representing an NRA by NCA matrix that contains information from the QR factorization of A. See LQRRR for details.
BRRUX — Work vector of length NCA containing information about the orthogonal factor of the QR factorization of A. See LQRRR for details.
IPVT — Integer work vector of length NCA containing the pivoting information for the QR factorization of A. See LQRRR for details.
WK — Work vector of length NRA + 2 * NCA − 1.
2. Informational error
Type | Code | Description |
|---|---|---|
4 | 1 | The data matrix is too ill-conditioned for iterative refinement to be effective. |
3. Routine LSBRR calculates the QR decomposition with pivoting of a matrix A and tests the diagonal elements against a user-supplied tolerance TOL. The first integer KBASIS = k is determined for which
∣rk+1,k+1 ∣ ≤ TOL * ∣r11∣
In effect, this condition implies that a set of columns with a condition number approximately bounded by 1.0/TOL is used. Then, LQRSL performs a truncated fit of the first KBASIS columns of the permuted A to an input vector B. The coefficient of this fit is unscrambled to correspond to the original columns of A, and the coefficients corresponding to unused columns are set to zero. It may be helpful to scale the rows and columns of A so that the error estimates in the elements of the scaled matrix are roughly equal to TOL. The iterative refinement method of Björck is then applied to this factorization.
4. Integer Options with Chapter 11 Options Manager
16 This option uses four values to solve memory bank conflict (access inefficiency) problems. In routine L2BRR the leading dimension of QR is increased by IVAL(3) when N is a multiple of IVAL(4). The values IVAL(3) and IVAL(4) are temporarily replaced by IVAL(1) and IVAL(2), respectively, in LSBRR. Additional memory allocation for QR and option value restoration are done automatically in LSBRR. Users directly calling L2BRR can allocate additional space for QR and set IVAL(3) and IVAL(4) so that memory bank conflicts no longer cause inefficiencies. There is no requirement that users change existing applications that use LSBRR or L2BRR. Default values for the option are IVAL(*) = 1, 16, 0, 1.
17 This option has two values that determine if the L1 condition number is to be computed. Routine LSBRR temporarily replaces IVAL(2) by IVAL(1). The routine L2CRG computes the condition number if IVAL(2) = 2. Otherwise L2CRG skips this computation. LSBRR restores the option. Default values for the option are IVAL(*) = 1, 2.
Example
This example solves the linear least-squares problem with A, an 8 × 4 matrix. Note that the second and fourth columns of A are identical. Routine LSBRR determines that there are three columns in the basis.
USE LSBRR_INT
USE UMACH_INT
USE WRRRN_INT
! Declare variables
PARAMETER (NRA=8, NCA=4, LDA=NRA)
REAL A(LDA,NCA), B(NRA), X(NCA), RES(NRA), TOL
!
! Set values for A
!
! A = ( 1 5 15 5 )
! ( 1 4 17 4 )
! ( 1 7 14 7 )
! ( 1 3 18 3 )
! ( 1 1 15 1 )
! ( 1 8 11 8 )
! ( 1 3 9 3 )
! ( 1 4 10 4 )
!
DATA A/8*1, 5., 4., 7., 3., 1., 8., 3., 4., 15., 17., 14., &
18., 15., 11., 9., 10., 5., 4., 7., 3., 1., 8., 3., 4. /
!
! Set values for B
!
DATA B/ 30., 31., 35., 29., 18., 35., 20., 22. /
!
! Solve the least squares problem
TOL = 1.0E-4
CALL LSBRR (A, B, X, tol=tol, RES=RES, KBASIS=KBASIS)
! Print results
CALL UMACH (2, NOUT)
WRITE (NOUT,*) ’KBASIS = ’, KBASIS
CALL WRRRN (’X’, X, 1, NCA, 1)
CALL WRRRN (’RES’, RES, 1, NRA, 1)
!
END
Output
KBASIS = 3
X
1 2 3 4
0.636 2.845 1.058 0.000
RES
1 2 3 4 5 6 7 8
-0.733 0.996 -0.365 0.783 -1.353 -0.036 1.306 -0.597
