# 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)

Deflated preconditioned CG method.

See _DeflationMixin and Cg 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, *args, **kwargs)

Deflated preconditioned MINRES method.

See _DeflationMixin and Minres for the documentation of the available parameters.

class krypy.deflation.DeflatedGmres(linear_system, U=None, *args, **kwargs)

Deflated preconditioned GMRES method.

See _DeflationMixin and Gmres for the documentation of the available parameters.

class krypy.deflation._DeflationMixin(linear_system, U=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()
projection = None

Projection that is used for deflation.

class krypy.deflation.ObliqueProjection(linear_system, U, **kwargs)

Oblique projection for left deflation.

AU = None

Result of application of operator to deflation space, i.e., $$M_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 system linear_system and the deflation space defined by U.

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 except X and Y.

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. Hh: the Hessenberg matrix with Hh.shape == (n+d-k, n+d-k). Rh: the perturbation core matrix with Rh.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: (if full == True) the Arnoldi basis with Vh.shape == (N, n+d-k). F: (if full == True) the perturbation matrix $$F=-Z\hat{R}\hat{V}_n^* - \hat{V}_n\hat{R}^*Z^*$$.
krypy.deflation.bound_pseudo(arnoldifyer, Wt, b_norm, g_norm=0.0, G_norm=0.0, GW_norm=0.0, WGW_norm=0.0, tol=1e-06, method='gmres', pseudo_type='auto', delta_n=20, delta_exp=5)

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 and U=last_P.U, i.e., $$W=[V,U]\tilde{W}$$ and $$\mathcal{W}=\operatorname{colspan}(W)$$. Must fulfill $$\tilde{W}^*\tilde{W}=I_k$$. b_norm – norm $$\|b\|$$ of right hand side. g_norm – norm $$\|g\|$$ of difference $$g=c-b$$ of right hand sides. 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$$. method – type of method that is used to construct the residuals and residual/error polynomial from $$\hat{H}$$: 'cg': for the CG method 'minres': for the MINRES method 'gmres': for the GMRES method 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).