Source code for morphogen.homogenization.solvers

"""Linear solvers for the symmetric positive definite systems of the FE problems.

* ``direct``: sparse LU factorization (SuperLU, from SciPy), reused for every right-hand
  side. Exact and fast for small systems; its memory grows quickly in 3D.
* ``amg``: conjugate gradient preconditioned by smoothed-aggregation algebraic multigrid
  (:mod:`morphogen.homogenization.amg`), with the rigid-body modes (or constants) as
  near-null space. For 10-node tetrahedra, the preconditioner has two levels: a
  Gauss-Seidel sweep on the quadratic system, and an AMG cycle on the linear system of
  the corner nodes (Galerkin projection). The hierarchy is reused for every right-hand
  side.
* ``cg``: conjugate gradient with a Jacobi preconditioner (slow on large or
  high-contrast problems; for checks).
* ``auto``: ``direct`` up to :data:`DIRECT_LIMIT` unknowns, ``amg`` above.

The tangents of the nonlinear problems whose behaviours have nonsymmetric consistent
tangents (``symmetric=False``: crystal and porous plasticity, the Armstrong-Frederick
hardening, learned laws that are not potentials, MFront behaviours without a symmetric
tangent) are solved by sparse LU (``direct``) or by GMRES with deflated restarts
(:func:`gmres`) with the preconditioner of their symmetric part (``amg``, ``cg``); along
the loading paths of the voxels GMRES recycles its space from a solve to the next once
one restarts (GCRO-DR, :class:`Recycling`) and stops where it stagnates
(:data:`GMRES_STAGNATION`).
"""

from __future__ import annotations

import logging
import math
import time
from dataclasses import dataclass

import numpy as np
import scipy.linalg as sla
import scipy.sparse as sp
import scipy.sparse.linalg as spla
from numba import njit, prange

from morphogen.homogenization.amg import NodeBlocks, SmoothedAggregation, Smoother, product
from morphogen.settings import without_blas_threads
from morphogen.stopping import checkpoint

log = logging.getLogger("morphogen")

DIRECT_LIMIT = 6_000
#: A multigrid preconditioner kept from a step of a loading path to the next is built again
#: when the iterations that a solve takes for a decade of its residual have grown by this
#: factor since it was built (:meth:`LinearSolver.worn`): building it costs as much as
#: the iterations that a third more would add to a step
WORN = 1.3
#: The dimension of the Krylov spaces of :func:`gmres` before it restarts (the vectors of
#: its basis kept in memory)
GMRES_RESTART = 50
#: The approximate eigenvectors that :func:`gmres` keeps at its restarts: the harmonic Ritz
#: vectors of the harmonic Ritz values of least modulus (deflated restarting; 0: the plain
#: restarts)
GMRES_DEFLATE = 20
#: The cycles over which the residual of a solve of :func:`gmres` along a loading path must
#: at least halve (``stagnation``): 240 iterations of restarted cycles. Measured on the
#: softening composites of 16^3 voxels (Rousselier and GTN at high triaxialities), it stops
#: all the solves that would end at their ``maxiter`` above their tolerance (35 of them,
#: after about 300 iterations instead of 1,320) and none of the 95 that converge after
#: restarts (up to 528 iterations, after slow cycles); six cycles would stop three of
#: these, three cycles eight
GMRES_STAGNATION = 8
METHODS = ("auto", "direct", "amg", "cg")
#: Solvers of finite element problems: morphoGen's linear solvers, or FEniCSx
#: (:mod:`morphogen.homogenization.fenicsx`).
SOLVERS = (*METHODS, "fenicsx")
#: Right-hand sides smaller than this fraction of their scale (the norm they would have
#: without cancellation between elements) are round-off: the affine field solves the
#: problem (homogeneous medium, laminate loaded along its layers...).
NEGLIGIBLE = 1e-12


