"""
System solvers in the TT format, based on the alternating minimal energy (AMEn) method :cite:p:`dolgov2014alternating`.
"""
import torch as tn
import numpy as np
import torchtt
import datetime
from torchtt._decomposition import QR, SVD, lr_orthogonal, rl_orthogonal, rank_chop
from torchtt._iterative_solvers import BiCGSTAB_reset, gmres_restart
import opt_einsum as oe
from .errors import *
import torch.nn.functional as tnf
try:
import torchttcpp
_flag_use_cpp = True
except:
import warnings
warnings.warn(
"\x1B[33m\nC++ implementation not available. Using pure Python.\n\033[0m")
_flag_use_cpp = False
[docs]
def cpp_enabled():
"""
Is the C++ backend enabled?
Returns:
bool: the flag
"""
return _flag_use_cpp
def _local_product(Phi_right, Phi_left, coreA, core, shape, bandA=-1):
"""
Compute local matvec product
Args:
Phi (torch.tensor): right tensor of shape r x R x r.
Psi (torch.tensor): left tensor of shape lp x Rp x lp.
coreA (torch.tensor): current core of A, shape is rp x N x N x r.
x (torch.tensor): the current core of x, shape is rp x N x r.
shape (torch.Size): the shape of x.
bandA (int): if positive specifies number of diagonals in the matrix. 0 means diagonal structure, 1 means tridiagonal, ...
Returns:
torch.tensor: the reuslt.
"""
if bandA < 0:
w = oe.contract('lsr,smnS,LSR,rnR->lmL',
Phi_left, coreA, Phi_right, core)
else:
w = 0
for i in range(-bandA, bandA+1):
tmp = tn.diagonal(coreA, i, 1, 2)
tmp = tnf.pad(tmp, ((i) if i > 0 else 0,
abs(i) if i < 0 else 0, 0, 0, 0, 0))
tmp = oe.contract('lsr,sSm,LSR,rmR->lmL',
Phi_left, tmp, Phi_right, core)
if i < 0:
tmp = tnf.pad(tmp[:, :i, :], (0, 0, -i, 0, 0, 0))
else:
tmp = tnf.pad(tmp[:, i:, :], (0, 0, 0, i, 0, 0))
w += tmp
return w
class _LinearOp():
def __init__(self, Phi_left, Phi_right, coreA, shape, prec, band_diagonal=-1):
self.Phi_left = Phi_left
self.Phi_right = Phi_right
self.shape = shape
self.prec = prec
self.band_diagonal = band_diagonal
if band_diagonal >= 0:
self.bands = []
for i in range(-band_diagonal, band_diagonal+1):
tmp = tn.diagonal(coreA, i, 1, 2)
tmp = tnf.pad(tmp, ((i) if i > 0 else 0, abs(i) if i < 0 else 0, 0, 0, 0, 0))
self.bands.append(tmp.clone())
else:
self.coreA = coreA
if prec == 'c':
Jl = tn.einsum('sd,smnS->dmnS',
tn.diagonal(Phi_left, 0, 0, 2), coreA)
Jr = tn.diagonal(Phi_right, 0, 0, 2)
J = tn.einsum('dmnS,SD->dDmn', Jl, Jr)
self.J = tn.linalg.inv(J)
if shape[0]*shape[1]*shape[2] > 1e5:
self.contraction = oe.contract_expression(
'lsr,smnS,LSR,raR,rRna->lmL', Phi_left.shape, coreA.shape, Phi_right.shape, shape, self.J.shape)
else:
self.contraction = None
elif prec == 'r':
Jl = tn.einsum('sd,smnS->dmnS',
tn.diagonal(Phi_left, 0, 0, 2), coreA)
J = tn.einsum('dmnS,LSR->dmLnR', Jl, Phi_right)
sh = J.shape
J = tn.reshape(
J, [-1, J.shape[1]*J.shape[2], J.shape[3]*J.shape[4]])
self.J = tn.reshape(tn.linalg.inv(J), sh)
if shape[0]*shape[1]*shape[2] > 2*1e4:
self.contraction = oe.contract_expression(
'lsr,smnS,LSR,rab,rnRab->lmL', Phi_left.shape, coreA.shape, Phi_right.shape, shape, self.J.shape)
else:
self.contraction = None
else:
pass
def apply_prec(self, x):
if self.prec == 'c':
# no improvement using opt_einsum
y = tn.einsum('rnR,rRmn->rmR', x, self.J)
return y
elif self.prec == 'r':
y = tn.einsum('rnR,rmLnR->rmL', x, self.J)
return y
def matvec(self, x, apply_prec=True):
if self.prec == None or not apply_prec:
x = tn.reshape(x, self.shape)
if self.band_diagonal >= 0:
wtmp = tn.tensordot(x, self.Phi_left, ([0], [2]))
w = 0
for i in range(-self.band_diagonal, self.band_diagonal+1):
tmp = tn.einsum('nRls,sSn->RlnS', wtmp, self.bands[i+self.band_diagonal])
if i < 0:
tmp = tnf.pad(tmp[:, :, :i, :], (0, 0, -i, 0, 0, 0, 0, 0))
else:
tmp = tnf.pad(tmp[:, :, i:, :], (0, 0, 0, i, 0, 0, 0, 0))
w += tmp
w = tn.tensordot(w, self.Phi_right,
([0, 3], [2, 1])) # RlmS,LSR->lmL
else:
# shape rnR,lsr->nRls
w = tn.tensordot(x, self.Phi_left, ([0], [2]))
# nRls,smnS->RlmS
w = tn.tensordot(w, self.coreA, ([0, 3], [2, 0]))
w = tn.tensordot(w, self.Phi_right,
([0, 3], [2, 1])) # RlmS,LSR->lmL
elif self.prec == 'c' or self.prec == 'r':
x = tn.reshape(x, self.shape)
if not self.contraction is None:
w = self.contraction(
self.Phi_left, self.coreA, self.Phi_right, x, self.J)
else:
x = self.apply_prec(x)
# shape rnR,lsr->nRls
w = tn.tensordot(x, self.Phi_left, ([0], [2]))
# nRls,smnS->RlmS
w = tn.tensordot(w, self.coreA, ([0, 3], [2, 0]))
w = tn.tensordot(w, self.Phi_right,
([0, 3], [2, 1])) # RlmS,LSR->lmL
else:
raise Exception('Preconditioner '+str(self.prec)+' not defined.')
return tn.reshape(w, [-1, 1])
[docs]
def amen_solve(A, b, nswp=22, x0=None, eps=1e-10, rmax=32768, max_full=256, kickrank=4, kick2=0, trunc_norm='res', local_solver=1, local_iterations=40, resets=2, verbose=False, preconditioner=None, use_cpp=True, band_diagonal=-1, use_single_precision=False):
"""
Solve a multilinear system :math:`\\mathsf{Ax} = \\mathsf{b}` in the Tensor Train format.
This method implements the alternating minimal energy (AMEn) algorithm from `Sergey V Dolgov, Dmitry V Savostyanov, Alternating minimal energy methods for linear systems in higher dimensions <https://epubs.siam.org/doi/abs/10.1137/140953289>`_.
Example:
.. code-block:: python
import torchtt
A = torchtt.random([(4,4),(5,5),(6,6)],[1,2,3,1]) # create random matrix
x = torchtt.random([4,5,6],[1,2,3,1]) # invent a random solution
b = A @ x # compute the rhs
xx = torchtt.solvers.amen_solve(A,b) # solve
print((xx-x).norm()/x.norm()) # error
Args:
A (torchtt.TT): the system matrix in TT.
b (torchtt.TT): the right hand side in TT.
nswp (int, optional): number of sweeps. Defaults to 22.
x0 (torchtt.TT, optional): initial guess. If None is provided the initial guess is a ones tensor. Defaults to None.
eps (float, optional): relative residual. Defaults to 1e-10.
rmax (int | list[int], optional): maximum rank, or one maximum per rank index. Defaults to 32768.
max_full (int, optional): local systems strictly smaller than this are solved
directly, larger ones with the iterative local solver. Defaults to 256.
kickrank (int, optional): rank enrichment. Defaults to 4.
kick2 (int, optional): number of random vectors added to the rank enrichment, in addition to the ``kickrank`` vectors computed from the residual. Defaults to 0.
trunc_norm (str, optional): truncation of the local solution. ``'res'`` keeps the smallest rank whose local residual stays below the tolerance, ``'fro'`` truncates the singular values in the Frobenius norm. Defaults to 'res'.
local_solver (int, optional): choose local iterative solver: 1 for GMRES (generalized minimal residual) and 2 for BiCGSTAB (biconjugate gradient stabilized). Defaults to 1.
local_iterations (int, optional): number of iterations of the local solver: GMRES iterations between two restarts, or BiCGSTAB iterations. Defaults to 40.
resets (int, optional): number of GMRES restarts. Defaults to 2.
verbose (bool, optional): choose whether to display or not additional information during the runtime. Defaults to False.
preconditioner (string, optional): Choose the preconditioner for the local system. Possible values are None, 'c' (block Jacobi with one block per pair of rank indices) and 'r' (block Jacobi with one block per left rank index). No preconditioner is used if None is provided. Defaults to None.
use_cpp (bool, optional): use the C++ implementation of AMEn if available. It has the same accuracy and is 3-7x faster on CPU, most for small TT cores. It supports only real tensors, ``local_solver=1``, ``trunc_norm='res'``, ``band_diagonal=-1`` and an integer ``rmax``; other calls run the Python implementation. Defaults to True.
band_diagonal (int, optional): bandwidth of the TT cores of the matrix if they are band diagonal, -1 for dense cores. Defaults to -1.
use_single_precision (bool, optional): solve the local systems with the iterative solver in single precision. The Python implementation also computes the local residuals in single precision, the C++ implementation computes them in the precision of the input. Defaults to False.
Raises:
InvalidArguments: A and b must be TT instances.
InvalidArguments: Invalid preconditioner.
InvalidArguments: Invalid trunc_norm.
InvalidArguments: Solver not implemented.
IncompatibleTypes: A must be TT-matrix and b must be vector.
ShapeMismatch: A is not quadratic.
ShapeMismatch: Dimension mismatch.
Returns:
torchtt.TT: the approximation of the solution in TT format.
"""
# perform checks of the input data
if not (isinstance(A, torchtt.TT) and isinstance(b, torchtt.TT)):
raise InvalidArguments('A and b must be TT instances.')
if not (A.is_ttm and not b.is_ttm):
raise IncompatibleTypes('A must be TT-matrix and b must be vector.')
if A.M != A.N:
raise ShapeMismatch('A is not quadratic.')
if A.N != b.N:
raise ShapeMismatch('Dimension mismatch.')
if trunc_norm not in ['res', 'fro']:
raise InvalidArguments("Invalid trunc_norm, it must be 'res' or 'fro'.")
if local_solver not in [1, 2]:
raise InvalidArguments('Solver not implemented.')
# the C++ implementation has none of the other options and supports only real tensors
cpp_supported = local_solver == 1 and trunc_norm == 'res' and band_diagonal < 0 and isinstance(rmax, (int, np.integer)) and \
not any(c.is_complex() for c in A.cores + b.cores + ([] if x0 is None else x0.cores))
if use_cpp and _flag_use_cpp and cpp_supported:
if x0 == None:
x_cores = []
x_R = [1]*(1+len(A.N))
else:
x_cores = x0.cores
x_R = x0.R
if preconditioner == None:
prec = 0
elif preconditioner == 'c':
prec = 1
elif preconditioner == 'r':
prec = 2
else:
raise InvalidArguments("Invalid preconditioner.")
cores = torchttcpp.amen_solve(A.cores, b.cores, x_cores, b.N, A.R, b.R, x_R, nswp,
eps, rmax, max_full, kickrank, kick2, local_iterations, resets, verbose, prec, use_single_precision)
return torchtt.TT(list(cores))
else:
return _amen_solve_python(A, b, nswp, x0, eps, rmax, max_full, kickrank, kick2, trunc_norm, local_solver, local_iterations, resets, verbose, preconditioner, use_single_precision, band_diagonal)
def _amen_solve_python(A, b, nswp=22, x0=None, eps=1e-10, rmax=1024, max_full=256, kickrank=4, kick2=0, trunc_norm='res', local_solver=1, local_iterations=40, resets=2, verbose=False, preconditioner=None, use_single_precision=False, band_diagonal=-1):
if verbose:
time_total = datetime.datetime.now()
dtype = A.cores[0].dtype
device = A.cores[0].device
rank_search = 1 # binary rank search
damp = 2
if x0 == None:
x = torchtt.ones(b.N, dtype=dtype, device=device)
else:
x = x0
rA = A.R
N = b.N
d = len(N)
x_cores = x.cores.copy()
rx = x.R.copy()
# check if rmax is a list
if isinstance(rmax, int):
rmax = [1] + (d-1) * [rmax] + [1]
# z cores
rz = [1]+(d-1)*[kickrank+kick2]+[1]
z_tt = torchtt.random(N, rz, dtype, device=device)
z_cores = z_tt.cores
z_cores, rz = rl_orthogonal(z_cores, rz, False)
norms = np.zeros(d)
Phiz = [tn.ones((1, 1, 1), dtype=dtype, device=device)] + [None] * (d-1) + \
[tn.ones((1, 1, 1), dtype=dtype, device=device)
] # size is rzk x Rk x rxk
Phiz_b = [tn.ones((1, 1), dtype=dtype, device=device)] + [None] * (d-1) + \
[tn.ones((1, 1), dtype=dtype, device=device)] # size is rzk x rzbk
Phis = [tn.ones((1, 1, 1), dtype=dtype, device=device)] + [None] * (d-1) + \
[tn.ones((1, 1, 1), dtype=dtype, device=device)
] # size is rk x Rk x rk
Phis_b = [tn.ones((1, 1), dtype=dtype, device=device)] + [None] * (d-1) + \
[tn.ones((1, 1), dtype=dtype, device=device)] # size is rk x rbk
last = False
normA = np.ones((d-1))
normb = np.ones((d-1))
normx = np.ones((d-1))
nrmsc = 1.0
if verbose:
print('Starting AMEn solve with:\n\tepsilon: %g\n\tsweeps: %d\n\tlocal iterations: %d\n\tresets: %d\n\tpreconditioner: %s' % (
eps, nswp, local_iterations, resets, str(preconditioner)))
print()
for swp in range(nswp):
# right to left orthogonalization
if verbose:
print()
print('Starting sweep %d %s...' %
(swp+1, "(last one) " if last else ""))
tme_sweep = datetime.datetime.now()
tme = datetime.datetime.now()
for k in range(d-1, 0, -1):
# update the z part (ALS) update
if not last:
if swp > 0:
# shape rzp x N x rz
czA = _local_product(
Phiz[k+1], Phiz[k], A.cores[k], x_cores[k], x_cores[k].shape, band_diagonal)
# shape is rzp x N x rz
czy = tn.einsum('br,bnB,BR->rnR',
Phiz_b[k], b.cores[k], Phiz_b[k+1])
cz_new = czy*nrmsc - czA
_, _, vz = SVD(tn.reshape(cz_new, [cz_new.shape[0], -1]))
# truncate to kickrank
cz_new = vz[:min(kickrank, vz.shape[0]), :].t()
if k < d-1: # extend cz_new with random elements
cz_new = tn.cat(
(cz_new, tn.randn((cz_new.shape[0], kick2), dtype=dtype, device=device)), 1)
else:
cz_new = tn.reshape(z_cores[k], [rz[k], -1]).t()
qz, _ = QR(cz_new)
rz[k] = qz.shape[1]
z_cores[k] = tn.reshape(qz.t(), [rz[k], N[k], rz[k+1]])
# norm correction ?
if swp > 0:
nrmsc = nrmsc * normA[k-1] * normx[k-1] / normb[k-1]
core = tn.reshape(x_cores[k], [rx[k], N[k]*rx[k+1]]).t()
Qmat, Rmat = QR(core)
core_prev = tn.einsum('ijk,km->ijm', x_cores[k-1], Rmat.T)
rx[k] = Qmat.shape[1]
current_norm = tn.linalg.norm(core_prev)
if current_norm > 0:
core_prev = core_prev / current_norm
else:
current_norm = 1.0
normx[k-1] = normx[k-1]*current_norm
x_cores[k] = tn.reshape(Qmat.t(), [rx[k], N[k], rx[k+1]])
x_cores[k-1] = core_prev[:]
# update phis (einsum)
Phis[k] = _compute_phi_bck_A(
Phis[k+1], x_cores[k], A.cores[k], x_cores[k])
Phis_b[k] = _compute_phi_bck_rhs(
Phis_b[k+1], b.cores[k], x_cores[k])
# ... and norms
norm = tn.linalg.norm(Phis[k])
norm = norm if norm > 0 else 1.0
normA[k-1] = norm
Phis[k] = Phis[k] / norm
norm = tn.linalg.norm(Phis_b[k])
norm = norm if norm > 0 else 1.0
normb[k-1] = norm
Phis_b[k] = Phis_b[k]/norm
# norm correction
nrmsc = nrmsc * normb[k-1] / (normA[k-1] * normx[k-1])
# compute phis_z
if not last:
Phiz[k] = _compute_phi_bck_A(
Phiz[k+1], z_cores[k], A.cores[k], x_cores[k]) / normA[k-1]
Phiz_b[k] = _compute_phi_bck_rhs(
Phiz_b[k+1], b.cores[k], z_cores[k]) / normb[k-1]
# start loop
max_res = 0
max_dx = 0
for k in range(d):
if verbose:
print('\tCore', k)
previous_solution = tn.reshape(x_cores[k], [-1, 1])
# assemble rhs
rhs = tn.einsum('br,bmB,BR->rmR',
Phis_b[k], b.cores[k] * nrmsc, Phis_b[k+1])
rhs = tn.reshape(rhs, [-1, 1])
norm_rhs = tn.linalg.norm(rhs)
zero_rhs = norm_rhs == 0
norm_rhs = norm_rhs if norm_rhs > 0 else 1.0
# residuals
real_tol = (eps/np.sqrt(d))/damp
# solve the local system
use_full = rx[k]*N[k]*rx[k+1] < max_full
if use_full:
# solve the full system
if verbose:
print('\t\tChoosing direct solver (local size %d)....' %
(rx[k]*N[k]*rx[k+1]))
# shape is Rp x N x N x r x r
Bp = tn.einsum('smnS,LSR->smnRL', A.cores[k], Phis[k+1])
B = tn.einsum('lsr,smnRL->lmLrnR', Phis[k], Bp)
B = tn.reshape(B, [rx[k]*N[k]*rx[k+1], rx[k]*N[k]*rx[k+1]])
solution_now = tn.linalg.solve(B, rhs)
res_old = tn.linalg.norm(B@previous_solution-rhs)/norm_rhs
res_new = tn.linalg.norm(B@solution_now-rhs)/norm_rhs
else:
# iterative solver
if verbose:
print('\t\tChoosing iterative solver %s (local size %d)....' % (
'GMRES' if local_solver == 1 else 'BiCGSTAB_reset', rx[k]*N[k]*rx[k+1]))
time_local = datetime.datetime.now()
shape_now = [rx[k], N[k], rx[k+1]]
if use_single_precision:
Op = _LinearOp(Phis[k].to(tn.float32), Phis[k+1].to(tn.float32),
A.cores[k].to(tn.float32), shape_now, preconditioner, band_diagonal)
eps_local = real_tol * norm_rhs
drhs = Op.matvec(previous_solution.to(tn.float32), False)
drhs = rhs.to(tn.float32)-drhs
norm_drhs = tn.linalg.norm(drhs)
eps_local = eps_local / (norm_drhs if norm_drhs > 0 else 1.0)
if zero_rhs or norm_drhs == 0:
solution_now, flag, nit = tn.zeros_like(drhs), True, 0
elif local_solver == 1:
solution_now, flag, nit = gmres_restart(Op, drhs, previous_solution.to(
tn.float32)*0, rhs.shape[0], local_iterations, eps_local, resets)
elif local_solver == 2:
solution_now, flag, nit, _ = BiCGSTAB_reset(
Op, drhs, previous_solution.to(tn.float32)*0, eps_local, local_iterations)
else:
raise InvalidArguments('Solver not implemented.')
if preconditioner != None:
solution_now = Op.apply_prec(
tn.reshape(solution_now, shape_now))
solution_now = tn.reshape(solution_now, [-1, 1])
solution_now = tn.zeros_like(previous_solution) if zero_rhs else previous_solution + solution_now.to(dtype)
res_old = tn.linalg.norm(Op.matvec(previous_solution.to(
tn.float32), False).to(dtype)-rhs)/norm_rhs
res_new = tn.linalg.norm(Op.matvec(solution_now.to(
tn.float32), False).to(dtype)-rhs)/norm_rhs
else:
Op = _LinearOp(Phis[k], Phis[k+1],
A.cores[k], shape_now, preconditioner, band_diagonal)
eps_local = real_tol * norm_rhs
drhs = Op.matvec(previous_solution, False)
drhs = rhs-drhs
norm_drhs = tn.linalg.norm(drhs)
eps_local = eps_local / (norm_drhs if norm_drhs > 0 else 1.0)
if zero_rhs or norm_drhs == 0:
solution_now, flag, nit = tn.zeros_like(drhs), True, 0
elif local_solver == 1:
solution_now, flag, nit = gmres_restart(
Op, drhs, previous_solution*0, rhs.shape[0], local_iterations, eps_local, resets)
elif local_solver == 2:
solution_now, flag, nit, _ = BiCGSTAB_reset(
Op, drhs, previous_solution*0, eps_local, local_iterations)
else:
raise InvalidArguments('Solver not implemented.')
if preconditioner != None:
solution_now = Op.apply_prec(
tn.reshape(solution_now, shape_now))
solution_now = tn.reshape(solution_now, [-1, 1])
solution_now = tn.zeros_like(previous_solution) if zero_rhs else previous_solution + solution_now
res_old = tn.linalg.norm(
Op.matvec(previous_solution, False)-rhs)/norm_rhs
res_new = tn.linalg.norm(
Op.matvec(solution_now, False)-rhs)/norm_rhs
if verbose:
print('\t\tFinished with flag %d after %d iterations with relres %g (from %g)' % (
flag, nit, res_new, real_tol * norm_rhs))
time_local = datetime.datetime.now() - time_local
print('\t\tTime needed ', time_local)
# residual damp check
if res_old/res_new < damp and res_new > real_tol:
if verbose:
print('WARNING: residual increases. res_old %g, res_new %g, real_tol %g' % (
res_old, res_new, real_tol)) # warning (from tt toolbox)
# compute residual and step size
norm_solution = tn.linalg.norm(solution_now)
dx = tn.linalg.norm(solution_now-previous_solution) / (norm_solution if norm_solution > 0 else 1.0)
if verbose:
print('\t\tdx = %g, res_now = %g, res_old = %g' %
(dx, res_new, res_old))
max_dx = max(dx, max_dx)
max_res = max(max_res, res_old)
solution_now = tn.reshape(solution_now, [rx[k]*N[k], rx[k+1]])
# truncation
if k < d-1:
u, s, v = SVD(solution_now)
if trunc_norm == 'fro':
s_np = s.detach().cpu().numpy()
r = min([rank_chop(s_np, real_tol*np.linalg.norm(s_np)), tn.numel(s), rmax[k+1]])
else:
# search for a rank such that offeres small enough residuum
# TODO: binary search?
# A scan that never exceeds the budget means rank 1 already
# suffices; incrementing the exhausted loop variable instead
# floored the rank at 2 and left a spurious direction behind.
r_trunc = 1
for r in range(u.shape[1]-1, 0, -1):
# solution has the same size
solution = u[:, :r] @ tn.diag(s[:r]) @ v[:r, :]
if use_full:
res = tn.linalg.norm(
B@tn.reshape(solution, [-1, 1])-rhs)/norm_rhs
else:
res = tn.linalg.norm(Op.matvec(solution.to(
tn.float32 if use_single_precision else dtype), False).to(dtype)-rhs)/norm_rhs
# On the final sweep the residual enrichment is disabled, so any
# accuracy given away here can no longer be recovered. Budget the
# truncation against what the local solve just achieved instead of
# against the global tolerance. This does less rank reduction on
# that sweep, so the returned ranks may be higher than before;
# round the result if compression matters more than the accuracy.
if res > (res_new*damp if last else max(real_tol*damp, res_new)):
r_trunc = r + 1
break
r = min([r_trunc, tn.numel(s), rmax[k+1]])
else:
u, v = QR(solution_now)
r = u.shape[1]
s = tn.ones(r, dtype=dtype, device=device)
u = u[:, :r]
v = tn.diag(s[:r]) @ v[:r, :]
v = v.t()
if not last:
czA = _local_product(Phiz[k+1], Phiz[k], A.cores[k], tn.reshape(
u@v.t(), [rx[k], N[k], rx[k+1]]), [rx[k], N[k], rx[k+1]], band_diagonal) # shape rzp x N x rz
# shape is rzp x N x rz
czy = tn.einsum('br,bnB,BR->rnR',
Phiz_b[k], b.cores[k]*nrmsc, Phiz_b[k+1])
cz_new = czy - czA
uz, _, _ = SVD(tn.reshape(cz_new, [rz[k]*N[k], rz[k+1]]))
# truncate to kickrank
cz_new = uz[:, :min(kickrank, uz.shape[1])]
if k < d-1: # extend cz_new with random elements
cz_new = tn.cat(
(cz_new, tn.randn((cz_new.shape[0], kick2), dtype=dtype, device=device)), 1)
qz, _ = QR(cz_new)
rz[k+1] = qz.shape[1]
z_cores[k] = tn.reshape(qz, [rz[k], N[k], rz[k+1]])
if k < d-1:
if not last:
left_res = _local_product(Phiz[k+1], Phis[k], A.cores[k], tn.reshape(
u@v.t(), [rx[k], N[k], rx[k+1]]), [rx[k], N[k], rx[k+1]], band_diagonal)
left_b = tn.einsum(
'br,bmB,BR->rmR', Phis_b[k], b.cores[k]*nrmsc, Phiz_b[k+1])
uk = left_b - left_res # rx_k x N_k x rz_k+1
u, Rmat = QR(
tn.cat((u, tn.reshape(uk, [u.shape[0], -1])), 1))
r_add = uk.shape[2]
v = tn.cat(
(v, tn.zeros([rx[k+1], r_add], dtype=dtype, device=device)), 1)
v = v @ Rmat.t()
r = u.shape[1]
v = tn.einsum('ji,jkl->ikl', v, x_cores[k+1])
# remove norm correction
nrmsc = nrmsc * normA[k] * normx[k] / normb[k]
norm_now = tn.linalg.norm(v)
if norm_now > 0:
v = v / norm_now
else:
norm_now = 1.0
normx[k] = normx[k] * norm_now
x_cores[k] = tn.reshape(u, [rx[k], N[k], r])
x_cores[k+1] = tn.reshape(v, [r, N[k+1], rx[k+2]])
rx[k+1] = r
# next phis with norm correction
Phis[k+1] = _compute_phi_fwd_A(Phis[k],
x_cores[k], A.cores[k], x_cores[k])
Phis_b[k +
1] = _compute_phi_fwd_rhs(Phis_b[k], b.cores[k], x_cores[k])
# ... and norms
norm = tn.linalg.norm(Phis[k+1])
norm = norm if norm > 0 else 1.0
normA[k] = norm
Phis[k+1] = Phis[k+1] / norm
norm = tn.linalg.norm(Phis_b[k+1])
norm = norm if norm > 0 else 1.0
normb[k] = norm
Phis_b[k+1] = Phis_b[k+1] / norm
# norm correction
nrmsc = nrmsc * normb[k] / (normA[k] * normx[k])
# next phiz
if not last:
Phiz[k+1] = _compute_phi_fwd_A(Phiz[k], z_cores[k],
A.cores[k], x_cores[k]) / normA[k]
Phiz_b[k+1] = _compute_phi_fwd_rhs(
Phiz_b[k], b.cores[k], z_cores[k]) / normb[k]
else:
x_cores[k] = tn.reshape(
u@tn.diag(s[:r]) @ v[:r, :].t(), [rx[k], N[k], rx[k+1]])
if verbose:
print('Solution rank is', rx)
print('Maxres ', max_res)
tme_sweep = datetime.datetime.now()-tme_sweep
print('Time ', tme_sweep)
if last:
break
if max_res < eps:
last = True
if verbose:
time_total = datetime.datetime.now() - time_total
print()
print('Finished after', swp+1, ' sweeps and ', time_total)
print()
normx = np.exp(np.sum(np.log(normx))/d)
for k in range(d):
x_cores[k] = x_cores[k] * normx
x = torchtt.TT(x_cores)
return x
def _compute_phi_bck_A(Phi_now, core_left, core_A, core_right):
"""
Compute the phi backwards for the form dot(left,A @ right)
Args:
Phi_now (torch.tensor): The current phi. Has shape r1_k+1 x R_k+1 x r2_k+1
core_left (torch.tensor): the core on the left, it is conjugated. Has shape r1_k x N_k x r1_k+1
core_A (torch.tensor): the core of the matrix. Has shape R_k x N_k x N_k x R_k
core_right (torch.tensor): the core to the right. Has shape r2_k x N_k x r2_k+1
Returns:
torch.tensor: The following phi (backward). Has shape r1_k x R_k x r2_k
"""
Phi = oe.contract('LSR,lML,sMNS,rNR->lsr', Phi_now,
tn.conj(core_left), core_A, core_right)
return Phi
def _compute_phi_fwd_A(Phi_now, core_left, core_A, core_right):
"""
Compute the phi forward for the form dot(left,A @ right)
Args:
Phi_now (torch.tensor): The current phi. Has shape r1_k x R_k x r2_k
core_left (torch.tensor): the core on the left, it is conjugated. Has shape r1_k x N_k x r1_k+1
core_A (torch.tensor): the core of the matrix. Has shape R_k x N_k x N_k x R_k
core_right (torch.tensor): the core to the right. Has shape r2_k x N_k x r2_k+1
Returns:
torch.tensor: The following phi (backward). Has shape r1_k+1 x R_k+1 x r2_k+1
"""
Phi_next = oe.contract('lsr,lML,sMNS,rNR->LSR',
Phi_now, tn.conj(core_left), core_A, core_right)
return Phi_next
def _compute_phi_bck_rhs(Phi_now, core_b, core):
"""
Args:
Phi_now (torch.tensor): The current phi. Has shape rb_k+1 x r_k+1
core_b (torch.tensor): The current core of the rhs. Has shape rb_k x N_k x rb_k+1
core (torch.tensor): The current core, it is conjugated. Has shape r_k x N_k x r_k+1
Returns:
torch.tensor: The backward phi corresponding to the rhs. Has shape rb_k x r_k
"""
Phi = oe.contract('BR,bnB,rnR->br', Phi_now, core_b, tn.conj(core))
return Phi
def _compute_phi_fwd_rhs(Phi_now, core_rhs, core):
"""
Args:
Phi_now (torch.tensor): The current phi. Has shape rb_k x r_k
core_b (torch.tensor): The current core of the rhs. Has shape rb_k x N_k+1 x rb_k+1
core (torch.tensor): The current core, it is conjugated. Has shape r_k x N_k x r_k+1
Returns:
torch.tensor: The forward computer phi for the rhs. Has shape rb_k+1 x r_k+1
"""
Phi_next = oe.contract('br,bnB,rnR->BR', Phi_now, core_rhs, tn.conj(core))
return Phi_next