- -

Low-rank updates of balanced incomplete factorization preconditioners

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

  • Estadisticas de Uso

Low-rank updates of balanced incomplete factorization preconditioners

Show simple item record

Files in this item

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


This item appears in the following Collection(s)

Show simple item record