dc.contributor.author |
Cerdán Soriano, Juana Mercedes
|
es_ES |
dc.contributor.author |
Marín Mateos-Aparicio, José
|
es_ES |
dc.contributor.author |
Mas Marí, José
|
es_ES |
dc.date.accessioned |
2018-09-17T07:09:27Z |
|
dc.date.available |
2018-09-17T07:09:27Z |
|
dc.date.issued |
2017 |
es_ES |
dc.identifier.issn |
1017-1398 |
es_ES |
dc.identifier.uri |
http://hdl.handle.net/10251/107359 |
|
dc.description.abstract |
[EN] Let Ax = b be a large and sparse system of linear equations where A is a nonsingular matrix. An approximate solution is frequently obtained by applying preconditioned terations. Consider the matrix B = A + PQT where P,Q ∈ Rn×k are full rank matrices. In this work, we study the problem of updating a previously computed preconditioner for A in order to solve the updated linear system Bx = b by preconditioned iterations. In particular, we propose a method for updating a Balanced Incomplete Factorization preconditioner. The strategy is based on the computation of an approximate Inverse Sherman-Morrison decomposition for an equivalent augmented linear system. Approximation properties of the preconditioned matrix and an analysis of the computational cost of the algorithm are studied. Moreover the results of the numerical experiments with different types of problems show that the proposed method contributes to accelerate the convergence. |
es_ES |
dc.description.sponsorship |
This work was supported by the Spanish Ministerio de Economia y Competitividad under grant MTM2014-58159-P. |
|
dc.language |
Inglés |
es_ES |
dc.publisher |
Springer-Verlag |
es_ES |
dc.relation.ispartof |
Numerical Algorithms |
es_ES |
dc.rights |
Reserva de todos los derechos |
es_ES |
dc.subject |
Iterative methods |
es_ES |
dc.subject |
Preconditioning |
es_ES |
dc.subject |
Low rank update |
es_ES |
dc.subject |
Balanced incomplete factorization |
es_ES |
dc.subject |
Sparse linear systems |
es_ES |
dc.subject.classification |
MATEMATICA APLICADA |
es_ES |
dc.title |
Low-rank updates of balanced incomplete factorization
preconditioners |
es_ES |
dc.type |
Artículo |
es_ES |
dc.identifier.doi |
10.1007/s11075-016-0151-6 |
es_ES |
dc.relation.projectID |
info:eu-repo/grantAgreement/MINECO//MTM2014-58159-P/ES/PRECONDICIONADORES PARA SISTEMAS DE ECUACIONES LINEALES, PROBLEMAS DE MINIMOS CUADRADOS, CALCULO DE VALORES PROPIOS Y APLICACIONES TECNOLOGICAS/ |
es_ES |
dc.rights.accessRights |
Abierto |
es_ES |
dc.contributor.affiliation |
Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada |
es_ES |
dc.description.bibliographicCitation |
Cerdán Soriano, JM.; Marín Mateos-Aparicio, J.; Mas Marí, J. (2017). Low-rank updates of balanced incomplete factorization
preconditioners. Numerical Algorithms. 74(2):337-370. https://doi.org/10.1007/s11075-016-0151-6 |
es_ES |
dc.description.accrualMethod |
S |
es_ES |
dc.relation.publisherversion |
http://doi.org/10.1007/s11075-016-0151-6 |
es_ES |
dc.description.upvformatpinicio |
337 |
es_ES |
dc.description.upvformatpfin |
370 |
es_ES |
dc.type.version |
info:eu-repo/semantics/publishedVersion |
es_ES |
dc.description.volume |
74 |
es_ES |
dc.description.issue |
2 |
es_ES |
dc.relation.pasarela |
S\325855 |
es_ES |
dc.contributor.funder |
Ministerio de Economía, Industria y Competitividad |
es_ES |
dc.description.references |
Bellavia, S., Bertaccini, D., Morini, B.: Nonsymmetric preconditioner updates in Newton-Krylov methods for nonlinear systems. SIAM J. Sci. Comput. 33 (5), 2595–2619 (2011) |
es_ES |
dc.description.references |
Benzi, M., Bertaccini, D.: Approximate inverse preconditioning for shifted linear systems. BIT 43(2), 231–244 (2003) |
es_ES |
dc.description.references |
Bergamaschi, L., Bru, R., Martínez, A.: Low-rank update of preconditioners for the inexact Newton method with SPD Jacobian. Math. Comput. Model. 54, 1863–1873 (2011) |
es_ES |
dc.description.references |
Bergamaschi, L., Bru, R., Martínez, A., Mas, J., Putti, M.: Low-rank update of preconditioners for the nonlinear Richards Equation. Math. Comput. Model. 57, 1933–1941 (2013) |
es_ES |
dc.description.references |
Bergamaschi, L., Gondzio, J., Venturin, M., Zilli, G.: Inexact constraint preconditioners for linear systems arising in interior point methods. Comput. Optim. Appl. 36(2-3), 137–147 (2007) |
es_ES |
dc.description.references |
Beroiz, M., Hagstrom, T., Lau, S.R., Price, R.H.: Multidomain, sparse, spectral-tau method for helically symmetric flow. Comput. Fluids 102(0), 250–265 (2014) |
es_ES |
dc.description.references |
Bertaccini, D.: Efficient preconditioning for sequences of parametric complex symmetric linear systems. Electron. Trans. Numer. Anal. 18, 49–64 (2004) |
es_ES |
dc.description.references |
Bollhöfer, M.: A robust and efficient ILU that incorporates the growth of the inverse triangular factors. SIAM J. Sci. Comput. 25(1), 86–103 (2003) |
es_ES |
dc.description.references |
Bollhöfer, M., Saad, Y.: On the relations between ILUs and factored approximate inverses. SIAM. J. Matrix Anal. Appl. 24(1), 219–237 (2002) |
es_ES |
dc.description.references |
Bru, R., Cerdán, J., Marín, J., Mas, J.: Preconditioning sparse nonsymmetric linear systems with the Sherman-Morrison formula. SIAM J. Sci. Comput. 25(2), 701–715 (2003) |
es_ES |
dc.description.references |
Bru, R., Marín, J., Mas, J., Tůma, M.: Balanced incomplete factorization. SIAM J. Sci. Comput. 30(5), 2302–2318 (2008) |
es_ES |
dc.description.references |
Bru, R., Marín, J., Mas, J., Tůma, M.: Improved balanced incomplete factorization. SIAM J. Matrix Anal. Appl. 31(5), 2431–2452 (2010) |
es_ES |
dc.description.references |
Cerdán, J., Faraj, T., Malla, N., Marín, J., Mas, J.: Block approximate inverse preconditioners for sparse nonsymmetric linear systems. Electron. Trans. Numer. Anal. 37, 23–40 (2010) |
es_ES |
dc.description.references |
Cerdán, J., Marín, J., Mas, J., Tůma, M.: Block balanced incomplete factorization. Technical Report No. TR-IMM2015/04, Polytechnic University of Valencia, Spain (2015) |
es_ES |
dc.description.references |
Davis, T.A.: University of Florida Sparse Matrix Collection. available online at http://www.cise.ufl.edu/~davis/sparse/ , NA Digest, vol. 94, issue 42, October 1994. |
es_ES |
dc.description.references |
Tebbens, J.D., Tůma, M.: Efficient preconditioning of sequences of nonsymmetric linear systems. SIAM J. Sci Comput. 29(5), 1918–1941 (2007) |
es_ES |
dc.description.references |
Tebbens, J.D., Tůma, M.: Preconditioner updates for solving sequences of linear systems in matrix-free environment. Numer Linear Algebra Appl. 17, 997–1019 (2010) |
es_ES |
dc.description.references |
Embree, M., Sifuentes, J.A., Soodhalter, K.M., Szyld, D.B., Xue, F.: Short-term recurrence Krylov subspace methods for nearly hermitian matrices. SIAM.J. Matrix Anal. Appl. 33-2, 480–500 (2012) |
es_ES |
dc.description.references |
Engquist, B., Ying, L.: Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation. Commun. Pure Appl. Math. 64, 697–735 (2011) |
es_ES |
dc.description.references |
Gatto, P., Christiansen, R.E., Hesthaven, J.S.: A preconditioner based on a low-rank approximation with applications to topology optimization. Technical Report EPFL-ARTICLE-207108, École polytechnique fédérale de Lausanne, EPFL, CH-1015 Lausanne, 2015. |
es_ES |
dc.description.references |
Grasedyck, L., Hackbusch, W.: Construction and arithmetics of H-matrices. Computing 70(4), 295–334 (2003) |
es_ES |
dc.description.references |
Grasedyck, L., Kressner, D., Tobler, C.: A literature survey of low-rank tensor approximation techniques. GAMM-Mitteilungen 36(1), 53–78 (2013) |
es_ES |
dc.description.references |
Greengard, L., Rokhlin, V.: A new version of the fast multipole method for the Laplace equation in three dimensions. Acta Numer. 6(1), 229–269 (1997) |
es_ES |
dc.description.references |
Hager, W.W.: Updating the inverse of matrix. SIAM Rev. 31(2), 221–239 (1989) |
es_ES |
dc.description.references |
Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011) |
es_ES |
dc.description.references |
Kelley, C.T.: Solving Nonlinear Equations with Newton’s Method. Fundamentals of algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2003) |
es_ES |
dc.description.references |
Saad, Y.: ILUT: a dual threshold incomplete L U factorization. Numer. Linear Algebra Appl. 1(4), 387–402 (1994) |
es_ES |
dc.description.references |
Saad, Y., Schulz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7, 856–869 (1986) |
es_ES |
dc.description.references |
Simoncini, V., Szyld, D.B.: The effect of non-optimal bases on the convergence of Krylov subspace methods. Numer Math. 100(4), 711–733 (2005) |
es_ES |
dc.description.references |
van der Vorst, H.A.: Bi-CGSTAB: a fast and smoothly converging variant of bi-CG for the solution of non-symmetric linear systems. SIAM J. Sci. Stat. Comput. 12, 631–644 (1992) |
es_ES |