krypy.deflation
- Linear Systems Solvers with Deflation¶
The deflation
module provides functions for deflated Krylov subspace
methods. With deflation, a linear system is multiplied with a suitable
projection with the goal of accelerating the overall solution process for the
linear system. This module provides tools that are needed in deflated Krylov
subspace methods such as involved projections and computations of Ritz or
harmonic Ritz pairs from a deflated Krylov subspace.
-
class
krypy.deflation.
DeflatedCg
(*args, **kwargs)¶ Bases:
krypy.deflation._DeflationMixin
,krypy.linsys.Cg
Deflated preconditioned CG method.
See
_DeflationMixin
andCg
for the documentation of the available parameters.-
_apply_projection
(Av)¶ Computes \(\langle C,M_lAM_rV_n\rangle\) efficiently with a three-term recurrence.
-
-
class
krypy.deflation.
DeflatedMinres
(linear_system, U=None, projection_kwargs=None, *args, **kwargs)¶ Bases:
krypy.deflation._DeflationMixin
,krypy.linsys.Minres
Deflated preconditioned MINRES method.
See
_DeflationMixin
andMinres
for the documentation of the available parameters.
-
class
krypy.deflation.
DeflatedGmres
(linear_system, U=None, projection_kwargs=None, *args, **kwargs)¶ Bases:
krypy.deflation._DeflationMixin
,krypy.linsys.Gmres
Deflated preconditioned GMRES method.
See
_DeflationMixin
andGmres
for the documentation of the available parameters.
-
class
krypy.deflation.
_DeflationMixin
(linear_system, U=None, projection_kwargs=None, *args, **kwargs)¶ Bases:
object
Mixin class for deflation in Krylov subspace methods.
Can be used to add deflation functionality to any solver from
linsys
.Parameters: - linear_system – the
LinearSystem
that should be solved. - U – a basis of the deflation space with
U.shape == (N, k)
.
All other parameters are passed through to the underlying solver from
linsys
.-
B_
¶ \(\underline{B}=\langle V_{n+1},M_lAM_rU\rangle\).
This property is obtained from \(C\) if the operator is self-adjoint. Otherwise, the inner products have to be formed explicitly.
-
C
= None¶ \(C=\langle U,M_lAM_rV_n\rangle\).
This attribute is updated while the Arnoldi/Lanczos method proceeds. See also
_apply_projection()
.
-
E
= None¶ \(E=\langle U,M_lAM_rU\rangle\).
-
_apply_projection
(Av)¶ Apply the projection and store inner product.
Parameters: v – the vector resulting from an application of \(M_lAM_r\) to the current Arnoldi vector. (CG needs special treatment, here).
-
_get_initial_residual
(x0)¶ Return the projected initial residual.
Returns \(MPM_l(b-Ax_0)\).
-
_get_xk
(yk)¶
-
_solve
()¶
-
estimate_time
(nsteps, ndefl, deflweight=1.0)¶ Estimate time needed to run nsteps iterations with deflation
Uses timings from
linear_system
if it is an instance ofTimedLinearSystem
. Otherwise, anOtherError
is raised.Parameters: - nsteps – number of iterations.
- ndefl – number of deflation vectors.
- deflweight – (optional) the time for the setup and application of the projection for deflation is multiplied by this factor. This can be used as a counter measure for the evaluation of Ritz vectors. Defaults to 1.
-
projection
= None¶ Projection that is used for deflation.
- linear_system – the
-
class
krypy.deflation.
ObliqueProjection
(linear_system, U, qr_reorthos=0, **kwargs)¶ Bases:
krypy.deflation._Projection
Oblique projection for left deflation.
-
AU
= None¶ Result of application of operator to deflation space, i.e., \(M_lAM_rU\).
-
MAU
¶ Result of preconditioned operator to deflation space, i.e., \(MM_lAM_rU\).
-
U
= None¶ An orthonormalized basis of the deflation space
U
with respect to provided inner product.
-
correct
(z)¶ Correct the given approximate solution
z
with respect to the linear systemlinear_system
and the deflation space defined byU
.
-
-
class
krypy.deflation.
_Projection
(linear_system, U, **kwargs)¶ Bases:
krypy.utils.Projection
Abstract base class of a projection for deflation.
Parameters: - A – the
LinearSystem
. - U – basis of the deflation space with
U.shape == (N, d)
.
All parameters of
Projection
are valid exceptX
andY
.- A – the
-
class
krypy.deflation.
Ritz
(deflated_solver, mode='ritz')¶ Bases:
object
Compute Ritz pairs from a deflated Krylov subspace method.
Parameters: - deflated_solver – an instance of a deflated solver.
- mode –
(optional)
ritz
(default): compute Ritz pairs.harmonic
: compute harmonic Ritz pairs.
-
coeffs
= None¶ Coefficients for Ritz vectors in the basis \([V_n,U]\).
-
get_explicit_residual
(indices=None)¶ Explicitly computes the Ritz residual.
-
get_explicit_resnorms
(indices=None)¶ Explicitly computes the Ritz residual norms.
-
get_vectors
(indices=None)¶ Compute Ritz vectors.
-
resnorms
= None¶ Residual norms of Ritz pairs.
-
values
= None¶ Ritz values.
-
class
krypy.deflation.
Arnoldifyer
(deflated_solver)¶ Bases:
object
Obtain Arnoldi relations for approximate deflated Krylov subspaces.
Parameters: deflated_solver – an instance of a deflated solver. -
get
(Wt, full=False)¶ Get Arnoldi relation for a deflation subspace choice.
Parameters: - Wt – the coefficients \(\tilde{W}\) of the deflation vectors
in the basis \([V_n,U]\) with
Wt.shape == (n+d, k)
, i.e., the deflation vectors are \(W=[V_n,U]\tilde{W}\). Must fulfill \(\tilde{W}^*\tilde{W}=I_k\). - full – (optional) should the full Arnoldi
basis and the full perturbation be returned? Defaults to
False
.
Returns: Hh
: the Hessenberg matrix withHh.shape == (n+d-k, n+d-k)
.Rh
: the perturbation core matrix withRh.shape == (l, n+d-k)
.q_norm
: norm \(\|q\|_2\).vdiff_norm
: the norm of the difference of the initial vectors \(\tilde{v}-\hat{v}\).PWAW_norm
: norm of the projection \(P_{\mathcal{W}^\perp,A\mathcal{W}}\).Vh
: (iffull == True
) the Arnoldi basis withVh.shape == (N, n+d-k)
.F
: (iffull == True
) the perturbation matrix \(F=-Z\hat{R}\hat{V}_n^* - \hat{V}_n\hat{R}^*Z^*\).
- Wt – the coefficients \(\tilde{W}\) of the deflation vectors
in the basis \([V_n,U]\) with
-
-
krypy.deflation.
bound_pseudo
(arnoldifyer, Wt, g_norm=0.0, G_norm=0.0, GW_norm=0.0, WGW_norm=0.0, tol=1e-06, pseudo_type='auto', pseudo_kwargs=None, delta_n=20, terminate_factor=1.0)¶ Bound residual norms of next deflated system.
Parameters: - arnoldifyer – an instance of
Arnoldifyer
. - Wt – coefficients \(\tilde{W}\in\mathbb{C}^{n+d,k}\) of the
considered deflation vectors \(W\) for the basis \([V,U]\)
where
V=last_solver.V
andU=last_P.U
, i.e., \(W=[V,U]\tilde{W}\) and \(\mathcal{W}=\operatorname{colspan}(W)\). Must fulfill \(\tilde{W}^*\tilde{W}=I_k\). - g_norm – norm \(\|g\|\) of difference \(g=c-b\) of right hand sides. Has to fulfill \(\|g\|<\|b\|\).
- G_norm – norm \(\|G\|\) of difference \(G=B-A\) of operators.
- GW_norm – Norm \(\|G|_{\mathcal{W}}\|\) of difference \(G=B-A\) of operators restricted to \(\mathcal{W}\).
- WGW_norm – Norm \(\|\langle W,GW\rangle\|_2\).
- pseudo_type –
One of
'auto'
: determines if \(\hat{H}\) is non-normal, normal or Hermitian and uses the corresponding mode (see other options below).'nonnormal'
: the pseudospectrum of the Hessenberg matrix \(\hat{H}\) is used (involves one computation of a pseudospectrum)'normal'
: the pseudospectrum of \(\hat{H}\) is computed efficiently by the union of circles around the eigenvalues.'hermitian'
: the pseudospectrum of \(\hat{H}\) is computed efficiently by the union of intervals around the eigenvalues.'contain'
: the pseudospectrum of the extended Hessenberg matrix \(\begin{bmatrix}\hat{H}\\S_i\end{bmatrix}\) is used (pseudospectrum has to be re computed for each iteration).'omit'
: do not compute the pseudospectrum at all and just use the residual bounds from the approximate Krylov subspace.
- pseudo_kwargs – (optional) arguments that are passed to the method that computes the pseudospectrum.
- terminate_factor – (optional) terminate the computation if the ratio of two subsequent residual norms is larger than the provided factor. Defaults to 1.
- arnoldifyer – an instance of