tensor4all_core/floating_zone.rs
1//! Greedy coordinate-descent (floating-zone) search for high-error points.
2//!
3//! The floating-zone walk is the strongest global pivot search used in this
4//! codebase: from a starting point it repeatedly sweeps every site
5//! coordinate, moving each coordinate to the value with the largest
6//! interpolation error, until the error stops improving or exceeds a
7//! tolerance. It is a strict generalization of the single-cross search used
8//! elsewhere (one sweep with no repeats equals a cross scan).
9
10use crate::MultiIndex;
11
12/// Invalid search inputs or an error from a floating-zone evaluator.
13///
14/// [`floating_zone_walk`] and [`floating_zone_walk_with_initial_error`]
15/// validate their arguments before evaluating any candidate. Callback failures
16/// retain their original type in [`Self::Evaluation`].
17///
18/// # Examples
19///
20/// ```
21/// use tensor4all_core::{floating_zone_walk_with_initial_error, FloatingZoneError};
22/// let result = floating_zone_walk_with_initial_error::<_, std::convert::Infallible>(
23/// &[2], &vec![], 0.0, 0, 1.0, |_, _| unreachable!(),
24/// );
25/// assert_eq!(result, Err(FloatingZoneError::StartingPointLength {
26/// expected: 1, actual: 0,
27/// }));
28/// ```
29#[derive(Debug, PartialEq, thiserror::Error)]
30#[non_exhaustive]
31pub enum FloatingZoneError<E> {
32 /// A site's local dimension is zero.
33 #[error("floating-zone site {site} has zero local dimension")]
34 InvalidLocalDimension {
35 /// Position of the invalid site.
36 site: usize,
37 },
38 /// The starting point has the wrong number of coordinates.
39 #[error("floating-zone starting point has length {actual}; expected {expected}")]
40 StartingPointLength {
41 /// Number of local dimensions.
42 expected: usize,
43 /// Number of supplied coordinates.
44 actual: usize,
45 },
46 /// A starting coordinate is outside its site's local dimension.
47 #[error("floating-zone coordinate {coordinate} at site {site} exceeds dimension {dimension}")]
48 StartingCoordinate {
49 /// Position of the invalid site.
50 site: usize,
51 /// Supplied coordinate.
52 coordinate: usize,
53 /// Exclusive upper bound for the coordinate.
54 dimension: usize,
55 },
56 /// The supplied starting error is negative or nonfinite.
57 #[error("floating-zone starting error must be finite and nonnegative; got {value}")]
58 InvalidInitialError {
59 /// Supplied starting error.
60 value: f64,
61 },
62 /// The stopping tolerance is negative or NaN.
63 #[error("floating-zone stopping tolerance must be nonnegative and not NaN; got {value}")]
64 InvalidTolerance {
65 /// Supplied stopping tolerance; positive infinity is permitted.
66 value: f64,
67 },
68 /// The coordinate scan's vector storage cannot be represented.
69 #[error("floating-zone candidate storage overflows at site {site}")]
70 AllocationSizeOverflow {
71 /// Position of the site whose candidate batch is too large.
72 site: usize,
73 },
74 /// The error-magnitude callback failed.
75 #[error("floating-zone evaluation failed: {0}")]
76 Evaluation(#[source] E),
77}
78
79/// Walk one floating-zone search trajectory.
80///
81/// Mirrors `TensorCrossInterpolation.jl`'s `_floatingzone`: starting from
82/// `init_p`, each sweep visits every site in order and moves that site's
83/// coordinate to the value with the largest error (as measured by
84/// `eval_batch`), keeping the running maximum error monotonically
85/// non-decreasing. The walk stops when a sweep does not increase the
86/// maximum error (the trajectory is stuck on a local maximum) or when the
87/// maximum error exceeds `early_stop_tol` (the point is already
88/// significant), or after `max_sweeps` sweeps as a safety bound.
89///
90/// # Arguments
91///
92/// * `local_dims` - Local dimension of each site.
93/// * `init_p` - Starting multi-index; must have length `local_dims.len()`.
94/// * `max_sweeps` - Upper bound on the number of coordinate sweeps. The
95/// no-improvement early stop almost always fires first.
96/// * `early_stop_tol` - Stop walking once the maximum error exceeds this
97/// value; the caller has found a significantly wrong point.
98/// * `eval_batch` - Evaluates the error magnitude `|f - tt|` at a batch of
99/// multi-indices. It is called once for the starting point with a scan site
100/// of `None`, and then once per site per sweep with `Some(site)` and that
101/// site's `local_dims[site] - 1` *other* candidate points: the candidate
102/// equal to the current pivot is not re-evaluated, because the walk already
103/// knows its error from the step that moved there. The scan site is passed
104/// so that a caller whose evaluator exploits scan structure can declare it
105/// rather than infer it from the batch, which a single-point batch cannot
106/// support.
107///
108/// # Returns
109///
110/// The final pivot and the maximum error encountered along the walk. The
111/// returned error may exceed `early_stop_tol`; the caller decides whether
112/// the point is significant.
113///
114/// # Errors
115///
116/// Returns [`FloatingZoneError`] before evaluating anything for a zero local
117/// dimension, a starting-point length or coordinate mismatch, a negative or
118/// NaN `early_stop_tol`, or an unrepresentable candidate allocation. Positive
119/// infinity is a valid stopping tolerance, and empty `local_dims` are valid
120/// with an empty starting point. Callback errors are wrapped in
121/// [`FloatingZoneError::Evaluation`] with their original value and type.
122///
123/// # Examples
124///
125/// ```
126/// use tensor4all_core::{floating_zone_walk, FloatingZoneError};
127///
128/// // A separable error surface whose maximum is the all-last-coordinate
129/// // point, so a greedy coordinate walk must find it exactly.
130/// let local_dims = [3usize, 4, 2];
131/// let error_at = |point: &Vec<usize>| point.iter().map(|&c| c as f64).sum::<f64>();
132/// let mut evaluated = 0usize;
133/// let (pivot, error) = floating_zone_walk::<_, std::convert::Infallible>(
134/// &local_dims,
135/// &vec![0usize, 0, 0],
136/// 16,
137/// f64::INFINITY,
138/// |_site, points| {
139/// evaluated += points.len();
140/// Ok(points.iter().map(error_at).collect())
141/// },
142/// )?;
143///
144/// assert_eq!(pivot, vec![2, 3, 1]);
145/// assert_eq!(error, 6.0);
146/// // One point for the start, then `local_dims[site] - 1` per site scan: the
147/// // coordinate the pivot already holds is never re-evaluated.
148/// assert_eq!(evaluated, 1 + 2 * ((3 - 1) + (4 - 1) + (2 - 1)));
149/// # Ok::<(), FloatingZoneError<std::convert::Infallible>>(())
150/// ```
151pub fn floating_zone_walk<E, Err>(
152 local_dims: &[usize],
153 init_p: &MultiIndex,
154 max_sweeps: usize,
155 early_stop_tol: f64,
156 mut eval_batch: E,
157) -> std::result::Result<(MultiIndex, f64), FloatingZoneError<Err>>
158where
159 E: FnMut(Option<usize>, &[MultiIndex]) -> std::result::Result<Vec<f64>, Err>,
160{
161 validate_search(local_dims, init_p, max_sweeps, early_stop_tol)?;
162 // Initial error at the starting point. This also seeds `pivot_error`,
163 // which is what lets every site scan below skip the candidate the pivot
164 // already holds.
165 let start_errors =
166 eval_batch(None, std::slice::from_ref(init_p)).map_err(FloatingZoneError::Evaluation)?;
167 floating_zone_walk_unchecked(
168 local_dims,
169 init_p,
170 start_errors.first().copied().unwrap_or(0.0),
171 max_sweeps,
172 early_stop_tol,
173 eval_batch,
174 )
175 .map_err(FloatingZoneError::Evaluation)
176}
177
178/// Walk a floating-zone trajectory using an already evaluated starting error.
179///
180/// This shares the site order, tie breaking, and stopping rule of
181/// [`floating_zone_walk`], but skips its initial `eval_batch(None, ...)` call.
182/// Use it when starting points were evaluated together before the search.
183/// `initial_error` must be the same finite, nonnegative error magnitude that the
184/// callback would return for `init_p`. The other arguments have the meaning
185/// documented on [`floating_zone_walk`]. The callback receives `Some(site)`
186/// for each nonempty batch of that site's other coordinate values.
187///
188/// Returns the final pivot and the maximum error encountered, including
189/// `initial_error`. With zero sweeps, returns the starting point and error.
190///
191/// # Errors
192///
193/// Returns [`FloatingZoneError`] before evaluation for a zero local dimension,
194/// a starting-point length or coordinate mismatch, a negative or NaN
195/// `early_stop_tol`, or an unrepresentable candidate allocation. Positive
196/// infinity is a valid stopping tolerance. Empty `local_dims` are valid with an
197/// empty starting point. Validation also applies with zero sweeps. A negative
198/// or nonfinite `initial_error` is rejected after those checks. Callback errors
199/// are wrapped in [`FloatingZoneError::Evaluation`] with their original value
200/// and type.
201///
202/// # Examples
203///
204/// ```
205/// use tensor4all_core::floating_zone_walk_with_initial_error;
206/// let mut points_evaluated = 0;
207/// let (pivot, error) = floating_zone_walk_with_initial_error::<_, std::convert::Infallible>(
208/// &[2, 3], &vec![0, 1], 1.0, 4, f64::INFINITY,
209/// |site, points| {
210/// assert!(site.is_some());
211/// points_evaluated += points.len();
212/// Ok(points.iter().map(|p| (p[0] + p[1]) as f64).collect())
213/// },
214/// )?;
215/// assert_eq!((pivot, error), (vec![1, 2], 3.0));
216/// assert_eq!(points_evaluated, 2 * (1 + 2));
217/// # Ok::<(), tensor4all_core::FloatingZoneError<std::convert::Infallible>>(())
218/// ```
219pub fn floating_zone_walk_with_initial_error<E, Err>(
220 local_dims: &[usize],
221 init_p: &MultiIndex,
222 initial_error: f64,
223 max_sweeps: usize,
224 early_stop_tol: f64,
225 eval_batch: E,
226) -> std::result::Result<(MultiIndex, f64), FloatingZoneError<Err>>
227where
228 E: FnMut(Option<usize>, &[MultiIndex]) -> std::result::Result<Vec<f64>, Err>,
229{
230 validate_search(local_dims, init_p, max_sweeps, early_stop_tol)?;
231 if !initial_error.is_finite() || initial_error < 0.0 {
232 return Err(FloatingZoneError::InvalidInitialError {
233 value: initial_error,
234 });
235 }
236 floating_zone_walk_unchecked(
237 local_dims,
238 init_p,
239 initial_error,
240 max_sweeps,
241 early_stop_tol,
242 eval_batch,
243 )
244 .map_err(FloatingZoneError::Evaluation)
245}
246
247/// Checks every search argument the two public entry points share.
248///
249/// Runs before any evaluation or allocation so both entry points reject the
250/// same inputs with the same variants, and so the walk's unchecked index is
251/// never the first guard on caller-supplied metadata.
252fn validate_search<E>(
253 local_dims: &[usize],
254 init_p: &MultiIndex,
255 max_sweeps: usize,
256 early_stop_tol: f64,
257) -> std::result::Result<(), FloatingZoneError<E>> {
258 if init_p.len() != local_dims.len() {
259 return Err(FloatingZoneError::StartingPointLength {
260 expected: local_dims.len(),
261 actual: init_p.len(),
262 });
263 }
264 for (site, (&dimension, &coordinate)) in local_dims.iter().zip(init_p).enumerate() {
265 if dimension == 0 {
266 return Err(FloatingZoneError::InvalidLocalDimension { site });
267 }
268 if coordinate >= dimension {
269 return Err(FloatingZoneError::StartingCoordinate {
270 site,
271 coordinate,
272 dimension,
273 });
274 }
275 if max_sweeps > 0 {
276 let candidate_bytes = (dimension - 1)
277 .checked_mul(std::mem::size_of::<MultiIndex>())
278 .and_then(|metadata| {
279 init_p
280 .len()
281 .checked_mul(std::mem::size_of::<usize>())
282 .and_then(|coordinates| coordinates.checked_mul(dimension - 1))
283 .and_then(|coordinates| metadata.checked_add(coordinates))
284 });
285 if !candidate_bytes.is_some_and(|bytes| bytes <= isize::MAX as usize) {
286 return Err(FloatingZoneError::AllocationSizeOverflow { site });
287 }
288 }
289 }
290 if early_stop_tol.is_nan() || early_stop_tol < 0.0 {
291 return Err(FloatingZoneError::InvalidTolerance {
292 value: early_stop_tol,
293 });
294 }
295 Ok(())
296}
297
298fn floating_zone_walk_unchecked<E, Err>(
299 local_dims: &[usize],
300 init_p: &MultiIndex,
301 initial_error: f64,
302 max_sweeps: usize,
303 early_stop_tol: f64,
304 mut eval_batch: E,
305) -> std::result::Result<(MultiIndex, f64), Err>
306where
307 E: FnMut(Option<usize>, &[MultiIndex]) -> std::result::Result<Vec<f64>, Err>,
308{
309 let n = local_dims.len();
310 let mut pivot = init_p.clone();
311 let mut max_error = initial_error;
312 let mut pivot_error = max_error;
313
314 for _ in 0..max_sweeps {
315 let prev_max_error = max_error;
316 for ipos in 0..n {
317 // Candidate points: every value at this site except the one the
318 // pivot already holds, the rest fixed at the current pivot
319 // (updated greedily within this sweep). The skipped candidate is
320 // the current pivot itself, whose error is `pivot_error`.
321 let held = pivot[ipos];
322 let mut points = Vec::with_capacity(local_dims[ipos].saturating_sub(1));
323 for value in 0..local_dims[ipos] {
324 if value == held {
325 continue;
326 }
327 let mut point = pivot.clone();
328 point[ipos] = value;
329 points.push(point);
330 }
331 let errors = if points.is_empty() {
332 Vec::new()
333 } else {
334 eval_batch(Some(ipos), &points)?
335 };
336
337 // Fold in value order, with the held candidate's known error in
338 // its own place, so the greedy choice is the one the full batch
339 // would have made.
340 let mut best_local_idx = held;
341 let mut best_local_error = 0.0f64;
342 let mut evaluated = errors.iter();
343 for value in 0..local_dims[ipos] {
344 let error = if value == held {
345 pivot_error
346 } else {
347 match evaluated.next() {
348 Some(&error) => error,
349 None => break,
350 }
351 };
352 if error > best_local_error {
353 best_local_error = error;
354 best_local_idx = value;
355 }
356 }
357 pivot[ipos] = best_local_idx;
358 // The pivot is now the winning candidate of this scan, so its
359 // error is that candidate's error.
360 pivot_error = best_local_error;
361 max_error = max_error.max(best_local_error);
362 }
363
364 if max_error == prev_max_error || max_error > early_stop_tol {
365 break;
366 }
367 }
368
369 Ok((pivot, max_error))
370}
371
372#[cfg(test)]
373mod tests;