Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Partitioned TreeTNs

tensor4all-partitionedtreetn stores TreeTN subdomains as eagerly masked patches. It replaces the retired tensor4all-partitionedtt crate and supports named chains, branched trees, and multiple site indices on one node.

This crate provides partition algebra, TreeTN-general adaptive patching, and adaptive patched interpolation of a function through any tree interpolation engine. It does not implement an engine itself; the TreeTCI engine lives in tensor4all-treetci.

Construct an eager patch

Projectors use zero-based coordinates and full index identity. Construction retains every site axis but masks values outside the selected coordinates:

use tensor4all_core::{DynIndex, IdxTensor};
use tensor4all_partitionedtreetn::{Projector, SubDomainTreeTN};
use tensor4all_treetn::TreeTN;
fn main() -> Result<(), Box<dyn std::error::Error>> {
let site = DynIndex::new_dyn(2);
let tensor = IdxTensor::from_dense(
    vec![site.clone()],
    vec![3.0_f64, 1.0e12],
)?;
let tree = TreeTN::from_tensors(vec![tensor], vec!["root".to_string()])?;
let patch = SubDomainTreeTN::new(
    tree,
    Projector::from_pairs([(site.clone(), 0)])?,
)?;

let node = patch.data().node_index(&"root".to_string()).ok_or("missing root")?;
assert_eq!(patch.data().tensor(node).ok_or("missing tensor")?.to_vec::<f64>()?,
           vec![3.0, 0.0]);
assert!((patch.norm_squared()? - 9.0).abs() < 1.0e-12);
Ok(())
}

Norms, inner products, contraction, truncation, and summation use this stored masked value directly. No projector is re-applied and no full network is densified.

PartitionedTreeTN::evaluate_batched(&indices, values) evaluates a partition at many points, with the same indices and column-major values layout as TreeTN::evaluate. Each point is evaluated by the one patch whose projector it satisfies, found by a hash lookup, and a point that no patch covers is zero.

Adaptive patching

Every truncating or contracting operation takes an explicit existing node name as its center. PatchingOptions::cutoff is a non-negative dimensionless discarded-weight budget shared across patches, not an SVD truncation-policy knob, and PatchingOptions::allocation selects how it is spread. BudgetAllocation::Volume (the default, arXiv:2602.22372) assigns the absolute local threshold cutoff * ||F||^2 * volume_p / total_volume, applies each whole threshold at the patch’s local SVD truncations, and drops a patch whose squared norm is at most its threshold. Splitting is project-first: a patch whose budget-truncated probe is still above the bond cap is split, and its children are projections of the exact patch, so the threshold and the cap are spent once, on the final leaves. BudgetAllocation::Norm instead applies the relative squared tail-sum cutoff cutoff at every local SVD — the same rule as an ITensor-style relative cutoff in TreeTN::truncate — so each patch is accurate relative to itself, no patch is dropped, and projected children inherit no absolute budget. The same choice applies to add_with_patching, contract_adaptive, and truncate_adaptive. cutoff is best effort for the final whole-network error; max_bond_dim is a hard cap.

When several patches are summed exactly (contributions to one output projector in contract and contract_adaptive, inputs with an equal key in add_with_patching, and all patches in to_treetn), the sum is built with a SumEngine. PatchingOptions::sum_engine and PartitionedContractionOptions::sum_engine default to SumEngine::Binary, which adds the patches one by one. SumEngine::Balanced makes the same adds on a balanced tree over the patches, ceil(log2 N) levels deep: same sum, about N^2 instead of N^3 time, and one level of partial sums in memory instead of a single accumulator. SumEngine::Nary builds each sum in one pass, which is much faster when many patches meet in one sum, and SumEngine::NaryWithin { limit_bytes } does so only while the estimated size of the summed network fits the limit.

Whatever the engine, contract, contract_selected, contract_adaptive and add_with_patching return PartitionedTreeTNError::GroupSumLimit before forming a sum whose estimated size (TreeTN::estimate_exact_sum_bytes) exceeds group_sum_limit_bytes. For contract and contract_selected the field is on PartitionedContractionOptions; the adaptive routines use PatchingOptions. Both default to DEFAULT_GROUP_SUM_LIMIT_BYTES (4 GiB) and accept usize::MAX to disable the limit. Groups of one contribution pass without a check. contract, contract_selected and add_with_patching check every group before building any sum. The limit applies to the built sum. Peak memory also includes contributions already held and the workspace used to build and truncate the sum, up to about 5 times the limit for one group; the documentation of DEFAULT_GROUP_SUM_LIMIT_BYTES gives the measurements. A NaryWithin limit at or above group_sum_limit_bytes acts as Nary, since every larger sum is refused. An operator that mixes every value of the indices the patches fix, such as a Fourier transform on patches of the transformed variable, puts every pair of contract_adaptive into one group; apply it with reconstruction::schedule_merge_refine or the patched Fourier transform instead. to_treetn_with(engine) reports which method ran and the size estimate. Inputs that share an equal projector key are summed before patching.

