276
Views
2
CrossRef citations to date
0
Altmetric
Articles

Conjugate gradients for symmetric positive semidefinite least-squares problems

&
Pages 2229-2239 | Received 30 Nov 2015, Accepted 20 Jul 2017, Published online: 10 Sep 2017
 

ABSTRACT

The cgSLS (conjugate gradients for symmetric positive semidefinite least-squares) algorithm is presented. The algorithm exploits the cyclic property of invariant Krylov spaces to reduce the least-squares problem with a symmetric positive semidefinite matrix A to the minimization of the related energy function with the Hessian A on the range of A, so that a simple modification of the conjugate gradient (CG) method is applicable. At the same time, the algorithm generates approximations of the projection of the right-hand side to the range of A. The asymptotic rate of convergence of the new algorithm is proved to be the same as that of the CG method for the related consistent problem. An error bound in terms of the square root of the regular condition number of A is also given. The performance of the algorithm is demonstrated by numerical experiments.

2010 AMS SUBJECT CLASSIFICATIONS:

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the European Regional Development Fund in the IT4Innovations Centre of Excellence project [CZ.1.05/1.1.00/02.0070], by the project SPOMECH reg. no. CZ.1.07/2.3.00/20.0070, and by the project of major infrastructures for research, development and innovation of MEYS with reg. num. LM2011033.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.