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 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, projection_kwargs=None, *args, **kwargs)

Bases: krypy.deflation._DeflationMixin, krypy.linsys.Minres

Deflated preconditioned MINRES method.

See _DeflationMixin and Minres 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 and Gmres 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 of TimedLinearSystem. Otherwise, an OtherError 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.

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 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.
Returns:

  • 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, 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 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\).
  • 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.