Abstract
In this paper, we analyze how to update incomplete Cholesky preconditioners to solve least squares problems using iterative methods when the set of linear relations is updated with some new information, a new variable is added or, contrarily, some information or variable is removed from the set. Our proposed method computes a low-rank update of the preconditioner using a bordering method which is inexpensive compared with the cost of computing a new preconditioner. Moreover, the numerical experiments presented show that this strategy gives, in many cases, a better preconditioner than other choices, including the computation of a new preconditioner from scratch or reusing an existing one.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alexander, S.T., Pan, C.T., Plemmons, R.J.: Analysis of a recursive least squares hyperbolic rotation algorithm for signal processing. Linear Algebra Appl. 98, 3–40 (1988)
Andrew, R., Dingle, N.: Implementing QR factorization updating algorithms on GPUs. Parallel Comput. 40(7), 161–172 (2014). doi:10.1016/j.parco.2014.03.003. http://www.sciencedirect.com/science/article/pii/S0167819114000337. 7th Workshop on Parallel Matrix Algorithms and Applications
Benzi, M., T˚uma, M.: A robust incomplete factorization preconditioner for positive definite matrices. Numer. Linear Algebra Appl. 10(5-6), 385–400 (2003)
Benzi, M., Szyld, D.B., Van Duin, A.: Orderings for incomplete factorization preconditioning of nonsymmetric problems. SIAM J. Sci. Comput. 20(5), 1652–1670 (1999)
Björck, Å.: Numerical methods for Least Squares Problems. SIAM, Philadelphia (1996)
Bru, R., Marín, J., Mas, J., T˚uma, M.: Preconditioned iterative methods for solving linear least squares problems. SIAM J. Sci. Comput. 36(4), A2002–A2022 (2014)
Cerdán, J., Marín, J., Mas, J.: Low-rank upyears of balanced incomplete factorization preconditioners. Numer. Algorithms. doi:10.1007/s11075-016-0151-6 (2016)
Chambers, J.M.: Regression updating. J. Amer. Statist. Assoc. 66, 744–748 (1971)
Davis, T.A., Hu, Y.: The university of florida sparse matrix collection. ACM trans. Math. Software 38(1), 1–25 (2011)
Davis, T.A., Hager, W.W.: Modifying a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 20, 606–627 (1999)
Davis, T.A., Hager, W.W.: Multiple-rank modifications of a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 22, 997–1013 (2001)
Davis, T.A., Hager, W.W.: Row modification of a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 26, 621–639 (2005)
Hammarling, S., Lucas, C.: Updating the QR factorization and the least squares problem. Tech. rep., The University of Manchester, http://www.manchester.ac.uk/mims/eprints (2008)
Olsson, O., Ivarsson, T.: Using the QR factorization to swiftly upyear least squares problems. Thesis report, Centre for Mathematical Sciences. The Faculty of Engineering at Lund University LTH (2014)
Pothen, A., Fan, C.J.: Computing the block triangular form of a sparse matrix. ACM Trans. Math. Software 16, 303–324 (1990)
Saad, Y.: ILUT: A dual threshold incomplete LU factorization. Numer. Linear Algebra Appl. 1(4), 387–402 (1994)
Saad, Y.: Iterative Methods for Sparse Linear Systems. PWS Publishing Co., Boston (1996)
Acknowledgements
We would like to acknowledge the anonymous referees for their helpful comments that substantially contributed to improve this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by Spanish Grants MTM2014-58159-P and MTM2015-68805-REDT.
Rights and permissions
About this article
Cite this article
Marín, J., Mas, J., Guerrero, D. et al. Updating preconditioners for modified least squares problems. Numer Algor 75, 491–508 (2017). https://doi.org/10.1007/s11075-017-0315-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-017-0315-z