Deflated iterative methods

In Vui99SM the Deflated ICCG method is presented to solve problems with large jumps in the coefficients on layered domains. The idea of deflation combined with an iterative solver is also presented in papers of Nicolaides and Mansfield. It appears that the convergence of DICCG is independent of the size of the jump in the coefficients

The method is generalized to arbitrary domains in Vui01SMW. The deflation vectors used in this paper are denoted as "physical" deflation vectors, because their shape resembles the shape of the eigenvectors. This method is succesfully applied to electromagnetical problems in the paper:

H. De Gersem and K. Hameyer
A deflated iterative solver for magnetostatic finite element models with large differences in permeability
Eur. Phys. J. Appl. Phys., 13, 45-49, 2000

In Fra01V a parallel version of Deflated Krylov subspace methods are given. The deflation vectors are 1 in one subdomain and 0 in all other subdomains. These vectors are called "algebraic" deflation vectors. It appears that the convergence is independent of the number of subdomains. In Vui02SYD a comparison is given of the various choices of the deflation vectors.

For some software see the Deflated Krylov method page.

Other relevant publications are given below.

J. Vandenplas and B-V. Nguyen and C. Vuik (pdf, bibtex)
Deflation techniques applied on mixed model equations
Journal of Computational and Applied Mathematics, 426, 115095, 2023

N. Bootland and V. Dwarka and P. Jolivet and V. Dolean and C. Vuik (pdf, bibtex)
Inexact Subdomain Solves Using Deflated GMRES for Helmholtz Problems
Domain Decomposition Methods in Science and Engineering XXVI, editors S.C. Brenner and E. Chung and A. Klawonn and F. Kwok and J. Xu and J. Zou
Lecture Notes in Computational Science and Engineering book series LNCSE, volume 145, pp. 127-135, Springer, Cham, 2023

G.B. Diaz and J.D. Jansen and C. Vuik (pdf, bibtex)
Accelerating the solution of linear systems appearing in two-phase reservoir simulation by the use of POD-based deflation methods
Computational Geosciences, 25, pp 1621-1621, 2021

V. Dwarka and C. Vuik (pdf, bibtex)
Pollution and accuracy of solutions of the Helmholtz equation: A novel perspective from the eigenvalues
Journal of Computational and Applied Mathematics, 395, 113549, 2021

J. Vandenplas and M.P.L. Calus and H. Eding and M. van Pelt and R. Bergsma and C. Vuik (pdf, bibtex)
Convergence behavior of single-step GBLUP and SNPBLUP for different termination criteria
Genetics Selection Evolution, 53:34, 2021

Niall Bootland, Vandana Dwarka, Pierre Jolivet, Victorita Dolean, and Cornelis Vuik (pdf)
Inexact subdomain solves using deflated GMRES for Helmholtz problems
https://arxiv.org/abs/2103.17081

V. Dwarka and C. Vuik (pdf, bibtex)
Scalable Convergence Using Two-Level Deflation Preconditioning for the Helmholtz Equation
SIAM Journal of Scientific Computing, 42, pp. A901-A928, 2020

V. Dwarka and R. Tielen and M. Moller and C. Vuik (pdf)
Towards Accuracy and Scalability: Combining Isogeometric Analysis with Deflation to Obtain Scalable Convergence for the Helmholtz Equation
https://arxiv.org/abs/2010.10232

V. Dwarka and C. Vuik (pdf, bibtex)
Scalable multi-level deflation preconditioning for the highly indefinite Helmholtz equation
Delft University of Technology
Delft Institute of Applied Mathematics
Report 20-04, 2020
ISSN 1389-6520

J. Vandenplas and M.P.L. Calus and H. Eding and C. Vuik (pdf1, pdf2, bibtex)
A second-level diagonal preconditioner for single-step SNPBLUP
Genetics Selection Evolution, 51:30, pp. 1-16, 2019

J. Vandenplas and H. Eding and M.P.L. Calus and C. Vuik (pdf, bibtex)
Deflated preconditioned conjugate gradient method for solving single-step single nucleotide polymorphism BLUP
Proceedings of the World Congress on Genetics Applied to Livestock Production 11.25, pp. 1-7, 2018

