Krylov methods#

Implemented in yastn#

We provide a high-level, backend-agnostic implementation of some Krylov-based algorithms used in yastn.tn.mps. They assume a linear operation acting on a generalized vector, with the vector being an instance of a class that includes methods norm, vdot, add, expand_krylov_space, among others. Examples of such a vector include yastn.Tensor (see methods).

yastn.expmv(f, v, t=1.0, tol=1e-12, ncv=10, hermitian=False, normalize=False, return_info=False, **kwargs) → Vector[source]#

Calculate \(e^{(tF)}v\), where \(v\) is a vector, and \(F(v)\) is linear operator acting on \(v\).

The algorithm of: J. Niesen, W. M. Wright, ACM Trans. Math. Softw. 38, 22 (2012), Algorithm 919: A Krylov subspace algorithm for evaluating the phi-functions appearing in exponential integrators.

Parameters:

f (Callable[[vector], vector]) – defines an action of a “square matrix” on vector.
v (vector) – input vector to apply exponential map onto.
t (number) – exponent amplitude.
tol (number) – targeted tolerance; it is used to update the time-step and size of Krylov space. The returned result should have better tolerance, as correction is included.
ncv (int) – Initial guess for the size of the Krylov space.
hermitian (bool) – Assume that f is a Hermitian operator, in which case Lanczos iterations are used. Otherwise Arnoldi iterations are used to span the Krylov space.
normalize (bool) – Whether to normalize the result to unity using 2-norm.
return_info (bool) – if True, returns (vector, info), where
- info.ncv : guess of the Krylov-space size,
- info.error : estimate of error (likely over-estimate)
- info.krylov_steps : number of execution of f(x),
- info.steps : number of steps to reach t,
kwargs (any) – Further parameters that are passed to expand_krylov_space() and add().

yastn.eigs(f, v0, k=1, which='SR', ncv=10, maxiter=None, tol=1e-13, hermitian=False, **kwargs) → tuple[Sequence[float], Sequence[Vector]][source]#

Search for dominant eigenvalues of linear operator f using Arnoldi algorithm. Economic implementation (without restart) for internal use within yastn.tn.mps.dmrg_().

Parameters:

f (function) – define an action of a ‘square matrix’ on the ‘vector’ v0. f(v0) should preserve the signature of v0.
v0 (Tensor) – Initial guess, ‘vector’ to span the Krylov space.
k (int) – Number of desired eigenvalues and eigenvectors. The default is 1.
which (str) – One of ['LM', 'LR', 'SM', 'SR'] specifying which k eigenvectors and eigenvalues to find: 'LM' : largest magnitude, 'SM' : smallest magnitude, 'LR' : largest real part, 'SR' : smallest real part.
ncv (int) – Dimension of the employed Krylov space. The default is 10. Must be greated than k.
maxiter (int) – Maximal number of restarts; (not implemented for now)
tol (float) – Stopping criterion for an expansion of the Krylov subspace. The default is 1e-13. (not implemented for now)
hermitian (bool) – Assume that f is a Hermitian operator, in which case Lanczos iterations are used. Otherwise Arnoldi iterations are used to span the Krylov space.

yastn.svds(A: Tensor, axes=(0, 1), k=1, ncv=None, tol=0, which='LM', v0=None, maxiter=None, return_singular_vectors=True, solver='arpack', rng=None, options=None, **kwargs) → tuple[Tensor, Tensor, Tensor][source]#

Search for dominant singular values of tensor A using Arnoldi algorithm.

Parameters:

axes (tuple[int, int] | tuple[Sequence[int], Sequence[int]]) – Specify two groups of legs between which to perform SVD, as well as their final order.
v0 (Tensor) – Initial guess, ‘vector’ to span the Krylov space.
k (int = float(‘inf’)) – Number of singular values and singular vectors to compute. Must satisfy 1 <= k <= kmax, where kmax=min(M, N) for solver=’propack’ and kmax=min(M, N) - 1 otherwise.
tol (float, optional) – Tolerance for singular values. Zero (default) means machine precision.
which (str) – One of ['LM', 'LR', 'SM', 'SR'] specifying which D_total singular vectors and singular values to find: 'LM' : largest magnitude, 'SM' : smallest magnitude, 'LR' : largest real part, 'SR' : smallest real part.
Additional kwargs –