[docs] def dot(a: np.ndarray, b: np.ndarray) -> float: """Dot product of two vectors in a single thread. BLAS (``a @ b``) splits long vectors over its own threads, which compete with those of the compiled kernels and slow the solvers down several times — during the product and for a tenth of a second after it, while its idle threads wait for the next one (OpenBLAS); this sum is also the same for any number of threads.""" return float(np.einsum("i,i->", a, b))
[docs] def norm(a: np.ndarray) -> float: """Euclidean norm of a vector (see :func:`dot`).""" return math.sqrt(dot(a, a))
#: The sums of the products of two arrays of one or two dimensions _TIMES = {(1, 1): "i,i->", (2, 1): "ij,j->i", (1, 2): "i,ij->j", (2, 2): "ij,jk->ik"}
[docs] def times(a: np.ndarray, b: np.ndarray) -> np.ndarray: """``a @ b`` for arrays of one or two dimensions, in a single thread: the products of long arrays between two compiled kernels (see :func:`dot`).""" return np.einsum(_TIMES[a.ndim, b.ndim], a, b)
[docs] def choose_method(method: str, n: int) -> str: """Concrete solver for ``n`` unknowns (resolves ``auto``).""" if method not in METHODS: raise ValueError(f"solver: one of {METHODS}, got {method!r}") if method != "auto": return method return "direct" if n <= DIRECT_LIMIT else "amg"
[docs] @dataclass class SolveInfo: method: str n_dofs: int iterations: int residual: float setup_s: float solve_s: float
[docs] def to_dict(self) -> dict: return { "solver": self.method, "n_dofs": self.n_dofs, "iterations": self.iterations, "residual": self.residual, "setup_s": round(self.setup_s, 4), "solve_s": round(self.solve_s, 4), }
[docs] @without_blas_threads def conjugate_gradient(apply, precondition, rhs, tol, maxiter): """Preconditioned conjugate gradient from ``x = 0``. ``apply(v)`` and ``precondition(r)`` return new arrays. Stops when the residual is below ``tol`` times the norm of ``rhs``; returns (x, iterations, relative residual). A direction of negative curvature (an indefinite operator: the tangent of softening points) hands the system to :func:`minres`, from the current iterate or from zero, whichever leaves the smaller residual. Each iteration is a checkpoint of :mod:`morphogen.stopping`. """ x = np.zeros_like(rhs) norm_b = norm(rhs) if norm_b == 0.0: return x, 0, 0.0 r = rhs.copy() z = precondition(r) p = z.copy() rz = dot(r, z) res = 1.0 it = 0 for it in range(1, maxiter + 1): checkpoint() ap = apply(p) pap = dot(p, ap) if pap <= 0.0: norm_r = norm(r) if pap < 0.0 and norm_r > 0.0: if norm_r > norm_b: # an iterate worse than zero x[:] = 0.0 r = rhs.copy() norm_r = norm_b dx, more, rel = minres(apply, precondition, r, tol * norm_b / norm_r, maxiter - it) # fmt: skip return x + dx, it + more, rel * norm_r / norm_b break alpha = rz / pap x += alpha * p r -= alpha * ap res = norm(r) / norm_b if res <= tol: break z = precondition(r) rz_new = dot(r, z) if rz_new <= 0.0: # the residual is round-off the preconditioner cancels break p *= rz_new / rz p += z rz = rz_new return x, it, res
[docs] @without_blas_threads def minres(apply, precondition, rhs, tol, maxiter): """Preconditioned MINRES (Paige & Saunders 1975) from ``x = 0``, for a symmetric operator that may be indefinite (the tangent of softening points) and a symmetric positive definite preconditioner. Each cycle stops when the residual in the norm of the preconditioner falls below the target; the residual is then computed in the Euclidean norm, and another cycle starts from it while it is above ``tol`` times the norm of ``rhs``. Returns (x, iterations, relative residual), as :func:`conjugate_gradient`. """ x = np.zeros_like(rhs) norm_b = norm(rhs) if norm_b == 0.0: return x, 0, 0.0 r = rhs.copy() res = 1.0 total = 0 while total < maxiter: dx, its = _minres_cycle(apply, precondition, r, tol / res, maxiter - total) total += its x += dx r = rhs - apply(x) res = norm(r) / norm_b if res <= tol or its == 0: break return x, total, res
def _minres_cycle(apply, precondition, rhs, tol, maxiter): """One cycle of :func:`minres` from ``x = 0``: (x, iterations).""" x = np.zeros_like(rhs) r1 = rhs.copy() y = precondition(r1) beta1 = dot(r1, y) if not beta1 > 0.0: return x, 0 beta1 = math.sqrt(beta1) oldb, beta, dbar, epsln, phibar, cs, sn = 0.0, beta1, 0.0, 0.0, beta1, -1.0, 0.0 w = np.zeros_like(rhs) w2 = np.zeros_like(rhs) r2 = r1 it = 0 for it in range(1, maxiter + 1): checkpoint() v = y / beta y = apply(v) if it >= 2: y -= (beta / oldb) * r1 alfa = dot(v, y) y -= (alfa / beta) * r2 r1 = r2 r2 = y y = precondition(r2) oldb = beta beta = dot(r2, y) if beta < 0.0: # a preconditioner that is not positive definite break beta = math.sqrt(beta) # the previous rotation, then the next one oldeps = epsln delta = cs * dbar + sn * alfa gbar = sn * dbar - cs * alfa epsln = sn * beta dbar = -cs * beta gamma = max(math.hypot(gbar, beta), 1e-300) cs = gbar / gamma sn = beta / gamma phi = cs * phibar phibar = sn * phibar w1 = w2 w2 = w w = (v - oldeps * w1 - delta * w2) / gamma x += phi * w if abs(phibar) <= tol * beta1 or beta == 0.0: break return x, it #: The sums of the Gram-Schmidt passes of :func:`gmres` run by blocks of at least _BLOCK #: values, at most _MAX_BLOCKS of them: their number is set by the length of the vectors, #: so that the sums are the same for any number of threads, and whether one thread or #: several sweep them. Vectors of a single block (shorter than _PARALLEL) are swept by one #: thread (waking the threads would take longer; from two blocks on, the threads take a #: GMRES iteration on 24^3 voxels from 15.7 to 9.3 ms, 6.5 ms for the conjugate gradients) _BLOCK = 4096 _MAX_BLOCKS = 256 _PARALLEL = 2 * _BLOCK #: A Gram-Schmidt pass of :func:`gmres` that leaves less than this fraction of the norm of #: the vector is done again (Daniel, Gragg, Kaufman & Stewart 1976: twice is enough) _REORTHOGONALIZE = 1.0 / math.sqrt(2.0) @njit(cache=True) def _block_dots(basis, k, w, lo, hi, out): """``out[:k] = basis[:k, lo:hi] w[lo:hi]``, by four interleaved partial sums.""" for i in range(k): a0 = a1 = a2 = a3 = 0.0 t = lo while t + 4 <= hi: a0 += basis[i, t] * w[t] a1 += basis[i, t + 1] * w[t + 1] a2 += basis[i, t + 2] * w[t + 2] a3 += basis[i, t + 3] * w[t + 3] t += 4 while t < hi: a0 += basis[i, t] * w[t] t += 1 out[i] = (a0 + a1) + (a2 + a3) @njit(parallel=True, cache=True) def _parallel_dots(basis, k, w, partial): n, n_blocks = w.size, partial.shape[0] for b in prange(n_blocks): _block_dots(basis, k, w, b * n // n_blocks, (b + 1) * n // n_blocks, partial[b]) @njit(cache=True) def _serial_dots(basis, k, w, partial): n, n_blocks = w.size, partial.shape[0] for b in range(n_blocks): _block_dots(basis, k, w, b * n // n_blocks, (b + 1) * n // n_blocks, partial[b]) def _dots(basis, k: int, w, out) -> None: """``out[:k] = basis[:k] w``: the dot products of ``w`` with the first ``k`` vectors of ``basis`` (its rows), in one sweep of them.""" n = w.size partial = np.empty((min(max(n // _BLOCK, 1), _MAX_BLOCKS), k)) (_parallel_dots if n >= _PARALLEL else _serial_dots)(basis, k, w, partial) out[:k] = partial.sum(axis=0) @njit(cache=True) def _block_subtract(basis, k, coef, w, lo, hi): for i in range(k): c = coef[i] for t in range(lo, hi): w[t] -= c * basis[i, t] @njit(parallel=True, cache=True) def _parallel_subtract(basis, k, coef, w, n_blocks): n = w.size for b in prange(n_blocks): _block_subtract(basis, k, coef, w, b * n // n_blocks, (b + 1) * n // n_blocks) def _subtract(basis, k: int, coef, w) -> None: """``w -= basis[:k]^T coef[:k]``, in place (the vectors in the order of the basis).""" n = w.size if n >= _PARALLEL: _parallel_subtract(basis, k, coef, w, min(max(n // _BLOCK, 1), _MAX_BLOCKS)) else: _block_subtract(basis, k, coef, w, 0, n) #: The columns of the basis that :func:`_combine` turns at once _CHUNK = 256 @njit(cache=True) def _block_combine(basis, rows, p, lo, hi): """``basis[i, lo:hi] = sum_j p[j, i] basis[j, lo:hi]`` for the columns ``i`` of ``p`` and ``j < rows``, in place, by chunks of the columns of the basis.""" cols = p.shape[1] acc = np.empty((cols, _CHUNK)) for start in range(lo, hi, _CHUNK): width = min(_CHUNK, hi - start) acc[:, :width] = 0.0 for j in range(rows): for i in range(cols): c = p[j, i] for t in range(width): acc[i, t] += c * basis[j, start + t] for i in range(cols): for t in range(width): basis[i, start + t] = acc[i, t] @njit(parallel=True, cache=True) def _parallel_combine(basis, rows, p, n_blocks): n = basis.shape[1] for b in prange(n_blocks): _block_combine(basis, rows, p, b * n // n_blocks, (b + 1) * n // n_blocks) def _combine(basis, rows: int, p) -> None: """``basis[:c] = p^T basis[:rows]`` in place (``p``: rows x c): the vectors that a deflated restart of :func:`gmres` keeps, each sum in the order of the basis whatever the threads.""" n = basis.shape[1] p = np.ascontiguousarray(p, dtype=np.float64) if n >= _PARALLEL: _parallel_combine(basis, rows, p, min(max(n // _BLOCK, 1), _MAX_BLOCKS)) else: _block_combine(basis, rows, p, 0, n) def _deflation(h, c, y, m: int, k: int): """The start of the cycle that follows a full cycle of :func:`gmres` (``m`` iterations) in deflated restarting (Morgan 2002): ``h`` is the Arnoldi matrix of the cycle ((m + 1) x m, in its basis), ``c`` the coordinates of its first residual, ``y`` the solution of its least squares problem. The harmonic Ritz vectors of the ``k`` harmonic Ritz values of least modulus (the eigenvectors of ``H + h_{m+1,m}^2 H^-T e_m e_m^T``, ``H`` the square part of ``h``; a complex pair kept whole by the real and imaginary parts of its vectors) and the residual of the least squares problem, ``z = c - h y``, span the next start: their harmonic residuals are all parallel to ``z``, so that the Arnoldi relation holds on them. Returns their orthonormal basis ``P`` ((m + 1) x (k' + 1): the harmonic Ritz vectors, then ``z``), the Arnoldi matrix on it, ``P^T h P[:m, :k']``, a full block, and the coordinates ``P^T z`` of the residual; None when ``H`` is singular or the vectors are not finite or not independent of ``z`` (the cycle then restarts from the residual alone).""" z = c - h @ y[:m] hm = h[:m, :m] em = np.zeros(m) em[-1] = 1.0 try: a = hm.copy() a[:, -1] += h[m, m - 1] ** 2 * np.linalg.solve(hm.T, em) theta, g = np.linalg.eig(a) except np.linalg.LinAlgError: return None if not (np.all(np.isfinite(theta)) and np.all(np.isfinite(g))): return None vectors = [] for i in np.argsort(np.abs(theta), kind="stable"): if len(vectors) >= k: break if theta[i].imag > 0.0: # a pair: its conjugate gives the same two real vectors vectors += [g[:, i].real, g[:, i].imag] elif theta[i].imag == 0.0: vectors.append(g[:, i].real) q, tri = np.linalg.qr(np.column_stack(vectors)) diag = np.abs(np.diag(tri)) q = q[:, diag > 1e-12 * diag.max()] kept = q.shape[1] p = np.zeros((m + 1, kept + 1)) p[:m, :kept] = q perp = z.copy() for _ in range(2): perp -= p[:, :kept] @ (p[:, :kept].T @ perp) size = float(np.linalg.norm(perp)) if not size > 1e-12 * float(np.linalg.norm(z)): return None p[:, kept] = perp / size return p, p.T @ h @ p[:m, :kept], p.T @ z
[docs] @without_blas_threads def gmres(apply, precondition, rhs, tol, maxiter, restart: int = GMRES_RESTART, deflate: int = GMRES_DEFLATE, recycle: Recycling | None = None, stagnation: int = 0): # fmt: skip """GMRES (Saad & Schultz 1986) from ``x = 0``, preconditioned on the right, with deflated restarts (Morgan 2002): the solver of the tangent operators that are not symmetric (the full consistent tangents of the points), with the preconditioner of :func:`conjugate_gradient` (``apply(v)`` and ``precondition(r)`` return new arrays). Each cycle builds an orthonormal basis of the Krylov space of ``apply(precondition(.))`` by classical Gram-Schmidt (each pass sweeps the basis once for all its dot products, summed by blocks that do not depend on the threads), passed again where it cancels most of the vector (twice is enough: orthogonal to round-off), and minimizes the residual over it by the Givens rotations of its Hessenberg matrix. Preconditioned on the right, the residual minimized is that of the system, ``rhs - apply(x)``: the cycle stops when it falls below ``tol`` times the norm of ``rhs``, the test of the conjugate gradients. After ``restart`` iterations (the vectors kept) ``x`` is updated, and the next cycle starts from the harmonic Ritz vectors of the ``deflate`` harmonic Ritz values of least modulus and from the residual (:func:`_deflation`; their combinations replace the first vectors of the basis): the approximate eigenvectors of the eigenvalues nearest zero, which a plain restart loses and the next cycle must find again (restarted GMRES stalls on them: the indefinite tangents of softening points), stay in the space, and the cycle minimizes the residual over them and the Krylov vectors of the residual. The Hessenberg matrix of such a cycle has a full first block, factorized by Householder reflections, its next columns by rotations. A cycle that does not decrease the residual ends the solve; after deflated restarts the residual that reaches the tolerance is computed again (a product) and, if it is above it, the next cycle starts from it alone, as with ``deflate=0`` (the plain restarted GMRES: each cycle from the residual computed again) or a singular Hessenberg matrix. A solve that does not restart is that of the plain GMRES. Returns (x, iterations, relative residual); each iteration takes a product by the operator and one by the preconditioner, each cycle one more by the preconditioner, each residual computed again one more by the operator. Each iteration is a checkpoint of :mod:`morphogen.stopping`. ``recycle`` (a :class:`Recycling` shared by a sequence of solves): a solve that restarts leaves it the vectors of its last deflated restart, and the next solves of the sequence start from them by GCRO-DR (:func:`_gcro_dr`); the solves before the first restart are those without it, to the bit. ``stagnation``: a solve whose residual has not been halved over its last ``stagnation`` cycles stops there (0: never), an inexact correction of Newton's method that more cycles would improve only slowly. """ x = np.zeros_like(rhs) norm_b = norm(rhs) if norm_b == 0.0: return x, 0, 0.0 m = max(1, min(int(restart), int(maxiter))) k_max = min(int(deflate), m - 2) if recycle is not None and recycle.u is not None and k_max > 0: out = _gcro_dr(_HOST, apply, precondition, rhs, tol, maxiter, m, k_max, recycle, stagnation) # fmt: skip if out is not None: return out ends = [1.0] # the relative residuals at the ends of the cycles basis = np.empty((m + 1, rhs.size)) h = np.zeros((m + 1, m)) # the Arnoldi matrix of the cycle tri = np.zeros((m + 1, m)) # its triangular factor cs, sn, g, coef = np.zeros(m), np.zeros(m), np.zeros(m + 1), np.zeros(m + 1) c = np.zeros(m + 1) # the coordinates of the residual at the start of the cycle q0 = np.ones((1, 1)) # the orthogonal factor of the block of the kept vectors beta, total, res = norm_b, 0, 1.0 s, deflated = 0, False # the kept vectors (and the residual after them) np.divide(rhs, beta, out=basis[0]) c[0] = beta while total < maxiter: g[:] = 0.0 g[: s + 1] = q0.T @ c[: s + 1] k = s for j in range(s, min(m, s + maxiter - total)): checkpoint() w = apply(precondition(basis[j])) h[:, j] = 0.0 before = norm(w) for _ in range(2): _dots(basis, j + 1, w, coef) _subtract(basis, j + 1, coef, w) h[: j + 1, j] += coef[: j + 1] after = norm(w) if after > _REORTHOGONALIZE * before: # orthogonal enough break before = after h[j + 1, j] = after col = tri[:, j] col[:] = h[:, j] if s: col[: s + 1] = q0.T @ col[: s + 1] for i in range(s, j): # the rotations of the previous columns a, b = col[i], col[i + 1] col[i] = cs[i] * a + sn[i] * b col[i + 1] = cs[i] * b - sn[i] * a gamma = math.hypot(col[j], after) if not gamma > 0.0: # the operator vanishes on the space (or is not finite) break cs[j], sn[j] = col[j] / gamma, after / gamma col[j], col[j + 1] = gamma, 0.0 g[j + 1] = -sn[j] * g[j] g[j] *= cs[j] k = j + 1 total += 1 res = abs(g[k]) / norm_b if res <= tol or after == 0.0: break np.divide(w, after, out=basis[j + 1]) if k == 0: break y = np.zeros(m + 1) for i in range(k - 1, -1, -1): # the triangular system of the rotated Hessenberg y[i] = (g[i] - tri[i, i + 1 : k] @ y[i + 1 : k]) / tri[i, i] combined = np.zeros_like(rhs) _subtract(basis, k, -y, combined) x += precondition(combined) if total >= maxiter or (res <= tol and not deflated): break previous = beta full = res > tol and k == m and h[m, m - 1] > 0.0 if full and stagnation: ends.append(res) if _stagnates(ends, stagnation): break start = _deflation(h, c, y, m, k_max) if full and k_max > 0 else None if start is not None: p, hk, ck = start beta = res * norm_b if not beta < previous: break s = p.shape[1] - 1 _combine(basis, m + 1, p) h[:] = 0.0 h[: s + 1, :s] = hk c[:] = 0.0 c[: s + 1] = ck q0, r0 = np.linalg.qr(hk, mode="complete") tri[:] = 0.0 tri[: s + 1, :s] = r0 deflated = True continue r = rhs - apply(x) beta = norm(r) res = beta / norm_b if res <= tol or not beta < previous: break if deflated and recycle is not None: # before the plain cycle overwrites them _keep(_HOST, recycle, basis, h[: s + 1, :s]) np.divide(r, beta, out=basis[0]) c[:] = 0.0 c[0] = beta s, q0, deflated = 0, np.ones((1, 1)), False if deflated and recycle is not None: _keep(_HOST, recycle, basis, h[: s + 1, :s]) return x, total, res
def _stagnates(ends, cycles: int) -> bool: """Whether the relative residuals ``ends`` at the ends of the cycles of a solve (1 at its start) have not been halved over its last ``cycles`` cycles.""" return len(ends) > cycles and ends[-1] > 0.5 * ends[-1 - cycles]
[docs] class Recycling: """The space that :func:`gmres` recycles from a solve to the next of a sequence of systems whose operators change little, those of the Newton iterations of a loading path: GCRO-DR (Parks, de Sturler, Mackey, Johnson & Maiti 2006), the recycled vectors approximate eigenvectors of the eigenvalues nearest zero of the preconditioned operator, which restarted GMRES must otherwise find again in each solve. Empty until a solve of the sequence restarts, so that the solves before are those of GMRES with deflated restarts to the bit and cost nothing more: that solve leaves it the harmonic Ritz vectors of its last deflated restart, and each later solve minimizes its residual over them and the Krylov vectors of the operator projected out of their images, and keeps the harmonic Ritz vectors of that space at each of its own restarts. The solves of the same operator reuse the images of the recycled vectors; a new operator (:meth:`renew`: the tangent of the next Newton iteration) has them computed again by its first solve, ``k`` products (:attr:`products`), if the last solve filled a cycle (:attr:`needed`), and drops the space otherwise. The vectors live where those of the solves do (on the GPU for :func:`morphogen.homogenization.gpu.gmres`).""" def __init__(self): #: The recycled vectors (rows), in the variable of the preconditioned operator (the #: corrections are their images by the preconditioner), or None self.u = None #: Their images by the preconditioned operator, orthonormal self.c = None #: Whether :attr:`c` are the images by the operator of the next solve self.current = False #: Whether the last solve filled a cycle (it restarted, or would have without the #: recycled vectors): otherwise a new operator drops them (:meth:`renew`) self.needed = False #: The products by the operators spent on the images of the recycled vectors, and #: the solves started from them self.products = 0 self.solves = 0
[docs] def renew(self) -> None: """The next solves are those of another operator: the recycled vectors are kept if the last solve filled a cycle (:attr:`needed`), and their images will be computed again.""" if not self.needed: self.clear() self.current = False
[docs] def clear(self) -> None: """Drop the recycled space: the next solves are those of :func:`gmres` without it.""" self.u = self.c = None self.current = False
class _Host: """The operations on the vectors of :func:`_gcro_dr` and :func:`_keep` on the host: the kernels of :func:`gmres`, whose sums do not depend on the threads.""" norm = staticmethod(norm) zeros_like = staticmethod(np.zeros_like) @staticmethod def empty(rows: int, n: int) -> np.ndarray: return np.empty((rows, n)) @staticmethod def dots(basis, k: int, w) -> np.ndarray: out = np.empty(k) _dots(basis, k, w, out) return out @staticmethod def subtract(basis, k: int, coef, w) -> None: _subtract(basis, k, np.ascontiguousarray(coef, dtype=np.float64), w) @staticmethod def combine(basis, rows: int, p) -> None: _combine(basis, rows, p) _HOST = _Host() def _keep(ops, recycle: Recycling, basis, hk) -> None: """The space that a solve of :func:`gmres` which restarted leaves to ``recycle``: the ``s`` vectors ``W`` of its last deflated start (``basis[:s]``), whose images by the preconditioned operator are ``basis[:s + 1] hk`` (the Arnoldi relation of the deflated restart): with ``hk = Q R``, the vectors ``W R^-1`` and their images ``basis[:s + 1] Q``, orthonormal.""" s = hk.shape[1] if s == 0: return q, r = np.linalg.qr(hk) diag = np.abs(np.diag(r)) if not diag.min() > 1e-12 * diag.max(): return p = np.zeros((s + 1, 2 * s)) p[:s, :s] = sla.solve_triangular(r, np.eye(s)) p[:, s:] = q work = ops.empty(2 * s, basis.shape[1]) work[: s + 1] = basis[: s + 1] ops.combine(work, s + 1, p) recycle.u, recycle.c, recycle.current, recycle.needed = work[:s], work[s:], True, True def _orthonormalize(ops, rows, k: int): """Gram-Schmidt of the ``k`` vectors ``rows`` in place, each pass done again where it cancels most of the vector: their triangular factor (``rows = Q R``), or None when they are not independent.""" r = np.zeros((k, k)) largest = 0.0 for i in range(k): w = rows[i] before = ops.norm(w) largest = max(largest, before) after = before for _ in range(2 if i else 0): coef = ops.dots(rows, i, w) ops.subtract(rows, i, coef, w) r[:i, i] += coef after = ops.norm(w) if after > _REORTHOGONALIZE * before: break before = after if not after > 1e-10 * largest: return None r[i, i] = after w /= after return r def _recycled_space(h, e, m: int, k: int, keep: int): """The space that a full cycle of :func:`_gcro_dr` recycles: the harmonic Ritz vectors of its ``keep`` harmonic Ritz values of least modulus with respect to its images (a complex pair kept whole), the solutions ``z`` of ``G^T G z = theta G^T W^T V z`` (Parks et al. 2006), ``G = h`` the matrix of the cycle from its solution space ``V`` (the ``k`` recycled vectors, scaled to unit norms, and the ``m - k`` Krylov vectors) to its image space ``W`` (the images of the recycled vectors and the ``m - k + 1`` Krylov vectors, orthonormal), ``W^T V = [[e[:k], 0], [e[k:], I]]`` (``e = W^T U``). Returns ``(Z, Q)``: the new vectors ``V Z`` and their images ``W Q``, orthonormal (``G Z = Q``); None when the problem is singular or its vectors are not independent.""" t = np.zeros((m + 1, m)) t[:, :k] = e rows = np.arange(k, m) t[rows, rows] = 1.0 try: theta, z = sla.eig(h.T @ h, h.T @ t) except (np.linalg.LinAlgError, ValueError): return None vectors = [] for i in np.argsort(np.abs(theta), kind="stable"): if len(vectors) >= keep: break if not (np.isfinite(theta[i]) and np.all(np.isfinite(z[:, i]))): continue if theta[i].imag > 0.0: # a pair: its conjugate gives the same two real vectors vectors += [z[:, i].real, z[:, i].imag] elif theta[i].imag == 0.0: vectors.append(z[:, i].real) if not vectors: return None p, tri = np.linalg.qr(np.column_stack(vectors)) diag = np.abs(np.diag(tri)) p = p[:, diag > 1e-12 * diag.max()] q, tri = np.linalg.qr(h @ p) diag = np.abs(np.diag(tri)) if not diag.min() > 1e-12 * diag.max(): return None return p @ sla.solve_triangular(tri, np.eye(tri.shape[0])), q def _gcro_dr(ops, apply, precondition, rhs, tol, maxiter, m: int, k_max: int, recycle: Recycling, stagnation: int): # fmt: skip """GCRO-DR (Parks, de Sturler, Mackey, Johnson & Maiti 2006): :func:`gmres` from the space of ``recycle`` (``ops``: the operations on the vectors, :class:`_Host` or those of the GPU). With ``U`` its ``k`` vectors and ``C`` their orthonormal images by the preconditioned operator ``A M^-1`` (computed again for a new operator by ``k`` products and Gram-Schmidt, ``U`` turned with them), each cycle projects its residual out of ``C``, builds from it the Krylov vectors ``V`` of ``(I - C C^T) A M^-1`` (``m - k`` of them, each orthogonalized against ``C`` and the previous ones by the passes of :func:`gmres`, which give the coefficients ``B = C^T A M^-1 V``) and minimizes the residual over ``[U, V]``, whose images are ``[C, V] G`` with ``G = [[D, B], [0, H]]`` (``D`` the inverse norms of the ``U``, ``H`` the Hessenberg matrix): the least squares problem of :func:`gmres` with a diagonal first block and the same rotations. A full cycle keeps the harmonic Ritz vectors of ``[U, V]`` (:func:`_recycled_space`) as the next ``U``, combined in place with their images and the residual that starts the next cycle (``m + k + 2`` vectors at most). After more than one cycle the residual that reaches the tolerance is computed again (a product), and the cycles go on from it while it is above. Returns (x, iterations, relative residual), the products of the images counted as iterations; None when the images are not independent (the space is dropped).""" norm_b = ops.norm(rhs) n = rhs.size k = recycle.u.shape[0] rows = m + 1 + max(k, k_max + 1) # U, C and the Krylov vectors (a pair kept whole) work = ops.empty(rows, n) work[:k] = recycle.u current = recycle.current if current: work[k : 2 * k] = recycle.c recycle.u = recycle.c = None # the space lives in work while the solve runs total = 0 if not current: # the images by the new operator for i in range(k): checkpoint() work[k + i] = apply(precondition(work[i])) total = k recycle.products += k r = _orthonormalize(ops, work[k : 2 * k], k) if r is None: recycle.clear() return None ops.combine(work, k, sla.solve_triangular(r, np.eye(k))) recycle.solves += 1 x = ops.zeros_like(rhs) coords = np.zeros(m + 1) # the residual at the start of the cycle, on [C, V] start, ends, res, cycles = rhs, [1.0], 1.0, 0 while True: basis = work[k:] # C, then the Krylov vectors if start is not None: # the residual projected out of C basis[k] = start coords[:] = 0.0 before = ops.norm(basis[k]) for _ in range(2): coef = ops.dots(basis, k, basis[k]) ops.subtract(basis, k, coef, basis[k]) coords[:k] += coef after = ops.norm(basis[k]) if after > _REORTHOGONALIZE * before: break before = after coords[k] = after if after > 0.0: basis[k] /= after start = None d = np.array([ops.norm(work[i]) for i in range(k)]) h = np.zeros((m + 1, m)) h[np.arange(k), np.arange(k)] = 1.0 / d tri = h.copy() g = coords.copy() cs, sn = np.zeros(m), np.zeros(m) kend = k res = abs(g[k]) / norm_b for j in range(k, min(m, k + maxiter - total) if res > tol else k): checkpoint() w = apply(precondition(basis[j])) before = ops.norm(w) for _ in range(2): coef = ops.dots(basis, j + 1, w) ops.subtract(basis, j + 1, coef, w) h[: j + 1, j] += coef after = ops.norm(w) if after > _REORTHOGONALIZE * before: break before = after h[j + 1, j] = after col = tri[:, j] col[:] = h[:, j] for i in range(k, j): a, b = col[i], col[i + 1] col[i] = cs[i] * a + sn[i] * b col[i + 1] = cs[i] * b - sn[i] * a gamma = math.hypot(col[j], after) if not gamma > 0.0: break cs[j], sn[j] = col[j] / gamma, after / gamma col[j], col[j + 1] = gamma, 0.0 g[j + 1] = -sn[j] * g[j] g[j] *= cs[j] kend = j + 1 total += 1 res = abs(g[kend]) / norm_b if res <= tol or after == 0.0: break basis[j + 1] = w / after cycles += 1 y = np.zeros(m) for i in range(kend - 1, -1, -1): y[i] = (g[i] - tri[i, i + 1 : kend] @ y[i + 1 : kend]) / tri[i, i] combined = ops.zeros_like(rhs) ops.subtract(work, k, -y[:k] / d, combined) if kend > k: ops.subtract(basis[k:], kend - k, -y[k:kend], combined) x += precondition(combined) if res <= tol or total >= maxiter or kend < m: if res <= tol and cycles > 1: r = rhs - apply(x) true = ops.norm(r) / norm_b if true > tol and true < ends[-1] and total < maxiter: ends.append(true) start = r continue res = true break ends.append(res) if not ends[-1] < ends[-2] or (stagnation and _stagnates(ends, stagnation)): break e = np.empty((m + 1, k)) # W^T U, scaled as the first columns of h for i in range(k): e[:, i] = ops.dots(basis, m + 1, work[i]) / d[i] z = coords - h @ y # the residual of the cycle on [C, V] new = _recycled_space(h, e, m, k, k_max) kk = k if new is None else new[1].shape[1] p = np.zeros((k + m + 1, 2 * kk + 1)) if new is None: # U and C kept p[np.arange(k), np.arange(k)] = 1.0 q = np.eye(m + 1, k) else: zs, q = new p[:k, :kk] = zs[:k] / d[:, None] p[2 * k : k + m, :kk] = zs[k:] cq = q.T @ z perp = z - q @ cq perp -= q @ (q.T @ perp) size = float(np.linalg.norm(perp)) p[k:, kk : 2 * kk] = q if size > 0.0: p[k:, 2 * kk] = perp / size ops.combine(work, k + m + 1, p) k = kk coords[:] = 0.0 coords[:k] = cq coords[k] = size recycle.u, recycle.c, recycle.current = work[:k].copy(), work[k : 2 * k].copy(), True recycle.needed = cycles > 1 or kend == m return x, total, res
[docs] class TwoLevelPreconditioner: """Symmetric two-level preconditioner of ``A`` with a coarse space ``P``. A forward Gauss-Seidel sweep on ``A``, a correction by one AMG V-cycle on the Galerkin matrix ``P^T A P``, then a backward sweep (so the preconditioner is symmetric). With ``P`` the interpolation of the linear (4-node) elements into the quadratic (10-node) ones, the coarse matrix is the stiffness of the linear elements, on which smoothed aggregation is efficient. ``dofs``, ``coarse_dofs``: the degree of freedom ``3 node + component`` of each unknown of the matrix and of the coarse space, where they are components of the nodes of a mesh (the sweeps then work by nodes, see :class:`~morphogen.homogenization.amg.Smoother`); ``blocks``: the blocks of the matrix, where they have been made already (:class:`~morphogen.homogenization.amg.NodeBlocks`). """ def __init__(self, matrix, prolongation, near_null=None, dofs=None, coarse_dofs=None, blocks=None): # fmt: skip self.matrix = sp.csr_matrix(matrix) self.matrix.sort_indices() self.p = sp.csr_matrix(prolongation) self.pt = self.p.T.tocsr() coarse = (self.pt @ self.matrix @ self.p).tocsr() self.amg = SmoothedAggregation(coarse, _candidates(near_null), dofs=coarse_dofs) self.smoother = Smoother(self.matrix, dofs, blocks) if self.smoother.coloured: # the cycle in the order of the colours of the smoother: the interpolation # with its rows at their places in that order rows = self.p.tocoo() shape = (self.smoother.size, self.p.shape[1]) places = (self.smoother.place[rows.row], rows.col) self.p = sp.csr_matrix((rows.data, places), shape=shape) self.pt = self.p.T.tocsr()
[docs] def refresh(self, blocks: NodeBlocks) -> bool: """The sweeps for the values that the blocks of the matrix have now (see :meth:`~morphogen.homogenization.amg.Smoother.refresh`); the coarse space and its multigrid cycle are kept. The preconditioner stays symmetric positive definite: the coarse correction adds a positive term to the symmetric sweeps of the matrix as it is.""" return self.smoother.refresh(blocks)
def __call__(self, r: np.ndarray) -> np.ndarray: smoother = self.smoother if smoother.coloured: b = smoother.sorted(np.ascontiguousarray(r, dtype=float)) x = smoother.start(b) residual = smoother.residual(x) x += product(self.p, self.amg(product(self.pt, residual))) smoother.relax(x, b, False) return smoother.unsorted(x) x = np.zeros_like(r) smoother.sweep(x, r, True) residual = r - product(self.matrix, x) x += product(self.p, self.amg(product(self.pt, residual))) smoother.sweep(x, r, False) return x
def _candidates(near_null): if near_null is None: return None b = np.asarray(near_null, dtype=float) return b[:, np.linalg.norm(b, axis=0) > 0]
[docs] class LinearSolver: """Solver of A x = b for a fixed matrix A and several right-hand sides. ``near_null``: low-energy modes (columns) of A, used by algebraic multigrid. ``coarse``: ``(P, near_null_coarse)``, a coarse space for the two-level ``amg`` preconditioner (see :class:`TwoLevelPreconditioner`). ``symmetric``: false for a matrix that is not symmetric (the tangent of nonsymmetric consistent tangents), which the iterative methods solve by :func:`gmres` with the preconditioner of its symmetric part (LU factorizes it as it is). ``dofs``: the degree of freedom ``3 node + component`` of each unknown, where the unknowns are components of the displacements of the nodes of a mesh (the sweeps of the multigrid preconditioners then work by nodes, see :class:`~morphogen.homogenization.amg.Smoother`; ``coarse`` may carry those of its coarse space as a third item). The products of the iterative methods then read the matrix by the 3 x 3 blocks of its nodes (:attr:`blocks`: :class:`~morphogen.homogenization.amg.NodeBlocks`, the same products to the bit). """ def __init__( self, matrix, *, method="auto", tol=1e-8, maxiter=None, near_null=None, coarse=None, symmetric: bool = True, dofs=None, ): self.matrix = sp.csr_matrix(matrix) n = self.matrix.shape[0] method = choose_method(method, n) self.method = method self.tol = float(tol) self.maxiter = maxiter self.symmetric = bool(symmetric) t0 = time.perf_counter() self._precondition = None self._dofs = dofs #: The matrix by blocks of nodes, for the products of the iterative methods self.blocks = None #: The iterations per decade of the residual of the solves since the last step #: of a path, and those of the step for which the preconditioner was built self._wear = {"rates": [], "reference": None} if n and method != "direct": # (rows in the order of their columns: the order in which the blocks sum them) self.matrix.sort_indices() self.blocks = NodeBlocks.of(self.matrix, dofs) # the preconditioners are those of the symmetric part (which has its own blocks) part = self.matrix if self.symmetric else (0.5 * (self.matrix + self.matrix.T)).tocsr() shared = self.blocks if self.symmetric else None if n == 0: pass elif method == "direct": self._lu = spla.splu( self.matrix.tocsc(), permc_spec="MMD_AT_PLUS_A", options={"SymmetricMode": True} ) elif method == "amg": if coarse is not None: p, coarse_null = coarse[:2] coarse_dofs = coarse[2] if len(coarse) > 2 else None self._precondition = TwoLevelPreconditioner(part, p, coarse_null, dofs, coarse_dofs, shared) # fmt: skip self.method = "amg-2level" else: self._precondition = SmoothedAggregation(part, _candidates(near_null), dofs=dofs, blocks=shared) # fmt: skip else: d = self.matrix.diagonal() inv = 1.0 / np.where(d > 0, d, 1.0) self._precondition = lambda r: inv * r self.setup_s = time.perf_counter() - t0
[docs] def updated(self, matrix, symmetric: bool | None = None) -> LinearSolver: """Solver of another matrix of the same size (a new tangent operator): direct methods factorize it, iterative ones keep this preconditioner (``symmetric``: whether the matrix is, by default as this one). This solver is not to be used afterwards: the blocks of its matrix take the values of the new one, and with them the sweeps of a multigrid preconditioner that work by nodes (for a symmetric matrix of the same pattern) — the interpolations and the coarse levels are kept, and the preconditioner stays symmetric positive definite.""" if self.method == "direct" or self._precondition is None: return LinearSolver(matrix, method="direct", tol=self.tol, maxiter=self.maxiter) out = object.__new__(LinearSolver) out.__dict__.update(self.__dict__) out.matrix = sp.csr_matrix(matrix) out.setup_s = 0.0 if symmetric is not None: out.symmetric = bool(symmetric) if self.blocks is not None: if not self.blocks.refresh(out.matrix): # (other stored values: other blocks) out.blocks = NodeBlocks.of(out.matrix, self._dofs) elif out.symmetric and hasattr(self._precondition, "refresh"): self._precondition.refresh(self.blocks) return out
[docs] def worn(self) -> bool: """Whether the preconditioner is to be built again, asked at the start of a step of a loading path, before the solver is :meth:`updated`: true for a factorization or a diagonal (built with the solver); for a multigrid preconditioner, when the solves of the last step took :data:`WORN` times the iterations per decade of their residual that those of the step for which it was built took (the tangent has moved away from the one whose coarse levels it holds).""" if not isinstance(self._precondition, TwoLevelPreconditioner | SmoothedAggregation): return True wear = self._wear rates, wear["rates"] = wear["rates"], [] if not rates: return False last = sum(rates) / len(rates) if wear["reference"] is None: wear["reference"] = last return False return last > WORN * wear["reference"]
def _product(self, x: np.ndarray) -> np.ndarray: """``A x``: by the blocks of the nodes where the matrix has them.""" if self.blocks is not None and x.ndim == 1: return self.blocks.product(x) return product(self.matrix, x)
[docs] def solve( self, rhs: np.ndarray, x0: np.ndarray | None = None, tol: float | None = None ) -> tuple[np.ndarray, SolveInfo]: """Solution of ``A x = rhs``; iterative methods start from ``x0`` if given and stop at the relative residual ``tol`` (default: that of the solver).""" n = self.matrix.shape[0] b = np.asarray(rhs, dtype=float) t0 = time.perf_counter() norm_b = norm(b.ravel()) if n == 0 or norm_b == 0.0: return np.zeros(n), SolveInfo(self.method, n, 0, 0.0, self.setup_s, 0.0) tol = self.tol if tol is None else float(tol) iterations = 0 if self.method == "direct": x = self._lu.solve(b) else: default = 50_000 if self.method == "cg" else 2_000 start = None if x0 is None or not np.any(x0) else np.asarray(x0, dtype=float) r = b if start is None else b - self._product(start) norm_r = norm(r) if norm_r <= tol * norm_b: x = np.zeros(n) if start is None else start.copy() else: krylov = conjugate_gradient if self.symmetric else gmres x, iterations, _ = krylov( self._product, self._precondition, r, tol * norm_b / norm_r, self.maxiter or default, ) if start is not None: x += start residual = norm((b - self._product(x)).ravel()) / norm_b if iterations and start is None: # (the wear of the preconditioner: see worn) decades = max(-math.log10(max(residual, 1e-300)), 0.5) self._wear["rates"].append(iterations / decades) if self.method != "direct" and residual > 10 * tol: log.warning( "%s solver stopped at relative residual %.2e (tolerance %.1e)", self.method, residual, tol, ) info = SolveInfo( self.method, n, iterations, residual, self.setup_s, time.perf_counter() - t0 ) return x, info