J. Vandenplas and H. Eding and M.P.L. Calus and C. Vuik (pdf1, pdf2, bibtex)
Deflated preconditioned conjugate gradient method for solving single-step BLUP models efficiently
Genetics Selection Evolution, 50:51, pp. 1-17, 2018

G.B. Diaz Cortes and C. Vuik and J.D. Jansen (pdf, bibtex)
On POD-based Deflation Vectors for DPCG applied to porous media problems
Journal of Computational and Applied Mathematics, 330, pp. 193-213, 2018

A.H. Sheikh and D. Lahaye and L. Garcia Ramos and R. Nabben and C. Vuik (pdf, bibtex)
Accelerating the shifted Laplace preconditioner for the Helmholtz equation by multilevel deflation
Journal of Computational Physics, 322, pp. 473-490, 2016

R. Gupta and D. Lukarski and M.B. van Gijzen and C. Vuik (pdf, bibtex)
Evaluation of the Deflated Preconditioned CG method to solve Bubbly and Porous Media Flow Problems on GPU and CPU
International Journal for Numerical Methods in Fluids, 80, pp. 666-683, 2016

G.B. Diaz Cortes and C. Vuik and J.D. Jansen (pdf, bibtex)
Physics-based Pre-conditioners for Large-scale Subsurface Flow Simulation
ECMOR XV - 15th European Conference on the Mathematics of Oil Recovery, August 29 - September 1, 2016 Editor: J.D. Jansen EAGE, Houten, 2016 DOI: 10.3997/2214-4609.201601801

A. Lukyanov and C. Vuik (pdf, bibtex)
Parallel Fully Implicit Smoothed Particle Hydrodynamics Based Multiscale Method
ECMOR XV - 15th European Conference on the Mathematics of Oil Recovery, August 29 - September 1, 2016 Editor: J.D. Jansen EAGE, Houten, 2016 DOI: 10.3997/2214-4609.201601748

J.H. van der Linden and T.B. Jonsthovel and A.A. Lukyanov and C. Vuik (pdf, bibtex)
The parallel subdomain-levelset deflation method in reservoir simulation Journal of Computational Physics, 304, pp. 340-358, 2016

P. van Slingerland and C. Vuik (pdf, bibtex)
Scalable two-level preconditioning and deflation based on a piecewise constant subspace for (SIP)DG systems for diffusion problems Journal of Computational and Applied Mathematics, 275, pp. 61-78, 2015

F.J. Lingen and P.G. Bonnier and R.B.J. Brinkgreve and M.B. van Gijzen and C. Vuik (pdf, bibtex)
A parallel linear solver exploiting the physical properties of the underlying mechanical problem Computational Geosciences, 18, pp. 913-926, 2014

P. van Slingerland and C. Vuik (pdf, bibtex)
Fast linear solver for diffusion problems with applications to pressure computation in layered domains
Computational Geosciences, 18, pp. 343-356, 2014

A.H. Sheikh and D. Lahaye and C. Vuik (pdf, bibtex)
On the convergence of shifted Laplace preconditioner combined with multilevel deflation
Numerical Linear Algebra with Applications, 20, pp. 645-662, 2013

T.B. Jonsthovel and M.B. van Gijzen and C.Vuik and A. Scarpas (pdf, bibtex)
On the Use of Rigid Body Modes in the Deflated Preconditioned Conjugate Gradient Method
SIAM Journal on Scientific Computing, 35, pp. B207-B225, 2013

T.B. Jonsthovel and M.B. van Gijzen and S. MacLachlan and C.Vuik and A. Scarpas (pdf, bibtex)
Comparison of the deflated preconditioned conjugate gradient method and algebraic multigrid for composite materials
Computational Mechanics, 50, pp. 321-333, 2012

M.H. Carpenter and C. Vuik and P. Lucas and M.B. van Gijzen and H. Bijl (pdf, bibtex)
A General Algorithm for Reusing Krylov Subspace Information. I. Unsteady Navier-Stokes NASA, Langley Research Center, 2010 NASA/TM2010216190
E. van 't Wout and M.B. van Gijzen and A. Ditzel and A. van der Ploeg and C. Vuik (pdf, bibtex)
The Deflated Relaxed Incomplete Cholesky CG method for use in a real-time ship simulator
Procedia Computer Science, 1, pp. 249-257, 2010

