Files
leonarski_fandClaude Opus 5.5 c582a48131 Refinement on the GPU: the reorthogonalisation in three kernels, and less memory
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
2026-11-17 15:51:17 +01:00

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;
}