To apply a LinearOperator that acts on part of the tree with contract_adaptive, first write it on the state’s whole tree with LinearOperator::to_state_network(state.site_index_network()). The result is a TreeTN with the state’s nodes and edges, identities where the operator does not act, and one scalar type, so SubDomainTreeTN::from_treetn and PartitionedTreeTN::from_subdomain turn it into the left operand. Its output legs are fresh copies of the state’s site indices; outputs() pairs each with the declared index, so the result can be renamed back afterwards.

The treetn crate also offers the same pairwise reduction with a truncation after every add, TreeTN::pairwise_sum(terms, PairwiseSumOrder::{Sequential, Balanced}, Option<PerAddCutoff>), in place of one exact sum followed by one truncation. PerAddCutoff::cutoff is a per-add bound, not an end-to-end one: with N terms it accumulates over N - 1 adds (ceil(log2 N) for the balanced tree), so the end-to-end error is best effort, and reaching a target relative error eps with the chain takes a per-add squared cutoff of about eps / ((N - 1)^2 kappa^2) with kappa the largest partial-sum norm over the result norm.

It pays while the summands compress, so that the rank kept along the way stays well below the bond N * D that one exact sum builds. Measured on chains of 12 sites, bond D = 10, one core, single runs, at equal error: 2.4x less time at N = 64 on the smooth and mixed families, and at N = 256 51x less time and about 225x less peak memory. Where the summands do not compress, the per-add cutoff discards weight that the one-shot truncation keeps, so the exact sum stays the accurate choice. The per-add truncation is therefore opt-in; the sum engine section of docs/design/partitioned-treetn.md carries the measurement conditions and the full table.

For a cheap seed followed by variational refinement, use TreeTN::pairwise_sum_fit(&terms, order, per_add, FitOptions::new(1)). The pairwise cutoff and cap control only the seed; fit options independently control the sweeps over all original summands. Give the fit a larger bond cap or an SVD policy to grow beyond the seed. The result contains network and truncations, with the absolute discarded norm for each two-node update. These local losses are relative to the untruncated local projection, not an accuracy certificate against the exact sum. Zero sweeps return the seed. fit_sum_with_report(&terms, &seed, &center, options) accepts a seed built elsewhere. TreeTN::density_matrix_sum(&refs, &center, cutoff, max_bond_dim) builds such a seed from all terms at once, with exact cross-term environments and a density eigenvalue-tail cutoff. It returns network and discarded_weight, an absolute squared error estimate in exact arithmetic. Without a binding cap its relative error is bounded by sqrt((R - 1) * cutoff), apart from roundoff. Forming density matrices loses accuracy near machine precision; cancellation can weaken the estimate. Pair environments cost quadratic memory and work in the number of terms; this method can be slower than an exact N-ary sum at small input bonds.

Fitting retains an environment for each target, so a smaller seed does not guarantee lower peak memory or time than exact-then-truncate. The pairwise-fit rustdoc states the chain storage costs and the tested R=12, N=64 accuracy comparison. Exact SumEngine options in partitioned operations are unchanged.

use tensor4all_core::{DynIndex, IdxTensor};
use tensor4all_partitionedtreetn::{
    add_with_patching, BudgetAllocation, PatchSplitStrategy, PatchingOptions, SubDomainTreeTN,
};
use tensor4all_treetn::{SumEngine, TreeTN};
fn main() -> Result<(), Box<dyn std::error::Error>> {
let site0 = DynIndex::new_dyn(2);
let bond = DynIndex::new_dyn(2);
let site1 = DynIndex::new_dyn(2);
let left = IdxTensor::from_dense(
    vec![site0.clone(), bond.clone()],
    vec![1.0_f64, 0.0, 0.0, 1.0],
)?;
let right = IdxTensor::from_dense(
    vec![bond, site1],
    vec![1.0_f64, 0.0, 0.0, 1.0],
)?;
let patch = SubDomainTreeTN::from_treetn(
    TreeTN::from_tensors(vec![left, right], vec![0usize, 1])?,
)?;
let result = add_with_patching(
    vec![patch],
    &0,
    &PatchingOptions {
        cutoff: 0.0,
        allocation: BudgetAllocation::Volume,
        max_bond_dim: Some(1),
        patch_order: vec![site0],
        split_strategy: PatchSplitStrategy::Sequential,
        sum_engine: SumEngine::Binary,
        group_sum_limit_bytes: tensor4all_partitionedtreetn::DEFAULT_GROUP_SUM_LIMIT_BYTES,
    },
)?;

assert_eq!(result.len(), 2);
assert!(result.values().all(|patch| patch.max_bond_dim() <= 1));
Ok(())
}

PatchSplitStrategy::Sequential follows patch_order. The default ExactParameterGain forms and budget-truncates every candidate’s children, then compares checked sums of logical local tensor element counts. Structured storage payload length and AD state are not used as the metric.

Contracting selected outputs

PartitionedTreeTN::contract contracts every compatible patch pair and returns every output projector. When only some outputs are needed, such as a few blocks of a block product over a branch-like index, PartitionedTreeTN::contract_selected takes the wanted output projectors and skips every pair whose output projector is not among them, so its cost follows the pairs of the wanted outputs. Each returned patch equals the one contract returns under the same key when both operate on the same patch pairs, because contract_selected never refines the operands. contract_adaptive_selected is the adaptive counterpart. Its Volume budget uses the norm and volume totals of the selected outputs, so a wanted block can be truncated, or dropped, differently from the same block in a call over all outputs.

