# NAG Library Routine Document

## 1Purpose

f04amf calculates the accurate least squares solution of a set of $m$ linear equations in $n$ unknowns, $m\ge n$ and rank $\text{}=n$, with multiple right-hand sides, $AX=B$, using a $QR$ factorization and iterative refinement.

## 2Specification

Fortran Interface
 Subroutine f04amf ( a, lda, x, ldx, b, ldb, m, n, ir, eps, qr, ldqr, e, y, z, r, ipiv,
 Integer, Intent (In) :: lda, ldx, ldb, m, n, ir, ldqr Integer, Intent (Inout) :: ifail Integer, Intent (Out) :: ipiv(n) Real (Kind=nag_wp), Intent (In) :: a(lda,n), b(ldb,ir), eps Real (Kind=nag_wp), Intent (Inout) :: x(ldx,ir), qr(ldqr,n) Real (Kind=nag_wp), Intent (Out) :: alpha(n), e(n), y(n), z(n), r(m)
C Header Interface
#include <nagmk26.h>
 void f04amf_ (const double a[], const Integer *lda, double x[], const Integer *ldx, const double b[], const Integer *ldb, const Integer *m, const Integer *n, const Integer *ir, const double *eps, double qr[], const Integer *ldqr, double alpha[], double e[], double y[], double z[], double r[], Integer ipiv[], Integer *ifail)

## 3Description

To compute the least squares solution to a set of $m$ linear equations in $n$ unknowns $\left(m\ge n\right)$ $AX=B$, f04amf first computes a $QR$ factorization of $A$ with column pivoting, $AP=QR$, where $R$ is upper triangular, $Q$ is an $m$ by $m$ orthogonal matrix, and $P$ is a permutation matrix. ${Q}^{\mathrm{T}}$ is applied to the $m$ by $r$ right-hand side matrix $B$ to give $C={Q}^{\mathrm{T}}B$, and the $n$ by $r$ solution matrix $X$ is calculated, to a first approximation, by back-substitution in $RX=C$. The residual matrix $S=B-AX$ is calculated using additional precision, and a correction $D$ to $X$ is computed as the least squares solution to $AD=S$. $X$ is replaced by $X+D$ and this iterative refinement of the solution is repeated until full machine accuracy has been obtained.
Wilkinson J H and Reinsch C (1971) Handbook for Automatic Computation II, Linear Algebra Springer–Verlag

## 5Arguments

1:     $\mathbf{a}\left({\mathbf{lda}},{\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayInput
On entry: the $m$ by $n$ matrix $A$.
2:     $\mathbf{lda}$ – IntegerInput
On entry: the first dimension of the array a as declared in the (sub)program from which f04amf is called.
Constraint: ${\mathbf{lda}}\ge {\mathbf{m}}$.
3:     $\mathbf{x}\left({\mathbf{ldx}},{\mathbf{ir}}\right)$ – Real (Kind=nag_wp) arrayOutput
On exit: the $n$ by $r$ solution matrix $X$.
4:     $\mathbf{ldx}$ – IntegerInput
On entry: the first dimension of the array x as declared in the (sub)program from which f04amf is called.
Constraint: ${\mathbf{ldx}}\ge {\mathbf{n}}$.
5:     $\mathbf{b}\left({\mathbf{ldb}},{\mathbf{ir}}\right)$ – Real (Kind=nag_wp) arrayInput
On entry: the $m$ by $r$ right-hand side matrix $B$.
6:     $\mathbf{ldb}$ – IntegerInput
On entry: the first dimension of the array b as declared in the (sub)program from which f04amf is called.
Constraint: ${\mathbf{ldb}}\ge {\mathbf{m}}$.
7:     $\mathbf{m}$ – IntegerInput
On entry: $m$, the number of rows of the matrix $A$, i.e., the number of equations.
Constraint: ${\mathbf{m}}\ge 1$.
8:     $\mathbf{n}$ – IntegerInput
On entry: $n$, the number of columns of the matrix $A$, i.e., the number of unknowns.
Constraint: $0\le {\mathbf{n}}\le {\mathbf{m}}$.
9:     $\mathbf{ir}$ – IntegerInput
On entry: $r$, the number of right-hand sides.
10:   $\mathbf{eps}$ – Real (Kind=nag_wp)Input
On entry: must be set to the value of the machine precision.
11:   $\mathbf{qr}\left({\mathbf{ldqr}},{\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayOutput
On exit: details of the $QR$ factorization.
12:   $\mathbf{ldqr}$ – IntegerInput
On entry: the first dimension of the array qr as declared in the (sub)program from which f04amf is called.
Constraint: ${\mathbf{ldqr}}\ge {\mathbf{m}}$.
13:   $\mathbf{alpha}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayOutput
On exit: the diagonal elements of the upper triangular matrix $R$.
14:   $\mathbf{e}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayWorkspace
15:   $\mathbf{y}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayWorkspace
16:   $\mathbf{z}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayWorkspace
17:   $\mathbf{r}\left({\mathbf{m}}\right)$ – Real (Kind=nag_wp) arrayWorkspace
18:   $\mathbf{ipiv}\left({\mathbf{n}}\right)$ – Integer arrayOutput
On exit: details of the column interchanges.
19:   $\mathbf{ifail}$ – IntegerInput/Output
On entry: ifail must be set to $0$, . If you are unfamiliar with this argument you should refer to Section 3.4 in How to Use the NAG Library and its Documentation for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value  is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is $0$. When the value  is used it is essential to test the value of ifail on exit.
On exit: ${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

## 6Error Indicators and Warnings

If on entry ${\mathbf{ifail}}=0$ or $-1$, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
${\mathbf{ifail}}=1$
The rank of a is less than n. The problem does not have a unique solution.
${\mathbf{ifail}}=2$
The iterative refinement fails to converge. The matrix $A$ is too ill-conditioned.
${\mathbf{ifail}}=-99$
An unexpected error has been triggered by this routine. Please contact NAG.
See Section 3.9 in How to Use the NAG Library and its Documentation for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 3.8 in How to Use the NAG Library and its Documentation for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 3.7 in How to Use the NAG Library and its Documentation for further information.

## 7Accuracy

Although the correction process is continued until the solution has converged to full machine accuracy, all the figures in the final solution may not be correct since the correction $D$ to $X$ is itself the solution to a linear least squares problem. For a detailed error analysis see page 116 of Wilkinson and Reinsch (1971).

## 8Parallelism and Performance

f04amf makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

## 9Further Comments

The time taken by f04amf is approximately proportional to ${n}^{2}\left(3m-n\right)$, provided $r$ is small compared with $n$.

## 10Example

This example calculates the accurate least squares solution of the equations
 $1.1x1+0.9x2=2.2 1.2x1+1.0x2=2.3 1.0x1+1.0x2=2.1$

### 10.1Program Text

Program Text (f04amfe.f90)

### 10.2Program Data

Program Data (f04amfe.d)

### 10.3Program Results

Program Results (f04amfe.r)