Skip to main content

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;