Different patch layouts

add and contract accept operands whose patch layouts differ. PartitionedTreeTN::common_refinement returns the disjoint atoms every operand’s patch projectors are unions of, and PartitionedTreeTN::refine_to projects a partition onto a layout, keeping every value that layout covers, and dropping a region that no layout projector covers. add refines both operands onto the common refinement, so each operand keeps the part of its region that the other does not cover. contract refines both operands only when two predicted output projectors would overlap without being equal, and then on the uncontracted indices that the input patches fix, so any two outputs are equal or disjoint. Equal or disjoint layouts take the old path and are unchanged. add_truncated refines like add. This automatic refinement is limited to AUTOMATIC_REFINEMENT_LIMIT atoms; a larger one returns PartitionedTreeTNError::RefinementTooLarge before anything is refined, and callers who need it call common_refinement and refine_to explicitly, which are not limited. contract_selected and add_with_patching do not refine.

contract_adaptive and contract_adaptive_selected group compatible pairs by their predicted output projector before contracting anything. When two predicted output projectors overlap without being equal, the pairs are refined onto a disjoint grid of the fixed output indices, under the same AUTOMATIC_REFINEMENT_LIMIT; here the limit applies to the whole candidate output grid, which is more conservative than contract’s per-operand count. Before this refinement, overlapping output projectors made contract_adaptive return PartitionedTreeTNError::OverlappingProjectors; such inputs are now accepted, and a candidate grid above the limit returns RefinementTooLarge. contract_adaptive_selected selects by the original pair output keys first, so a returned key can be a refinement of a wanted key, and a pair whose key overlaps a wanted key without being equal to it is not formed. With a bond-dimension cap and PatchSplitStrategy::Sequential, a group that has a split candidate stops at its first contribution whose bond dimension reaches the cap and is recomputed on projected children; the remaining pairs of that group are not contracted. For layouts accepted before, the resulting partition layout and values are unchanged.

Adaptive patched interpolation

adaptive_interpolation::patched_interpolate interpolates a function on an arbitrary named tree directly into a partition. It runs an engine implementing tensor4all_treetn::interpolation::TreeInterpolator, such as tensor4all_treetci::TreeTciInterpolator, on the whole domain. A patch that cannot be accepted is split: the next unfixed site of patch_order is fixed and every child is interpolated in turn. For quantics grids, list the most significant bits first.

The evaluator receives a column-major [n_sites, n_points] batch of zero-based full-domain points in the derived site order (nodes in ascending name order, each node’s sites in the given order) and the run’s EvalContext. Every numerical stage of the run - the engine, re-embedding, measurement, and the norm readout - runs on the engine behind that context; nothing enters the process-global session, so a run completes on the engine you pass in (for example one lane’s engine) and needs no process-global warm-up. The returned partition and report are published as compact host storage and stay usable after the session closes. Each patch caches its samples and hands them to its children, so no point is evaluated twice, and a patch with at most one unfixed site is evaluated exactly without the engine.

The driver has three entries that share one wave loop over the BFS generations of the patch queue. patched_interpolate runs every patch on the caller’s session, one after another. adaptive_interpolation::patched_interpolate_on_lanes fans each wave out over the lanes of a caller-owned hataori_tenferro::TenferroLanes, so every patch runs in the child session of the lane that pulled it; the root wave and waves smaller than the lane count run one patch at a time, so a single item keeps the backend’s whole team. adaptive_interpolation::patched_interpolate_mpi (feature hataori-mpi or hataori-mpi-rsmpi-rt) distributes each wave over MPI ranks through hataori::pmap_lanes, with the root owning the queue and the result. The schedule does not change the report: seeds come from the seed and the patch path, counters are per patch, and the wave merge is in canonical path order.

The accuracy requirement is an ErrorNorm with an ErrorTolerance { rtol, atol }. The default, ErrorNorm::L2, bounds the L2 error over the whole domain by delta = max(atol, rtol * S), where S is an L2 norm of the function, usually given as L2Reference::Given(S). The driver measures every accepted and zero patch itself.

