Traced Monoidal

Cartesian and iterative traced monoidal structures, with trace and partial_trace operations.

traced

Traced monoidal categories: feedback and fixpoint.

A traced monoidal category is a symmetric monoidal category (C, ⊗, I) equipped with a trace operator:

Tr^U_{A,B}: C(A ⊗ U, B ⊗ U) → C(A, B)

satisfying naturality, dinaturality, vanishing, superposing, and yanking axioms.

In the V-enriched fuzzy-relation setting, the trace corresponds to a fixpoint computation: given f: A × U → B × U, the trace "feeds back" the U component:

Tr(f)(a, b) = ⋁_u f((a, u), (b, u))

which is the join (existential) over the feedback variable.

For the tropical algebra, this computes shortest-cycle distances. For general algebras, it may require iteration to a fixpoint.

This module provides:

TracedMonoidal (abstract)
├── CartesianTrace   — trace on the cartesian monoidal structure
└── IterativeTrace   — trace via fixpoint iteration

trace()              — apply the trace operator
partial_trace()      — trace over a subset of feedback wires

TracedMonoidal

TracedMonoidal(monoidal: MonoidalStructure, algebra: Algebra | None = None)

Bases: ABC

Abstract traced monoidal category.

Provides the trace operator Tr^U_{A,B} on a monoidal structure.

PARAMETER	DESCRIPTION
monoidal	The underlying monoidal structure. TYPE: MonoidalStructure
algebra	The enrichment algebra. TYPE: Algebra or None DEFAULT: None

Source code in src/quivers/categorical/traced.py

def __init__(
    self,
    monoidal: MonoidalStructure,
    algebra: Algebra | None = None,
) -> None:
    self._monoidal = monoidal
    self._algebra = algebra if algebra is not None else PRODUCT_FUZZY

monoidal property

monoidal: MonoidalStructure

The underlying monoidal structure.

algebra property

algebra: Algebra

The enrichment algebra.

trace abstractmethod

trace(morph: Morphism, feedback: SetObject, domain: SetObject, codomain: SetObject) -> Morphism

Apply the trace operator.

Given f: A ⊗ U → B ⊗ U, compute Tr^U(f): A → B.

PARAMETER	DESCRIPTION
morph	The morphism f: A ⊗ U → B ⊗ U. TYPE: Morphism
feedback	The feedback object U. TYPE: SetObject
domain	The external domain A. TYPE: SetObject
codomain	The external codomain B. TYPE: SetObject

RETURNS	DESCRIPTION
Morphism	The traced morphism Tr^U(f): A → B.

Source code in src/quivers/categorical/traced.py

@abstractmethod
def trace(
    self,
    morph: Morphism,
    feedback: SetObject,
    domain: SetObject,
    codomain: SetObject,
) -> Morphism:
    """Apply the trace operator.

    Given f: A ⊗ U → B ⊗ U, compute Tr^U(f): A → B.

    Parameters
    ----------
    morph : Morphism
        The morphism f: A ⊗ U → B ⊗ U.
    feedback : SetObject
        The feedback object U.
    domain : SetObject
        The external domain A.
    codomain : SetObject
        The external codomain B.

    Returns
    -------
    Morphism
        The traced morphism Tr^U(f): A → B.
    """
    ...

verify_yanking

verify_yanking(feedback: SetObject, atol: float = 1e-05) -> bool

Verify the yanking axiom: Tr^U(σ_{U,U}) = id_U.

The trace of the braiding/swap should be the identity.

PARAMETER	DESCRIPTION
feedback	The object U to test. TYPE: SetObject
atol	Absolute tolerance. TYPE: float DEFAULT: 1e-05

RETURNS	DESCRIPTION
bool	True if yanking holds within tolerance.

Source code in src/quivers/categorical/traced.py

