Partitioned TreeTNs

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

This crate provides partition algebra and TreeTN-general adaptive patching. It does not provide adaptive interpolation or TCI.

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.

Adaptive patching

Every truncating or contracting operation takes an explicit existing node name as its center. add_with_patching first assigns absolute local discarded-weight cutoffs proportional to logical patch volume (cutoff * ||F||^2 * volume_p / total_volume), applies each whole threshold at the patch’s local SVD truncations, then splits patches that remain above the bond cap. The cutoff is best effort for the final whole-network error; max_bond_dim is a hard cap. Inputs that share an equal projector key are summed before patching:

use tensor4all_core::{DynIndex, IdxTensor};
use tensor4all_partitionedtreetn::{
    add_with_patching, PatchSplitStrategy, PatchingOptions, SubDomainTreeTN,
};
use tensor4all_treetn::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,
        max_bond_dim: Some(1),
        patch_order: vec![site0],
        split_strategy: PatchSplitStrategy::Sequential,
    },
)?;

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.

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, sharing identical spectator constraints. Each leaf fixes a contiguous prefix of those indices, so leaf depths may differ as long as the leaves form a prefix code; all 2^d coordinate assignments must be covered by default, or a sparse subset with CoverageContract::ZeroForMissingLeaves, where every omitted assignment contributes exactly zero. Level zero applies the complete transform once per leaf. 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, one level advances every non-exhausted axis by one bit, and a two-axis level therefore combines four input children and 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. An output region is then refined only when its retained terms exceed the goal and refining lowers its maximum retained rank, a merged pair is combined into one term only when combining pays off (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::apply_options opts into a truncating operator application. The schedule then 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. 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

Use this crate for new named TreeTN partition work. The old tensor4all-partitionedtt crate remains buildable during migration and receives correctness and security fixes only; no removal date has been set.