use std::collections::BTreeMap;
use tensor4all_core::{ColMajorArray, ColMajorArrayRef, DynIndex, IdxTensor};
use tensor4all_partitionedtreetn::adaptive_interpolation::{
    patched_interpolate, GlobalL2Error, PatchedInterpolationOptions,
};
use tensor4all_partitionedtreetn::{ErrorNorm, ErrorTolerance, L2Reference};
use tensor4all_tensorbackend::{explicit::Session, CpuBackend};
use tensor4all_treetci::TreeTciInterpolator;
use tensor4all_treetn::interpolation::{EvalContext, Parallelism};
use tensor4all_treetn::NodeNameNetwork;
fn main() -> Result<(), Box<dyn std::error::Error>> {
// A junction "c" of degree three without a site, and three leaves.
let (x, y, z) = (DynIndex::new_dyn(2), DynIndex::new_dyn(3), DynIndex::new_dyn(3));
let mut topology = NodeNameNetwork::new();
for node in ["c", "x", "y", "z"] {
    topology.add_node(node.to_string())?;
}
for leaf in ["x", "y", "z"] {
    topology.add_edge(&"c".to_string(), &leaf.to_string())?;
}
let node_sites = BTreeMap::from([
    ("c".to_string(), vec![]),
    ("x".to_string(), vec![x.clone()]),
    ("y".to_string(), vec![y.clone()]),
    ("z".to_string(), vec![z.clone()]),
]);

// Site order [x, y, z]. f vanishes for x = 0 and has rank three otherwise.
let f = |p: &[usize]| (p[0] * (1 + p[1] + p[2]).pow(2)) as f64;
let values: Vec<f64> = (0..18).map(|k| f(&[k % 2, (k / 2) % 3, k / 6])).collect();
let norm = values.iter().map(|v| v * v).sum::<f64>().sqrt();
let options = PatchedInterpolationOptions::new(3)
    .with_error_norm(ErrorNorm::l2(L2Reference::Given(norm)))
    .with_tolerance(ErrorTolerance { rtol: 1e-10, atol: 0.0 })
    .with_patch_order(vec![x.clone(), y.clone()]);
let mut backend = CpuBackend::with_threads(1)?;
let mut ctx = EvalContext::new(Session::new(backend.engine_mut()), Parallelism::Serial);
let result = patched_interpolate(
    &TreeTciInterpolator::default(),
    topology,
    node_sites,
    ColMajorArray::new(vec![1, 2, 2], vec![3, 1]).expect("2D pivots"),
    &mut ctx,
    |batch: ColMajorArrayRef<'_, usize>,
     _ctx: &mut EvalContext<'_>|
     -> anyhow::Result<Vec<f64>> { Ok(batch.data().chunks(3).map(f).collect()) },
    &options,
)?;

// The x = 0 half is a measured zero patch; the rest is split at y.
assert_eq!(result.report.zero_patches.len(), 1);
assert_eq!(result.partition.len(), 3);
// Every patch was measured exhaustively: the global error is certified.
let error = result.report.norm.l2_error().unwrap();
assert!(matches!(error.global, GlobalL2Error::Certified { .. }));

let reference = IdxTensor::from_dense(vec![x, y, z], values)?;
let dense = result.partition.to_treetn()?.contract_to_tensor()?;
assert!(dense.sub(&reference)?.norm()? <= result.report.norm.delta().unwrap() + 1e-12 * norm);
Ok(())
}

Under ErrorNorm::L2 the allowance is split by patch volume: every accepted or zero patch must have a root-mean-square residual of at most tau = delta / sqrt(|X|), which is also the engine’s absolute tolerance. A patch with at most max(max_exhaustive_points, samples) points (see VerificationOptions) is measured at every point; a larger patch is estimated by VerificationOptions::estimator, followed by an independent audit with the same estimator. The default L2Estimator::ResidualTt interpolates the residual f - f~ with the same engine, starting from the largest residuals of a small uniform seed sample and from the patch corners and edges (grouped by with_variables), and uses the exact norm of that residual TT; its bond cap is max(ceil(chi_patch * residual_bond_ratio), residual_bond_floor), and a run that reaches the cap falls back to the larger of the residual norm and the seed sample’s RMS. L2Estimator::UniformMonteCarlo reproduces the M3 uniform sample. The report’s residual_evaluations and residual_saturations count the residual runs and the patches whose residual run reached its cap. A failed measurement of a converged run reruns the engine with the worst measured points (and the residual run’s nonzero pivots) added to its pivots, then splits the patch. What a run can claim is the report’s GlobalL2Error:

  • Certified: every contribution is exact or exhaustive, and the absolute error is at most delta up to a small relative margin and a rounding term from a calibrated, not proven, model (rounding_limited says when that term is not below tau); relative_error_bound bounds E / ||f|| when ||f~|| exceeds E.
  • Audited: some contribution is non-exact, and every such one was audited. It is an estimate with a standard error, never a bound and not a guarantee. Under L2Estimator::UniformMonteCarlo the audited mean square is unbiased (its square root is not), but a residual concentrated on unsampled points is missed by the acceptance sample and the audit alike, and the standard error, computed from the same points, does not reveal it. A localized feature that enters a patch only through a corner or an edge is such a case; the audited error can then be orders of magnitude too small. More samples make a miss less likely but do not exclude it. The opt-in with_cache_candidates(true) (child patches also start from the largest values the parent already evaluated in them) can prevent a miss where the parent sampled the feature, but not one where the parent never sampled it or where the engine saw the feature without resolving it and the acceptance sample misses the residual. L2Estimator::ResidualTt, the default, starts from the patch corners and edges and does not rely on uniform points alone, but its capped residual TT is still an estimate.
  • AcceptanceOnly: audits were disabled. The combined acceptance statistics are neither a bound nor an estimate.
  • ToleranceNotMet: some patch was retained by the minimum patch size without meeting its allowance (below). It takes precedence over the other three, is never certified, and its basis says which of them describes its measured value; an exact or exhaustive basis still bounds the error.

