### HSL_MI35 Sparse least squares: incomplete factorization preconditioner

HSL_MI35 computes an incomplete factorization preconditioner that may be
used in the solution of weighted sparse linear least squares problems. Given an
$m\times n$
($m\ge n$) sparse
matrix $A=\left\{{a}_{ij}\right\}$ and an
$m\times m$ diagonal matrix
of weights $W$,
HSL_MI35 computes an incomplete factorization of the matrix

$$C={A}^{T}{W}^{2}A.$$

The matrix $C$
may be optionally reordered, scaled and, if necessary, shifted to avoid
breakdown of the factorization. The computed lower triangular matrix
$L$ is such
that $L{L}^{T}$
is an incomplete factorization of

$$\overline{C}=S{Q}^{T}CQS+\alpha I,$$

where $Q$ is a permutation
matrix, $S$ is a diagonal
scaling matrix and $\alpha $
is a non-negative shift. The incomplete factorization may be used for preconditioning
when solving the normal equations

$${A}^{T}{W}^{2}Ax={A}^{T}{W}^{2}b.$$

A separate entry performs the preconditioning operation

$$y=Pz$$

where $P={\left(\overline{L}{\overline{L}}^{T}\right)}^{-1}$
is the incomplete factorization preconditioner and
$\overline{L}=Q{S}^{-1}L$.

The incomplete factorization is based on a matrix decomposition of the
form

$$\overline{C}=L{L}^{T}+L{R}^{T}+R{L}^{T}-E,$$
where $L$
is lower triangular with positive diagonal entries,
$R$ is a
strictly lower triangular matrix with small entries that is used to stabilize the factorization
process, and $E$
has the structure

$$E=R{R}^{T}+F+{F}^{T},$$
where $F$ is strictly lower
triangle. $F$ is discarded
while $R$ is used in the
computation of $L$
but is then discarded. The user controls the dropping of small entries from
$L$ and
$R$
and the maximum number of entries within each column of
$L$ and
$R$ (and thus the amount
of memory for $L$
and the intermediate work and memory used in computing the incomplete
factorization).

The incomplete factorization may be computed with or without forming
$C$
explicitly; the advantage of the latter option being that less memory is required.