sU: int = 1
Signature of the new leg in U; equal to 1 or -1. The default is 1. V is going to have the opposite signature on the connecting leg.

nU: bool = True
Whether or not to attach the charge of a to U. If False, it is attached to V. The default is True.

Uaxis, Vaxis: int, int = -1, 0
specify which leg of U and V tensors are connecting with S. By default, it is the last leg of U and the first of V.

compute_uv: bool = None
alias for return_singular_vectors. When provided, it overrides the value of return_singular_vectors. For syntax consistency with yastn.linalg.svd() and yastn.linalg.svd_with_truncation().

fix_signs: bool = True
Whether or not to fix phases in U and V, so that the largest element in each column of U is positive. Provide uniqueness of decomposition for non-degenerate cases. The default is False.

These parameters govern the truncation of singular triples after leading-k singular triples are found.

reltol: float = 0
relative tolerance of singular values below which to truncate across all blocks.

reltol_block: float = 0
relative tolerance of singular values below which to truncate within individual blocks.

D_total: int = None
alias for k. When provided, it overrides the value of k. For syntax consistency with yastn.linalg.svd() and yastn.linalg.svd_with_truncation().

D_block: int = float(‘inf’)
largest number of singular values to keep in a single block. Default is to keep all.

largest_gap: bool
If True, enlarge the truncation range specified by other arguments by shifting the cut to the largest gap between to-be-truncated singular values across all blocks. It provides a heuristic mechanism to avoid truncating part of a multiplet. If True, tol_block and D_block are ignored, as largest_gap is a global condition. The default is False.

eps_multiplet: float
Relative tolerance on multiplet splitting. If relative difference between two consecutive elements of S is larger than eps_multiplet, these elements are not considered as part of the same multiplet. Partially truncated multiplets are truncated down. The default is None, when this scheme is not used. If True, tol_block and D_block are ignored, as eps_multiplet is a global condition. Cannot be used together with largest_gap scheme.

hermitian: bool
If True, blocks related by hermitian conjugation are truncated equally, truncating down to the intersecting part. The default is False.

mask_f: function[yastn.Tensor] -> yastn.Tensor
custom truncation-mask function. If provided, it overrides all other truncation-related arguments.

yastn.lin_solver(f, b, v0, ncv=10, tol=1e-13, pinv_tol=1e-13, hermitian=False, **kwargs) → tuple[Sequence[float], Sequence[Vector]][source]#

Search for solution of the linear equation f(x) = b, where x is estimated vector and f(x) is matrix-vector operation. Implementation based on pseudoinverse of Krylov expansion [1].

Ref.[1] https://www.math.iit.edu/~fass/577_ch4_app.pdf

Parameters:

f (function) – define an action of a ‘square matrix’ on the ‘vector’ v0. f(v0) should preserve the signature of v0.
b (Tensor) – free term for the linear equation.
v0 (Tensor) – Initial guess span the Krylov space.
ncv (int) – Dimension of the employed Krylov space. The default is 10.
tol (float) – Stopping criterion for an expansion of the Krylov subspace. The default is 1e-13. TODO Not implemented yet.
pinv_tol (float) – Cutoff for pseudoinverse. Sets lower bound on inverted Schmidt values. The default is 1e-13.
hermitian (bool) – Assume that f is a Hermitian operator, in which case Lanczos iterations are used. Otherwise Arnoldi iterations are used to span the Krylov space.

Results#

vf: Tensor
Approximation of v in f(v) = b problem.

res: float
norm of the residual vector r = norm(f(vf) - b).

Other libraries#

With NumPy backend, it is possible to link to algorithms in sparse.sparse.linalg, employing yastn.Tensor.to_dict() and yastn.Tensor.from_dict(), combined with yastn.split_data_and_meta() and yastn.combine_data_and_meta(). See, an example.