Patch-size bounds

Two options bound the patch size in generalized bits: every unfixed site of a patch counts as one bit, whatever its dimension, so a fused quantics site of dimension 4 is one bit.

  • with_min_patch_bits(m) stops splitting where the children would have fewer than m bits. Such a patch is retained with its last engine run and recorded as PatchStatus::WithinTolerance or PatchStatus::ToleranceNotMet; report.tolerance_met() says whether every patch met its allowance, and the error of a run with a ToleranceNotMet patch can exceed delta without limit.
  • with_capped_patches(CappedPatches::AcceptUpTo { bits }) accepts a patch that reaches the bond cap when it has at most bits unfixed sites and passes its error check. Larger capped patches still split, and a patch that converges below the cap is never split for its size. The bound must be at least the minimum.

By default neither applies, and the driver may split down to exact patches in the worst case. On binary layouts, a capped bound of at most log2(max(max_exhaustive_points, samples)) bits keeps every capped acceptance exhaustively measured.

use std::collections::BTreeMap;
use tensor4all_core::{ColMajorArray, ColMajorArrayRef, DynIndex, IdxTensor};
use tensor4all_partitionedtreetn::adaptive_interpolation::{
    patched_interpolate, GlobalL2Error, PatchStatus, PatchedInterpolationOptions,
    ToleranceNotMetBasis,
};
use tensor4all_partitionedtreetn::{ErrorNorm, ErrorTolerance, L2Reference};
use tensor4all_tensorbackend::{explicit::Session, CpuBackend};
use tensor4all_treetci::TreeTciInterpolator;
use tensor4all_treetn::interpolation::{EvalContext, Parallelism};
use tensor4all_treetn::NodeNameNetwork;
fn main() -> Result<(), Box<dyn std::error::Error>> {
// f(x, y) = 1 + [x == y] on two sites of dimension 3 has rank three, which
// a cap of two cannot represent. A minimum of two bits retains the root.
let (x, y) = (DynIndex::new_dyn(3), DynIndex::new_dyn(3));
let mut topology = NodeNameNetwork::new();
topology.add_node(0usize)?;
topology.add_node(1usize)?;
topology.add_edge(&0, &1)?;
let node_sites = BTreeMap::from([(0usize, vec![x.clone()]), (1, vec![y.clone()])]);
let f = |p: &[usize]| if p[0] == p[1] { 2.0 } else { 1.0 };
let values: Vec<f64> = (0..9).map(|k| f(&[k % 3, k / 3])).collect();
let norm = values.iter().map(|v| v * v).sum::<f64>().sqrt();
let options = PatchedInterpolationOptions::new(2)
    .with_error_norm(ErrorNorm::l2(L2Reference::Given(norm)))
    .with_tolerance(ErrorTolerance { rtol: 1e-10, atol: 0.0 })
    .with_min_patch_bits(2);
let mut backend = CpuBackend::with_threads(1)?;
let mut ctx = EvalContext::new(Session::new(backend.engine_mut()), Parallelism::Serial);
let result = patched_interpolate(
    &TreeTciInterpolator::default(),
    topology,
    node_sites,
    ColMajorArray::new(vec![0, 0], vec![2, 1]).expect("2D pivots"),
    &mut ctx,
    |batch: ColMajorArrayRef<'_, usize>,
     _ctx: &mut EvalContext<'_>|
     -> anyhow::Result<Vec<f64>> { Ok(batch.data().chunks(2).map(f).collect()) },
    &options,
)?;

assert_eq!(result.report.splits, 0);
assert_eq!(result.report.accepted[0].status, PatchStatus::ToleranceNotMet);
assert!(!result.report.tolerance_met());
let error = result.report.norm.l2_error().unwrap();
let GlobalL2Error::ToleranceNotMet { measured_rms, basis, .. } = &error.global else {
    panic!("expected ToleranceNotMet");
};
// The nine points were measured exhaustively, so the measured error is the
// dense one.
assert!(matches!(basis, ToleranceNotMetBasis::ExactOrExhaustive { .. }));
let reference = IdxTensor::from_dense(vec![x, y], values)?;
let dense = result.partition.to_treetn()?.contract_to_tensor()?;
let residual_rms = dense.sub(&reference)?.norm()? / 3.0;
assert!((measured_rms - residual_rms).abs() <= 1e-12 * norm);
Ok(())
}

The reference norm defaults to L2Reference::Required, which fails before any evaluation unless rtol = 0 (use atol alone) or the root has at most one site (the reference is then exact). L2Reference::MonteCarlo estimates it from uniform root samples; the estimate is heavy-tailed for localized functions and can make the allowance looser than requested. With a tiny or zero tolerance the driver may split down to exact patches, so set max_patches.

ErrorNorm::sampled_max() keeps the M2 criterion: the engine’s sampled error estimate against max(atol, rtol * max_reference), where max_reference is a function value (sampled_max_with_reference(max_abs), or the largest root sample). It runs no measurement, is neither a certified bound nor a measured error, and makes no L2 claim. Under every norm, a patch whose candidate samples are all exactly zero is first screened (and under L2 measured); zero patches are reported in report.zero_patches and left out of the partition, which treats an absent patch as zero.