def verify_yanking(
    self,
    feedback: SetObject,
    atol: float = 1e-5,
) -> bool:
    """Verify the yanking axiom: Tr^U(σ_{U,U}) = id_U.

    The trace of the braiding/swap should be the identity.

    Parameters
    ----------
    feedback : SetObject
        The object U to test.
    atol : float
        Absolute tolerance.

    Returns
    -------
    bool
        True if yanking holds within tolerance.
    """
    # σ_{U,U}: U ⊗ U → U ⊗ U (swap)
    if isinstance(self._monoidal, CartesianMonoidal):
        swap = self._monoidal.braiding(feedback, feedback)
        traced = self.trace(swap, feedback, feedback, feedback)
        expected = identity(feedback, algebra=self._algebra).tensor

        return torch.allclose(traced.tensor, expected, atol=atol)

    return True  # skip for non-cartesian

CartesianTrace

CartesianTrace(algebra: Algebra | None = None)

Bases: TracedMonoidal

Trace on the cartesian monoidal structure (FinSet, ×, 1).

For a morphism f: A × U → B × U, the cartesian trace is:

Tr^U(f)(a, b) = ⋁_u f((a, u), (b, u))

This is the join over the feedback dimensions of the tensor's diagonal (where the U components of domain and codomain agree).

PARAMETER	DESCRIPTION
algebra	The enrichment algebra. TYPE: Algebra or None DEFAULT: None

Source code in src/quivers/categorical/traced.py

def __init__(self, algebra: Algebra | None = None) -> None:
    q = algebra if algebra is not None else PRODUCT_FUZZY
    super().__init__(CartesianMonoidal(q), q)

trace

trace(morph: Morphism, feedback: SetObject, domain: SetObject, codomain: SetObject) -> Morphism

Compute the cartesian trace via diagonal extraction and join.

PARAMETER	DESCRIPTION
morph	f: A × U → B × U. TYPE: Morphism
feedback	The feedback object U. TYPE: SetObject
domain	The external domain A. TYPE: SetObject
codomain	The external codomain B. TYPE: SetObject

RETURNS	DESCRIPTION
ObservedMorphism	Tr^U(f): A → B.

Source code in src/quivers/categorical/traced.py

def trace(
    self,
    morph: Morphism,
    feedback: SetObject,
    domain: SetObject,
    codomain: SetObject,
) -> Morphism:
    """Compute the cartesian trace via diagonal extraction and join.

    Parameters
    ----------
    morph : Morphism
        f: A × U → B × U.
    feedback : SetObject
        The feedback object U.
    domain : SetObject
        The external domain A.
    codomain : SetObject
        The external codomain B.

    Returns
    -------
    ObservedMorphism
        Tr^U(f): A → B.
    """
    q = self._algebra
    t = morph.tensor

    # tensor shape: (*a.shape, *u.shape, *b.shape, *u.shape)
    # we need to extract the diagonal over the two U copies
    # and join over U

    # the U dimensions in domain are at positions [n_a, n_a + n_u)
    # the U dimensions in codomain are at positions [n_a + n_u + n_b, n_a + n_u + n_b + n_u)
    result_shape = (*domain.shape, *codomain.shape)
    result = torch.full(result_shape, q.zero)

    # extract diagonal and join over U
    for a_idx in itertools.product(*(range(s) for s in domain.shape)):
        for b_idx in itertools.product(*(range(s) for s in codomain.shape)):
            # collect f(a, u, b, u) for all u
            vals: list[torch.Tensor] = []

            for u_idx in itertools.product(*(range(s) for s in feedback.shape)):
                src_idx = a_idx + u_idx + b_idx + u_idx
                vals.append(t[src_idx].unsqueeze(0))

            if vals:
                stacked = torch.cat(vals)
                result[a_idx + b_idx] = q.join(stacked, dim=0)

    return observed(domain, codomain, result, algebra=q)

IterativeTrace

IterativeTrace(monoidal: MonoidalStructure, algebra: Algebra | None = None, max_iter: int = 100, atol: float = 1e-06)

Bases: TracedMonoidal

Trace via fixpoint iteration.

For algebras where the trace does not have a closed-form expression, this computes the trace by iterating:

x_0 = ⊥
x_{n+1} = f(a, x_n)(b, x_n)  (schematically)

