The residuals' reorthogonalisation launched a dot and a projection per earlier residual (about 570 extra launches per solve): a solve took 5.7-10 ms on the small models against 1.5-3.8 ms before it. All coefficients are now taken at once from the same z (classical Gram-Schmidt: c_j = z . r_j / rz_j, on the CPU too), in one partial-sum kernel over all kept residuals, one finish and one projection: 1.9-4.4 ms per solve (myob 3.3, cytc 2.8, 7ris 2.6, 9zlo 1.9, 7l6j 4.4 ms; 4ybb 44 ms, as before the reorthogonalisation). Memory: the per-residue preconditioner keeps only the lower triangle of each block inverse, and the kept M^-1 r_j are in float (c_j comes from r_j, kept in pairs, so float's rounding of z_j enters only as c_j times it, far below the pairs). 4ybb peak GPU memory 14838 -> 14198 MiB (base 12982, without the reorthogonalisation 14038). Device vs host still median 3e-14, max 6e-12 (myob, cytc, every solve); a 1e-12 change of the right-hand side moves the solve by 2e-12. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01UqXYdHHZ4cogS1mrGUtfN7
228 lines
10 KiB
C++
228 lines
10 KiB
C++
// SPDX-FileCopyrightText: 2026 Filip Leonarski, Paul Scherrer Institute <filip.leonarski@psi.ch>
|
|
// SPDX-License-Identifier: GPL-3.0-only
|
|
|
|
#pragma once
|
|
|
|
#include <algorithm>
|
|
#include <cmath>
|
|
#include <deque>
|
|
#include <functional>
|
|
#include <vector>
|
|
|
|
#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 <typename Fn>
|
|
void Each(size_t n, size_t nthreads, Fn fn) {
|
|
ParallelChunks(static_cast<int>(n), ThreadsForWork(n, nthreads, SWEEP_PER_THREAD), [&](int lo, int hi) {
|
|
for (int k = lo; k < hi; k++)
|
|
fn(static_cast<size_t>(k));
|
|
});
|
|
}
|
|
inline double Dot(const std::vector<double> &a, const std::vector<double> &b, size_t nthreads) {
|
|
const int n = static_cast<int>(a.size());
|
|
std::vector<double> 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<bool(const std::vector<double> &x, double &f, std::vector<double> &g)>;
|
|
// q = H0 q at x.
|
|
using InverseHessian = std::function<void(const std::vector<double> &x, std::vector<double> &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<double> &x, int iterations, double f_tolerance, double max_step,
|
|
const std::function<bool()> &stop = nullptr) {
|
|
const size_t n = x.size();
|
|
Outcome out;
|
|
double f = 0;
|
|
std::vector<double> 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<double> 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<double> &a, const std::vector<double> &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<double> &x, const std::vector<double> &g, std::vector<double> &d) const {
|
|
const size_t m = s_.size(), n = g.size();
|
|
std::vector<double> 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<std::vector<double>> s_, y_;
|
|
std::deque<double> 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<void(const std::vector<double> &v, std::vector<double> &hv)> &product,
|
|
const std::function<void(const std::vector<double> &r, std::vector<double> &z)> &precondition,
|
|
const std::vector<double> &b, std::vector<double> &x, int max_iterations, double tolerance,
|
|
size_t nthreads = 1) {
|
|
auto dot = [&](const std::vector<double> &u, const std::vector<double> &v) { return refine_vec::Dot(u, v, nthreads); };
|
|
const size_t n = b.size();
|
|
x.assign(n, 0.0);
|
|
std::vector<double> r = b, z(n), p, hp(n);
|
|
precondition(r, z);
|
|
p = z;
|
|
double rz = dot(r, z);
|
|
std::vector<std::vector<double>> rs{r}, zs{z}; // the residuals so far, and M^-1 of each
|
|
std::vector<double> 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<double> 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;
|
|
}
|