Execution is sequential. For a fixed seed, a deterministic evaluator, and a deterministic engine, the report and every stored node tensor (values and positional axis order) are identical across runs on fresh threads within one process as long as the measured network values are reproducible. This is tested for f64 on trees with exactly one site per node. On trees with a site-free node or a node with several sites, or with f32/c32 data, the cached evaluator can round differently between threads and processes, an open limitation tracked in tenferro-rs#1963. Issue #795 closed the tracking/test gap through #816; it did not fix the planner. The intended scope is bitwise identical results on the same machine and build across threads, thread counts, and processes, with no cross-machine promise. Generic-path measurements still need deterministic contraction paths; reproducibility across processes is not claimed until a two-process test passes. Issue #791 was fixed by #793: TreeTN site/edge construction and dense-axis order no longer inherit that hash-iteration nondeterminism. site_space is still a set with unspecified iteration order; cached generic evaluation retains the separate planner limitation above.

Reconstruction with a fixed global L2 tolerance

Use reconstruction::reconstruct when approximation must be measured against one immutable target, rather than the local discarded-weight cutoff used above. ReconstructionTarget::from_partition validates and snapshots disjoint patches and pins their combined L2 norm. ReconstructionTolerance { rtol, atol } sets the fixed allowance max(atol, rtol * reference_scale).

The rank goal is soft: a split must improve rank, and a pairwise merge must reduce the sum of operand ranks. Unprofitable sums remain as superposition terms. The output’s regions are disjoint, but terms within a region can overlap. Use regions() to consume them. into_partition() rejects a region containing multiple terms; it never implicitly sums them.

This example is included directly from the checked executable source:

use tensor4all_core::{DynIndex, IdxTensor};
use tensor4all_partitionedtreetn::{reconstruction::*, PartitionedTreeTN, PatchSplitStrategy, SubDomainTreeTN, TreeTN};
fn main() -> Result<(), Box<dyn std::error::Error>> {
    let x = DynIndex::new_dyn(2);
    let y = DynIndex::new_dyn(2);
    let bond = DynIndex::new_dyn(2);
    // Column-major cores for T(x,y) = delta(x,y).
    let tree = TreeTN::from_tensors(
        vec![
            IdxTensor::from_dense(vec![x.clone(), bond.clone()], vec![1.0, 0.0, 0.0, 1.0])?,
            IdxTensor::from_dense(vec![bond, y], vec![1.0, 0.0, 0.0, 1.0])?,
        ],
        vec![0usize, 1],
    )?;
    let reference = tree.clone().to_dense()?; // Small reference example only.
    let partition = PartitionedTreeTN::from_subdomain(SubDomainTreeTN::from_treetn(tree)?)?;
    let target = ReconstructionTarget::from_partition(&partition)?;
    let output = reconstruct(
        &target,
        &0,
        ReconstructionTolerance {
            rtol: 1e-8,
            atol: 0.0,
        },
        &ReconstructionOptions {
            target_bond_dim: Some(1),
            patch_order: vec![x],
            split_strategy: PatchSplitStrategy::Sequential,
            ..Default::default()
        },
    )?;
    assert!((output.report().reference_scale - 2.0_f64.sqrt()).abs() < 1e-12);
    assert_eq!(output.report().region_count, 2);
    assert_eq!(output.report().max_bond_dim, 1);
    assert!(output.report().error_bound <= output.report().absolute_tolerance);
    // Conversion succeeds because each region has one retained term.
    let reconstructed = output.into_partition()?.to_treetn()?.to_dense()?;
    assert!(reconstructed.sub(&reference)?.maxabs()? < 1e-12);
Ok(())
}

ReconstructionTarget::from_tensor_products accepts pairs of patches on the same named topology and independent site spaces. Their output node owns both factors’ external indices. Each product norm is the product of its factor norms; orthogonal product-patch norm squares are then added. Products remain factorized until reconstruction begins. This is a tensor product, not an elementwise product or an induced operator norm.

Each accepted compression is checked against its uncompressed local input by an explicit difference-network norm. Residuals add within a region and combine in quadrature across disjoint regions. The report is a numerical a posteriori bound; it excludes floating-point roundoff. rtol = atol = 0 disables approximate compression. Reaching max_regions retains higher rank without relaxing the error allowance. A partial patch_order list constrains the search independently of any future QFT-selected index subset.

Reconstruction reuses PatchSplitStrategy. Sequential tries only the first unprojected nontrivial index in patch_order and stops that region on no gain or insufficient region capacity, without trying later indices. The default ExactParameterGain compares all permitted candidates by logical parameter count. For contiguous QTT intervals, supply the bits MSB first and select Sequential, even when the TT stores those bits in reverse order. An empty order uses all external indices in deterministic identity order, not numeric bit significance.

Applying a QFT to a subset of sites

