KSPLSQR

Implements LSQR [PS82]

Options Database Keys

• -ksp_lsqr_set_standard_error - set standard error estimates of solution, see KSPLSQRSetComputeStandardErrorVec() and KSPLSQRGetStandardErrorVec()

• -ksp_lsqr_exact_mat_norm - compute the exact matrix norm instead of using an iteratively refined estimate, see KSPLSQRSetExactMatNorm()

• -ksp_lsqr_monitor - monitor residual norm, norm of residual of normal equations \(A^T A x = A^T b \), and estimate of matrix norm \(||A||\)

Notes

Supports non-square (rectangular) matrices. See PETSCREGRESSORLINEAR for the PETSc toolkit for solving linear regression problems, including least squares.

This variant, when applied with no preconditioning is identical to the original published algorithm in exact arithmetic; however, in practice, with no preconditioning due to inexact arithmetic, it can converge differently. Hence when no preconditioner is used (PCType PCNONE) it automatically reverts to the original algorithm.

With the PETSc built-in preconditioners, such as PCICC, one should call KSPSetOperators(ksp,A,A^T*A)) since the preconditioner needs to work for the normal equations \(^T A\). For example, use MatCreateNormal().

Supports only left preconditioning.

For least squares problems with nonzero residual \(A x - b\), there are additional convergence tests for the residual of the normal equations, \(A^T (b - Ax)\), see KSPLSQRConvergedDefault(). see KSPLSQRConvergedDefault().

In exact arithmetic the LSQR method (with no preconditioning) is identical to the KSPCG algorithm applied to the normal equations. The preconditioned variant was implemented by Bas van’t Hof and is essentially a left preconditioning for the normal equations. It appears the implementation with preconditioning tracks the true (unpreconditioned) norm of the residual and uses that in the convergence test.

Developer Note

How is this related to the KSPCGNE implementation? One difference is that KSPCGNE applies the preconditioner transpose times the preconditioner, so one does not need to pass \(A^T*A\) as the third argument to KSPSetOperators().

References

[PS82]

C. C. Paige and M. A. Saunders. LSQR: an algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software, 8:43–71, 1982.

See Also

KSP: Linear System Solvers, KSPCreate(), KSPSetType(), KSPType, KSP, KSPSolve(), KSPLSQRConvergedDefault(), KSPLSQRSetComputeStandardErrorVec(), KSPLSQRGetStandardErrorVec(), KSPLSQRSetExactMatNorm(), KSPLSQRMonitorResidualDrawLGCreate(), KSPLSQRMonitorResidualDrawLG(), KSPLSQRMonitorResidual(), PETSCREGRESSORLINEAR

Level

beginner

Location

src/ksp/ksp/impls/lsqr/lsqr.c

Examples

src/ksp/ksp/tutorials/ex27.c

---

Index of all KSP routines
Table of Contents for all manual pages
Index of all manual pages