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 2^d dyadic input leaves of the d selected binary indices, sharing identical spectator constraints. 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 and returns a strict partition with one patch per output coordinate. MergeRefineOptions::target_bond_dim is a soft rank goal: None keeps the trajectory exact, while Some(goal) truncates a merged item only toward that goal and only when its measured residual fits the item’s share of the global allowance, so an unaffordable candidate is retained exactly rather than violating the accuracy contract. MergeRefineReport records the schedule shape (level_count, applied_operator_count, additions, projections, compression_attempts, compressions, work_items_per_level, peak_work_items) next to the pinned reference scale, the allowance, and the measured error_bound. The bound adds measured truncation residuals by the triangle inequality within a region and combines disjoint regions by the Euclidean norm, so it never exceeds the allowance; it excludes operator-construction error and the application error of an externally approximated operator. Adaptive refinement with a shared error ledger, nonuniform geometry, and benchmark evidence remain follow-up work, and automatic padding is a separate opt-in domain policy that is never applied silently.

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.