ReconstructionTarget::from_subset_operator(&preimage, &center, &operator, &selection, &options) prepares the images of an existing linear operator acting on an ordered subset of the target’s site indices. selection holds one full site index per operator node, in the operator’s own node order; for a quantics Fourier transform its node 0 is the most significant input bit. Build that operator with tensor4all_quanticstransform::quantics_fourier_operator and the crate stays free of a simplett-stack runtime dependency.

The selection may skip sites and spectators keep their identity, dimension, and node assignment. A spectator may share its node with a selected index. Several selected indices may share one node as well: the operator MPO nodes carrying them are fused into one multi-site node, which is exact and keeps the preimage node name. Only a group whose operator nodes are threaded through another owner’s node cannot be fused locally, and that selection is rejected with repair guidance.

The transformed output norm is never measured. SubsetOperatorOptions::unitary selects the amplification factor: false (default) uses the selected-space operator’s Frobenius norm, an upper bound on its induced amplification; true is a caller guarantee that the operator preserves the L2 norm, giving factor one. The preimage’s reference scale is multiplied by that factor, so successive applications propagate the scale instead of recomputing an output norm. For a general operator rtol is therefore relative to that scale, not to the actual ||A x||_2; pass unitary = true for a Fourier transform, whose construction error is accounted separately from the reconstruction bound.

The operator is applied exactly and the images stay separate, so a global direct sum is never formed.

The transform stores frequency bit t at selected position t without an output bit-reversal permutation. For contiguous output patches, supply patch_order = [r1, ..., rR] with PatchSplitStrategy::Sequential.

Level-coupled merge-refine scheduling

reconstruction::schedule_merge_refine(&preimage, &center, &operator, &selection, &subset, tolerance, &MergeRefineOptions) instead runs the complementary input-merge/output-refine trajectory of the patched Fourier algorithm. The preimage must already be the dyadic input leaves of the d selected binary indices. Different spectator constraints are supported: already disjoint groups are kept directly, while overlapping groups use a common grid of their varying spectator indices. The grid and refined leaf count are checked against work and term limits before tensor operations. Each leaf fixes a contiguous prefix of the selected indices; complete selected coverage is checked in each represented spectator cell, or omitted assignments contribute exact zero under CoverageContract::ZeroForMissingLeaves. Level zero applies the complete transform once per original patch, then restricts its image to the spectator cells without repeating application or its error charge. Level t merges the input siblings by removing the constraint on k_(d-t+1) and refines the output by fixing r_t, restricting every contribution to its output region before adding it, so no sum over the whole output domain is ever assembled and each computed object is reused by its descendants.

MergeRefineOptions::output_depth stops after that many levels; None (the default) refines every selected bit. MergeRefineOptions::coordinate_groups supplies several coordinate axes explicitly: each CoordinateGroup gives that axis’ selected indices in input order and, separately, in output order, and one level advances every refining, non-exhausted axis by one bit, so a two-axis level combines four input children and, without a rank goal, produces four output children. The default None treats selection as one axis with the documented reversed placement. MergeRefineOptions::target_bond_dim is a soft rank goal: None keeps the trajectory uniform and exact, while Some(goal) makes it adaptive and decides each axis of a region on its own. An output region is then merged without splitting first and stops on every axis as soon as that candidate fits the goal; for a candidate above the goal, an axis is refined only when that axis’ children store no more parameters in total than the candidate they replace, because a split keeps one region per output child and a projected child still keeps every output site axis, so a rank drop by one is not a gain. A level therefore splits into 2^(refining axes) children instead of 2^(coordinate axes); a stopped axis keeps the region’s shorter prefix for good while its other axes keep refining. A region whose axes have all stopped keeps its output key and still merges its input siblings on every later level, so it consolidates the input prefixes it held instead of freezing them. A merged pair is combined into one term when it fits the goal or lowers the bond dimension (otherwise both operands stay as separate terms of the region’s superposition), and every truncation candidate must fit the item’s share of the global allowance. An unaffordable or gainless candidate is retained exactly rather than violating the accuracy contract, and exceeding MergeRefineOptions::max_terms returns a resource-limit error.

MergeRefineOptions::application opts into a truncating operator application, and the choice is explicit because the charged error means different things. With OperatorApplication::Measured(options) the schedule applies the operator with those options and exactly, measures each leaf’s deviation, and charges that sum before any scheduling compression, so an approximate application is never a silent error; a measured application error already above the allowance is rejected. OperatorApplication::certified(share) is for images too large to form exactly: on a chain state each leaf is applied by apply_linear_operator_certified with an equal part of share times the allowance, and the proved bounds are charged instead. Every other entry point applies exactly. MergeRefineReport records the schedule shape (level_count, applied_operator_count, additions, projections, compression_attempts, compressions, work_items_per_level, peak_work_items, refined_regions, stopped_regions) next to the pinned reference scale, the allowance, and the measured error_bound. Every measured component — an application error, a truncation residual, or a dropped norm — is recorded once, at the level and region where it was measured: components of one level live in disjoint regions and combine by the Euclidean norm, while components of different levels can be nested and add by the triangle inequality. The bound therefore never exceeds the allowance and does not grow with the number of refined regions. It excludes operator-construction error and any error of a caller-approximated operator outside the charged application deviation. Per-input-branch refinement depths with lazy reconciliation and benchmark evidence in the intended patched-input regime remain follow-up work. The transform is never padded and its length never changes: the operator’s input and output are the same selected indices.

