## Version 2.0.0

30 March 2021

Recent Changes

Code Download

• Single
• Double

### 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×n$ ($m\ge n$) sparse matrix $A=\left\{{a}_{ij}\right\}$ and an $m×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.