// SPDX-FileCopyrightText: 2026 Filip Leonarski, Paul Scherrer Institute // SPDX-License-Identifier: GPL-3.0-only #pragma once #include #include #include #include #include #include "../../common/ParallelFor.h" // Sweeps over the parameters on `nthreads` threads: each element on its own, and dot products folded in fixed // blocks (ParallelBlocks), so that the bits do not depend on the number of threads. namespace refine_vec { // a pass over fewer than this many parameters per thread costs less than waking the threads constexpr size_t SWEEP_PER_THREAD = 65536; template void Each(size_t n, size_t nthreads, Fn fn) { ParallelChunks(static_cast(n), ThreadsForWork(n, nthreads, SWEEP_PER_THREAD), [&](int lo, int hi) { for (int k = lo; k < hi; k++) fn(static_cast(k)); }); } inline double Dot(const std::vector &a, const std::vector &b, size_t nthreads) { const int n = static_cast(a.size()); std::vector part(ReductionBlocks(n, SWEEP_PER_THREAD), 0.0); ParallelBlocks(n, nthreads, [&](int block, int lo, int hi) { double s = 0; for (int k = lo; k < hi; k++) s += a[k] * b[k]; part[block] = s; }, SWEEP_PER_THREAD); double s = 0; for (double v : part) s += v; return s; } } // namespace refine_vec // Limited-memory BFGS whose initial inverse Hessian is the caller's (SetInverseHessian: H0 q, here the Gauss-Newton // normal matrix solved by ConjugateGradients), and whose memory outlives one call, so that a refinement's // macro-cycles - each a few iterations on a target whose scale and likelihood parameters were refitted in between - // go on from what the earlier ones learnt. The normal matrix holds what is known of the curvature in advance (the // restraints exactly, the X-ray target per atom); the pairs add what it leaves out (the X-ray target's coupling of // neighbouring atoms). The line search backtracks from the full step to sufficient decrease. // Following Nocedal (1980) Math. Comp. 35, 773-782 and Liu & Nocedal (1989) Math. Program. 45, 503-528 class RefinementMinimiser { public: // f(x, g): the target at x, and its gradient in g (sized as x); false where it cannot be evaluated there. using Target = std::function &x, double &f, std::vector &g)>; // q = H0 q at x. using InverseHessian = std::function &x, std::vector &q)>; // `nthreads`: the threads the sweeps over the parameters run on. explicit RefinementMinimiser(size_t memory = 20, size_t nthreads = 1) : memory_(memory), nthreads_(nthreads) {} // Forget the pairs (the target changed beyond what the memory still describes). void Reset() { s_.clear(); y_.clear(); sy_.clear(); } void SetInverseHessian(InverseHessian h0) { h0_ = std::move(h0); } struct Outcome { int iterations = 0; int evaluations = 0; double f_start = 0, f_end = 0; }; // At most `iterations` iterations from x (x is where it ended); stops early where an iteration lowers f by // less than `f_tolerance` relative to |f|, or `stop` says so (checked before every iteration). `max_step`, in // the parameters' units, is the most any parameter moves in the first trial of a line search. Outcome Minimise(const Target &target, std::vector &x, int iterations, double f_tolerance, double max_step, const std::function &stop = nullptr) { const size_t n = x.size(); Outcome out; double f = 0; std::vector g(n), d(n), x_new(n), g_new(n); if (!target(x, f, g)) return out; out.evaluations++; out.f_start = out.f_end = f; for (int it = 0; it < iterations; it++) { if (stop && stop()) break; Direction(x, g, d); double gd = Dot(g, d); if (!(gd < 0)) { // not a descent direction: the memory no longer fits, start again from H0 Reset(); Direction(x, g, d); gd = Dot(g, d); if (!(gd < 0)) break; } double d_max = 0; for (double v : d) d_max = std::max(d_max, std::fabs(v)); double alpha = d_max > max_step ? max_step / d_max : 1.0; double f_new = 0; bool accepted = false; for (int ls = 0; ls < 10; ls++) { refine_vec::Each(n, nthreads_, [&](size_t k) { x_new[k] = x[k] + alpha * d[k]; }); const bool ok = target(x_new, f_new, g_new); out.evaluations++; if (ok && f_new <= f + 1e-4 * alpha * gd) { accepted = true; break; } // the minimum of the quadratic through f, its slope and f_new, kept within [0.1, 0.5] of the step const double q = ok ? -gd * alpha * alpha / (2.0 * (f_new - f - gd * alpha)) : 0.1 * alpha; alpha = std::clamp(q, 0.1 * alpha, 0.5 * alpha); } if (!accepted) break; std::vector s(n), y(n); refine_vec::Each(n, nthreads_, [&](size_t k) { s[k] = x_new[k] - x[k]; y[k] = g_new[k] - g[k]; }); const double sy = Dot(s, y); if (sy > 1e-10 * std::sqrt(Dot(s, s) * Dot(y, y))) { s_.push_back(std::move(s)); y_.push_back(std::move(y)); sy_.push_back(sy); if (s_.size() > memory_) { s_.pop_front(); y_.pop_front(); sy_.pop_front(); } } const double decrease = f - f_new; x.swap(x_new); g.swap(g_new); f = f_new; out.iterations++; out.f_end = f; if (decrease <= f_tolerance * std::max(std::fabs(f), 1.0)) break; } return out; } private: double Dot(const std::vector &a, const std::vector &b) const { return refine_vec::Dot(a, b, nthreads_); } // d = -H g by the two-loop recursion, H0 the caller's. void Direction(const std::vector &x, const std::vector &g, std::vector &d) const { const size_t m = s_.size(), n = g.size(); std::vector q = g, a(m); for (size_t i = m; i-- > 0;) { a[i] = Dot(s_[i], q) / sy_[i]; refine_vec::Each(n, nthreads_, [&](size_t k) { q[k] -= a[i] * y_[i][k]; }); } h0_(x, q); for (size_t i = 0; i < m; i++) { const double b = Dot(y_[i], q) / sy_[i]; refine_vec::Each(n, nthreads_, [&](size_t k) { q[k] += s_[i][k] * (a[i] - b); }); } d.resize(n); refine_vec::Each(n, nthreads_, [&](size_t k) { d[k] = -q[k]; }); } size_t memory_, nthreads_; InverseHessian h0_; std::deque> s_, y_; std::deque sy_; // s.y of each pair, as taken when it was kept }; // z with H z = b to `tolerance` of |b| (at most `max_iterations`), by conjugate gradients preconditioned with M: // hv = H v (product), z = M^-1 r (precondition), both symmetric positive definite. Returns the iterations taken. // Following Hestenes & Stiefel (1952) J. Res. Natl. Bur. Stand. 49, 409-436 // Each residual is made M^-1-orthogonal again to all the earlier ones (Gram-Schmidt, every coefficient r_j M^-1 r / // r_j M^-1 r_j = z . r_j / rz_j from the same z, then r and z = M^-1 r corrected together). Without it the recurrence loses that orthogonality in rounding once the first Ritz values converge, and // from then on amplifies a rounding difference several times per iteration: on the refinement's normal matrix two // solves of right-hand sides 1e-14 apart ended up to 7% apart after 20 iterations, which set CPU and GPU apart. // The loss of orthogonality after Paige (1976) J. Inst. Maths Applics 18, 341-349 and Greenbaum (1989) Linear // Algebra Appl. 113, 7-63 inline int ConjugateGradients(const std::function &v, std::vector &hv)> &product, const std::function &r, std::vector &z)> &precondition, const std::vector &b, std::vector &x, int max_iterations, double tolerance, size_t nthreads = 1) { auto dot = [&](const std::vector &u, const std::vector &v) { return refine_vec::Dot(u, v, nthreads); }; const size_t n = b.size(); x.assign(n, 0.0); std::vector r = b, z(n), p, hp(n); precondition(r, z); p = z; double rz = dot(r, z); std::vector> rs{r}, zs{z}; // the residuals so far, and M^-1 of each std::vector rzs{rz}; const double r0 = std::sqrt(dot(r, r)); int k = 0; while (k < max_iterations) { k++; product(p, hp); const double php = dot(p, hp); if (!(php > 0)) break; const double a = rz / php; refine_vec::Each(n, nthreads, [&](size_t j) { x[j] += a * p[j]; r[j] -= a * hp[j]; }); if (std::sqrt(dot(r, r)) < tolerance * r0) break; precondition(r, z); std::vector c(rs.size()); for (size_t i = 0; i < rs.size(); i++) c[i] = dot(z, rs[i]) / rzs[i]; refine_vec::Each(n, nthreads, [&](size_t j) { for (size_t i = 0; i < rs.size(); i++) { r[j] -= c[i] * rs[i][j]; z[j] -= c[i] * zs[i][j]; } }); const double rz_new = dot(r, z); refine_vec::Each(n, nthreads, [&](size_t j) { p[j] = z[j] + rz_new / rz * p[j]; }); rz = rz_new; rs.push_back(r); zs.push_back(z); rzs.push_back(rz); } return k; }