J.M. Tang and S.P. MacLachlan and R. Nabben and C. Vuik (pdf, bibtex)
A Comparison of Two-Level Preconditioners Based on Multigrid and Deflation
SIAM. J. Matrix Anal. and Appl., 31, pp. 1715-1739, 2010

T.B. Jonsthovel, M.B. van Gijzen, C.Vuik, C. Kasbergen, and A. Scarpas (pdf, bibtex)
Preconditioned conjugate gradient method enhanced by deflation of rigid body modes applied to composite materials
Computer Modeling in Engineering and Sciences, 47, pp. 97-118, 2009
J.M. Tang and R. Nabben and C. Vuik and Y.A. Erlangga (pdf, bibtex)
Comparison of Two-Level Preconditioners Derived from Deflation, Domain Decomposition and Multigrid Methods
Journal of Scientific Computing, 39, pp. 340-370, 2009
S.P. MacLachlan and J.M. Tang and C. Vuik (pdf, bibtex)
Fast and Robust Solvers for Pressure Correction in Bubbly Flow Problems
Journal of Computational Physics, 227, pp. 9742-9761, 2008
J.M. Tang and C. Vuik ( pdf, bibtex)
Acceleration of preconditioned Krylov solvers for bubbly flow problems
Parallel Processing and Applied Mathematics 7th International Conference, PPAM 2007, Gdansk, Poland, September 9-12, 2007
Editors R. Wyrzykowski and J. Dongarra and K. Karczewski and J. Wasniewski
pp. 1323--1332, Lecture Notes in Computer Science , Vol. 4967, Springer, Berlin, 2008
R. Nabben and C. Vuik (pdf , bibtex )
A comparison of abstract versions of deflation, balancing and additive coarse grid correction preconditioners
Numer. Linear Algebra Appl., 15, pp. 355-372, 2008
J.M. Tang and C. Vuik (pdf , bibtex )
New Variants of Deflation Techniques for Pressure Correction in Bubbly Flow Problems
Journal of Numerical Analysis, Industrial and Applied Mathematics, Vol.2, pp. 227-249, 2007
J.M. Tang and C. Vuik ( pdf , bibtex )
Efficient Deflation Methods applied to 3-D Bubbly Flow Problems
Electronic Transactions on Numerical Analysis, Vol. 26, pp. 330-349, 2007
J.M. Tang and C. Vuik, pdf, bibtex )
Fast deflation methods with applications to two-phase flows
Delft University of Technology
Delft Institute of Applied Mathematics
Report 07-10
J.M. Tang and R. Nabben and C. Vuik and Y.A. Erlangga ( pdf, bibtex)
Theoretical and numerical comparison of various projection methods derived from deflation, domain decomposition and multigrid methods
Delft University of Technology
Delft Institute of Applied Mathematics
Report 07-04
J.M. Tang and C. Vuik ( pdf, bibtex)
On deflation and singular symmetric positive semi-definite matrices
Journal of Computational and Applied Mathematics, 206, pp. 603-614, 2007
R. Nabben and C. Vuik ( pdf, bibtex )
A Comparison of Deflation and the Balancing Preconditioner
SIAM J. Sci. Comput.,27, pp. 1742-1759, 2006
J. Verkaik and C. Vuik and B.D. Paarhuis and A. Twerda ( pdf, bibtex )
The Deflation Accelerated Schwarz Method for CFD
Computational Science-ICCS 2005: 5th International Conference, Atlanta, GA, USA, May 22-25, 2005, Proceedings, Part I, editor: V.S. Sunderam and G.D. van Albada and P.M.A. Sloot and J.J. Dongarra Springer, Berlin, 2005 pages 868-875
R. Nabben and C. Vuik ( pdf, bibtex)
A comparison of Deflation and Coarse Grid Correction applied to porous media flow
SIAM J. Numer. Anal., 42, pp. 1631-1647, 2004
R. Nabben and C. Vuik ( pdf, bibtex )
A comparison of Deflation and the balancing Neumann-Neumann preconditioner Delft University of Technology
Department of Applied Mathematical Analysis
Report 04-09
ISSN 1389-6520
F. Vermolen, C. Vuik and A. Segal ( pdf, bibtex )
Deflation in preconditioned Conjugate Gradient methods for finite element problems
In: Conjugate Gradient and Finite Element Methods
editors: M. Krizek and P. Neittaanmaki and R. Glowinski and S. Korotov
Springer, Berlin, 2004
pages 103-129
ISBN 3-540-21319-8
C. Vuik and J. Frank and F.J. Vermolen ( bibtex )
Parallel Deflated Krylov methods for incompressible flow
Parallel Computational Fluid Dynamics: Practice and Theory, Proceedings of the Parallel CFD 2001 Conference, Egmond aan Zee, The Netherlands, May 21-23,2001
editors: P. Wilders and A. Ecer and J. Periaux and N. Satofuka and P. Fox
Elsevier, Amsterdam, 2002 pages 381--388
ISBN 0-444-50672-1
C. Vuik and A. Segal and L. El Yaakoubi and E. Dufour ( pdf, bibtex )
A comparison of various deflation vectors applied to elliptic problems with discontinuous coefficients
Applied Numerical Mathematics, 41, pp. 219--233, 2002
C. Vuik and A. Segal and J.A. Meijerink and G.T. Wijma ( pdf, bibtex )
The construction of projection vectors for a Deflated ICCG method applied to problems with extreme contrasts in the coefficients
Journal of Computational Physics, 172, pp. 426--450, 2001
see also Shell Report EP2000-8019
F. Vermolen and C. Vuik (pdf, bibtex )
The influence of deflation vectors at interfaces on the deflated Conjugate Gradient method
Delft University of Technology
Department of Applied Mathematical Analysis
Report 01-13
ISSN 1389-6520
J. Frank and C. Vuik ( pdf, bibtex )
On the construction of deflation-based preconditioners
SIAM Journal on Scientific Computing, 23, pp. 442--462, 2001
see also CWI Report MAS-R0009
C. Vuik and J. Frank ( bibtex , pdf )
Deflated ICCG method applied to problems with extreme contrasts in the coefficients
In: M. Deville and R. Owens (eds.): Proceedings of the 16th IMACS World Congress 2000. Lausanne, August 2000.
CDROM ISBN 3-9522075-1-9,
Rutgers University, New Brunswick, 2000
C. Vuik and A. Segal and J.A. Meijerink and J. Frank ( bibtex )
Deflated ICCG applied to problems with extreme contrasts in the coefficients
Sixth Copper Mountain Conference on Iterative Methods, (virtual proceedings)
Copper Mountain, Colorado, April 2 - April 7, 2000
editors: T.A. Manteuffel and S.F. McCormick
C. Vuik and A. Segal and J.A. Meijerink and G.T. Wijma ( bibtex )
The construction of projection vectors for a Deflated ICCG method applied to problems with extreme contrasts in the coefficients
Shell, 2000
Shell Report EP2000-8019
to appear in: Journal of Computational Physics
C. Vuik and A. Segal and J.A. Meijerink (pdf , bibtex )
An efficient preconditioned CG method for the solution of a class of layered problems with extreme contrasts in the coefficients
J. Comp. Phys., 152, pp. 385-403, 1999.
see also TUD Report 98-20.
C. Vuik and A. Segal and J.A. Meijerink and G.T. Wijma ( bibtex )
The construction of projection vectors for a deflated ICCG method used in problems with a layered structure
1999 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Industrial Applications, Minneapolis, USA, June 10-12, 1999, pp. 225-231
editors: Y. Saad and D. Pierce and W.P. Tang
University of Minnesota Supercomputing Institute, Minneapolis, 1999
related poster
Kees Vuik, Guus Segal and Koos Meijerink,
An efficient CG method for layered problems with large contrasts in the coefficients
Fifth Copper Mountain Conference on Iterative Methods, (virtual proceedings)
Copper Mountain, Colorado, March 30 - April 3, 1998
editors: T.A. Manteuffel and S.F. McCormick

Contact information:

Kees Vuik

Back to the keyword page, or the home page of Kees Vuik