until convergence. This works for continuous algebras on complete lattices (Kleene's fixpoint theorem).

PARAMETER	DESCRIPTION
monoidal	The monoidal structure. TYPE: MonoidalStructure
algebra	The enrichment algebra. TYPE: Algebra or None DEFAULT: None
max_iter	Maximum number of iterations. TYPE: int DEFAULT: 100
atol	Convergence tolerance. TYPE: float DEFAULT: 1e-06

Source code in src/quivers/categorical/traced.py

def __init__(
    self,
    monoidal: MonoidalStructure,
    algebra: Algebra | None = None,
    max_iter: int = 100,
    atol: float = 1e-6,
) -> None:
    super().__init__(monoidal, algebra)
    self._max_iter = max_iter
    self._atol = atol

max_iter property

max_iter: int

Maximum number of fixpoint iterations.

trace

trace(morph: Morphism, feedback: SetObject, domain: SetObject, codomain: SetObject) -> Morphism

Compute the trace via fixpoint iteration.

PARAMETER	DESCRIPTION
morph	f: A ⊗ U → B ⊗ U. TYPE: Morphism
feedback	The feedback object U. TYPE: SetObject
domain	The external domain A. TYPE: SetObject
codomain	The external codomain B. TYPE: SetObject

RETURNS	DESCRIPTION
ObservedMorphism	Tr^U(f): A → B.

Source code in src/quivers/categorical/traced.py

def trace(
    self,
    morph: Morphism,
    feedback: SetObject,
    domain: SetObject,
    codomain: SetObject,
) -> Morphism:
    """Compute the trace via fixpoint iteration.

    Parameters
    ----------
    morph : Morphism
        f: A ⊗ U → B ⊗ U.
    feedback : SetObject
        The feedback object U.
    domain : SetObject
        The external domain A.
    codomain : SetObject
        The external codomain B.

    Returns
    -------
    ObservedMorphism
        Tr^U(f): A → B.
    """
    q = self._algebra
    t = morph.tensor

    result_shape = (*domain.shape, *codomain.shape)

    # initialize with zero (bottom)
    prev = torch.full(result_shape, q.zero)
    current = prev

    for _ in range(self._max_iter):
        current = torch.full(result_shape, q.zero)

        for a_idx in itertools.product(*(range(s) for s in domain.shape)):
            for b_idx in itertools.product(*(range(s) for s in codomain.shape)):
                vals: list[torch.Tensor] = []

                for u_idx in itertools.product(*(range(s) for s in feedback.shape)):
                    src_idx = a_idx + u_idx + b_idx + u_idx
                    vals.append(t[src_idx].unsqueeze(0))

                if vals:
                    stacked = torch.cat(vals)
                    current[a_idx + b_idx] = q.join(stacked, dim=0)

        if torch.allclose(current, prev, atol=self._atol):
            break

        prev = current

    return observed(domain, codomain, current, algebra=q)

trace

trace(morph: Morphism, feedback: SetObject, domain: SetObject, codomain: SetObject, algebra: Algebra | None = None) -> Morphism

Convenience function: apply cartesian trace.

Given f: A × U → B × U, compute Tr^U(f): A → B using the CartesianTrace.

PARAMETER	DESCRIPTION
morph	The morphism f: A × U → B × U. TYPE: Morphism
feedback	The feedback object U. TYPE: SetObject
domain	The external domain A. TYPE: SetObject
codomain	The external codomain B. TYPE: SetObject
algebra	The enrichment algebra. TYPE: Algebra or None DEFAULT: None

RETURNS	DESCRIPTION
Morphism	The traced morphism Tr^U(f): A → B.

Source code in src/quivers/categorical/traced.py

def trace(
    morph: Morphism,
    feedback: SetObject,
    domain: SetObject,
    codomain: SetObject,
    algebra: Algebra | None = None,
) -> Morphism:
    """Convenience function: apply cartesian trace.

    Given f: A × U → B × U, compute Tr^U(f): A → B
    using the CartesianTrace.

    Parameters
    ----------
    morph : Morphism
        The morphism f: A × U → B × U.
    feedback : SetObject
        The feedback object U.
    domain : SetObject
        The external domain A.
    codomain : SetObject
        The external codomain B.
    algebra : Algebra or None
        The enrichment algebra.

    Returns
    -------
    Morphism
        The traced morphism Tr^U(f): A → B.
    """
    tracer = CartesianTrace(algebra=algebra)
    return tracer.trace(morph, feedback, domain, codomain)

partial_trace

partial_trace(morph: Morphism, feedback_indices: tuple[int, ...], algebra: Algebra | None = None) -> Morphism

Trace over a subset of feedback wires in a product.

Given f: (A₁ × ... × Aₙ) → (B₁ × ... × Bₙ) where some pairs (Aᵢ, Bᵢ) are feedback wires (Aᵢ = Bᵢ), compute the partial trace over the specified pairs.

PARAMETER	DESCRIPTION
morph	The morphism. TYPE: Morphism
feedback_indices	Indices of the product components to trace over. These components must have matching shapes in domain and codomain. TYPE: tuple[int, ...]
algebra	The enrichment algebra. TYPE: Algebra or None DEFAULT: None

RETURNS	DESCRIPTION
ObservedMorphism	The partially traced morphism.

Source code in src/quivers/categorical/traced.py

def partial_trace(
    morph: Morphism,
    feedback_indices: tuple[int, ...],
    algebra: Algebra | None = None,
) -> Morphism:
    """Trace over a subset of feedback wires in a product.

    Given f: (A₁ × ... × Aₙ) → (B₁ × ... × Bₙ) where some
    pairs (Aᵢ, Bᵢ) are feedback wires (Aᵢ = Bᵢ), compute the
    partial trace over the specified pairs.

    Parameters
    ----------
    morph : Morphism
        The morphism.
    feedback_indices : tuple[int, ...]
        Indices of the product components to trace over.
        These components must have matching shapes in domain
        and codomain.
    algebra : Algebra or None
        The enrichment algebra.

    Returns
    -------
    ObservedMorphism
        The partially traced morphism.
    """
    q = algebra if algebra is not None else PRODUCT_FUZZY
    t = morph.tensor
    dom = morph.domain
    cod = morph.codomain

    if not isinstance(dom, ProductSet) or not isinstance(cod, ProductSet):
        raise TypeError("partial_trace requires ProductSet domain and codomain")

    if len(dom.components) != len(cod.components):
        raise ValueError("domain and codomain must have the same number of components")

    # validate feedback components match
    for idx in feedback_indices:
        if dom.components[idx].shape != cod.components[idx].shape:
            raise ValueError(
                f"component {idx}: domain shape {dom.components[idx].shape} "
                f"!= codomain shape {cod.components[idx].shape}"
            )

    # build feedback and external objects
    external_dom_comps = [
        c for i, c in enumerate(dom.components) if i not in feedback_indices
    ]
    external_cod_comps = [
        c for i, c in enumerate(cod.components) if i not in feedback_indices
    ]
    [dom.components[i] for i in feedback_indices]

    # compute dimension indices
    n_dom = dom.ndim
    dom_offsets: list[int] = []
    offset = 0

    for c in dom.components:
        dom_offsets.append(offset)
        offset += c.ndim

    cod_offsets: list[int] = []
    offset = n_dom

    for c in cod.components:
        cod_offsets.append(offset)
        offset += c.ndim

    # identify feedback dimension pairs
    contra_dims: list[int] = []
    co_dims: list[int] = []

    for idx in feedback_indices:
        comp = dom.components[idx]

        for d in range(comp.ndim):
            contra_dims.append(dom_offsets[idx] + d)
            co_dims.append(cod_offsets[idx] + d)

    # use diagonal extraction and join
    from quivers.enriched.ends_coends import coend

    result = coend(
        t,
        contra_dims=tuple(contra_dims),
        co_dims=tuple(co_dims),
        algebra=q,
    )

    # build result objects
    if len(external_dom_comps) == 0:
        raise ValueError("cannot trace over all components")

    elif len(external_dom_comps) == 1:
        ext_dom = external_dom_comps[0]

    else:
        ext_dom = ProductSet(components=tuple(external_dom_comps))

    if len(external_cod_comps) == 1:
        ext_cod = external_cod_comps[0]

    else:
        ext_cod = ProductSet(components=tuple(external_cod_comps))

    return observed(ext_dom, ext_cod, result, algebra=q)