use std::collections::HashMap;
use tensor4all_core::{DynIndex, IdxTensor};
use tensor4all_partitionedtreetn::{reconstruction::*, PartitionedTreeTN, Projector, SubDomainTreeTN, TreeTN};
use tensor4all_treetn::{IndexMapping, LinearOperator};
fn main() -> Result<(), Box<dyn std::error::Error>> {
    let site = DynIndex::new_dyn(2);
    let tree = TreeTN::from_tensors(
        vec![IdxTensor::from_dense(vec![site.clone()], vec![3.0, 4.0])?],
        vec![0usize],
    )?;
    // The schedule consumes the 2^d dyadic input leaves of the selected sites.
    let full = SubDomainTreeTN::from_treetn(tree)?;
    let leaves = (0..2)
        .map(
            |value| -> Result<SubDomainTreeTN, Box<dyn std::error::Error>> {
                let projector = Projector::from_pairs([(site.clone(), value)])?;
                full.project(&projector)?.ok_or_else(|| "zero leaf".into())
            },
        )
        .collect::<Result<Vec<_>, _>>()?;
    let preimage =
        ReconstructionTarget::from_partition(&PartitionedTreeTN::from_subdomains(leaves)?)?;

    // A normalized Hadamard transform written as a one-node MPO.
    let (internal_input, internal_output) = (DynIndex::new_dyn(2), DynIndex::new_dyn(2));
    let scale = 1.0 / 2.0_f64.sqrt();
    let mpo = TreeTN::from_tensors(
        vec![IdxTensor::from_dense(
            vec![internal_input.clone(), internal_output.clone()],
            vec![scale, scale, scale, -scale],
        )?],
        vec![0usize],
    )?;
    let mut input_mapping = HashMap::new();
    input_mapping.insert(
        0usize,
        IndexMapping {
            true_index: site.clone(),
            internal_index: internal_input,
        },
    );
    let mut output_mapping = HashMap::new();
    output_mapping.insert(
        0usize,
        IndexMapping {
            true_index: site.clone(),
            internal_index: internal_output,
        },
    );

    let result = schedule_merge_refine(
        &preimage,
        &0,
        &LinearOperator::new(mpo, input_mapping, output_mapping),
        std::slice::from_ref(&site),
        &SubsetOperatorOptions { unitary: true },
        ReconstructionTolerance {
            rtol: 1e-12,
            atol: 0.0,
        },
        &MergeRefineOptions::default(),
    )?;

    // One complete transform per input leaf, one level, one addition per child.
    let report = result.report();
    assert_eq!(report.applied_operator_count, 2);
    assert_eq!(report.additions, 2);
    assert_eq!(report.work_items_per_level, vec![2, 2]);
    assert!((report.reference_scale - 5.0).abs() < 1e-12);

    // The fully refined result is one patch per output coordinate.
    let partition = result.into_partition()?;
    let region = |value: usize| -> Result<f64, Box<dyn std::error::Error>> {
        let patch = partition
            .values()
            .find(|patch| patch.projector().get(&site) == Some(value))
            .ok_or("missing output region")?;
        Ok(patch.norm()?)
    };
    assert!((region(0)? - 7.0 / 2.0_f64.sqrt()).abs() < 1e-12);
    assert!((region(1)? - 1.0 / 2.0_f64.sqrt()).abs() < 1e-12);
Ok(())
}

Dtype and topology

A partition is homogeneous: all patches must use the same IdxTensor scalar dtype and the same named topology and site-index assignment. Both f64 and Complex64 are supported. Topology is not restricted to a chain; a TreeTN with a central named node and three named leaves is a valid partition input. See the Tree Tensor Networks guide for constructing branched networks and selecting contraction/truncation options.

Migration from tensor4all-partitionedtt

The retired tensor4all-partitionedtt crate (removed in #915 D3, settling #825) worked on the positional SimpleTensorTrain representation. This crate carries the same partition algebra on named TreeTN values:

tensor4all-partitionedtttensor4all-partitionedtreetn
PartitionedTTPartitionedTreeTN
SubDomainTT::from_ttSubDomainTreeTN::from_treetn
PatchingOptions { rtol, .. }PatchingOptions { cutoff = rtol², .. }
add_with_patching(subdomains, &options)add_with_patching(subdomains, &center, &options)
truncate_adaptive(&tt, rtol, cap)truncate_adaptive(&partition, &center, cutoff, allocation, cap)
adaptiveinterpolate(...)adaptive_interpolation::patched_interpolate(...)

The adaptive interpolation driver needs an engine that implements TreeInterpolator; tensor4all-treetci::TreeTciInterpolator is the TreeTCI one. benchmarks/rust/benchmark_patching.rs is the ported patching benchmark.

For a Fourier-specific entry point, see Patched QFT on an index subset. Enable quanticstransform’s partitioned feature to derive axis layout and coordinate groups automatically while retaining lazy output regions.