Skip to main content

tensor4all_core/defaults/
direct_sum.rs

1//! Direct sum operations for tensors.
2//!
3//! This module provides functionality to compute the direct sum of tensors
4//! along specified index pairs. The direct sum concatenates tensor data along
5//! the paired indices, creating new indices with combined dimensions.
6//! [`direct_sum`] combines two tensors; [`direct_sum_many`] combines any
7//! number in one pass.
8//!
9//! This module works with concrete types (`DynIndex`, `IdxTensor`) only.
10
11use crate::defaults::DynIndex;
12use crate::defaults::IdxTensorError;
13use crate::index_like::IndexLike;
14use crate::tensor::IdxTensor;
15use anyhow::Result;
16use num_traits::Zero;
17use tensor4all_tensorbackend::TensorElement;
18
19/// Compute the direct sum of two tensors along specified index pairs.
20///
21/// For tensors A and B with indices to be summed specified as pairs,
22/// creates a new tensor C where each paired index has dimension = dim_A + dim_B.
23/// Non-paired indices must match exactly between A and B.
24///
25/// # Arguments
26///
27/// * `a` - First tensor
28/// * `b` - Second tensor
29/// * `pairs` - Pairs of (a_index, b_index) to be summed. Each pair creates
30///
31///   a new index in the result with dimension = dim(a_index) + dim(b_index).
32///
33/// # Returns
34///
35/// A tuple of:
36/// - The direct sum tensor
37/// - The new indices created for the summed dimensions (one per pair)
38///
39/// # Errors
40///
41/// Returns [`IdxTensorError::ShapeMismatch`] when a non-paired index of either
42/// operand is not a non-paired index of the other one (an index present on one
43/// side only, or matching only in id but not in prime level or tags), and
44/// [`IdxTensorError::Operation`] when `pairs` is empty, when a paired index is
45/// missing or a common index differs in dimension, when the operands do not
46/// share one dense scalar type (`f32`, `f64`, `Complex32` or `Complex64`), or
47/// when the backend construction fails.
48///
49/// # Example
50///
51/// ```
52/// use tensor4all_core::{direct_sum, DynIndex, IdxTensor};
53///
54/// # fn main() -> anyhow::Result<()> {
55/// let j = DynIndex::new_dyn(2);
56/// let k = DynIndex::new_dyn(3);
57///
58/// let a = IdxTensor::from_dense(vec![j.clone()], vec![1.0, 2.0])?;
59/// let b = IdxTensor::from_dense(vec![k.clone()], vec![3.0, 4.0, 5.0])?;
60/// let (result, new_indices) = direct_sum(&a, &b, &[(j.clone(), k.clone())])?;
61///
62/// assert_eq!(new_indices.len(), 1);
63/// assert_eq!(result.to_vec::<f64>()?, vec![1.0, 2.0, 3.0, 4.0, 5.0]);
64/// # Ok(())
65/// # }
66/// ```
67pub fn direct_sum(
68    a: &IdxTensor,
69    b: &IdxTensor,
70    pairs: &[(DynIndex, DynIndex)],
71) -> std::result::Result<(IdxTensor, Vec<DynIndex>), IdxTensorError> {
72    let Some(kind) = DenseKind::common(&[a, b]) else {
73        return Err(IdxTensorError::Operation {
74            operation: "direct_sum",
75            source: std::sync::Arc::new(std::io::Error::other(
76                "direct_sum requires both tensors to have the same dense scalar type (f32, f64, Complex32 or Complex64)",
77            )),
78        });
79    };
80    if pairs.is_empty() {
81        return Err(IdxTensorError::from(anyhow::anyhow!(
82            "direct_sum requires at least one index pair"
83        )));
84    }
85    direct_sum_dispatch(kind, &[a, b], Groups::Pairs(pairs))
86}
87
88/// Compute the direct sum of any number of tensors in one pass.
89///
90/// Each entry of `groups` lists one index per operand, in operand order, and
91/// becomes one new index whose dimension is the sum of the group's
92/// dimensions. Operand `i` occupies its own diagonal block, after the blocks
93/// of operands `0..i`, and every other entry is zero. The indices of an
94/// operand that belong to no group (its common indices) must be the same
95/// set, with the same dimensions, for every operand. With two operands this
96/// is [`direct_sum`] with `pairs[g] = (groups[g][0], groups[g][1])`.
97///
98/// Every result element is written once. A chain of binary [`direct_sum`]
99/// calls copies the growing partial result at every step instead.
100///
101/// # Arguments
102///
103/// * `operands` - The tensors to combine; at least one. They must share one
104///   dense scalar type: `f32`, `f64`, `Complex32` or `Complex64`.
105/// * `groups` - The grouped indices; at least one group, each with exactly
106///   `operands.len()` entries, entry `i` an index of operand `i`. An index of
107///   an operand may appear in at most one group.
108///
109/// # Returns
110///
111/// A tuple of the direct-sum tensor and the new indices (one per group, in
112/// `groups` order). The result's indices are `operands[0]`'s common indices in
113/// its order, followed by the new indices; the payload is column-major.
114///
115/// # Errors
116///
117/// Returns [`IdxTensorError::ShapeMismatch`] when a common index of one
118/// operand is not a common index of another one (an index present on one side
119/// only, or matching only in id but not in prime level or tags), and
120/// [`IdxTensorError::Operation`] when `operands` or `groups` is empty, when a
121/// group does not have one index per operand, when a grouped index is missing
122/// from its operand or appears in two groups, when a common index differs in
123/// dimension, when the operands do not share one dense scalar type, when an
124/// operand tracks gradients, or when the backend construction fails.
125///
126/// # Example
127///
128/// ```
129/// use tensor4all_core::{direct_sum_many, DynIndex, IdxTensor, IndexLike};
130///
131/// # fn main() -> anyhow::Result<()> {
132/// let site = DynIndex::new_dyn(2);
133/// let (b0, b1, b2) = (DynIndex::new_dyn(1), DynIndex::new_dyn(2), DynIndex::new_dyn(1));
134///
135/// let t0 = IdxTensor::from_dense(vec![site.clone(), b0.clone()], vec![1.0, 2.0])?;
136/// let t1 = IdxTensor::from_dense(vec![site.clone(), b1.clone()], vec![3.0, 4.0, 5.0, 6.0])?;
137/// let t2 = IdxTensor::from_dense(vec![b2.clone(), site.clone()], vec![7.0, 8.0])?;
138/// let (result, new_indices) = direct_sum_many(&[&t0, &t1, &t2], &[vec![b0, b1, b2]])?;
139///
140/// // The common `site` index comes first, then the new bond of dimension 1 + 2 + 1.
141/// assert_eq!(result.indices(), &[site, new_indices[0].clone()]);
142/// assert_eq!(new_indices[0].dim(), 4);
143/// assert_eq!(result.to_vec::<f64>()?, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0]);
144/// # Ok(())
145/// # }
146/// ```
147pub fn direct_sum_many(
148    operands: &[&IdxTensor],
149    groups: &[Vec<DynIndex>],
150) -> std::result::Result<(IdxTensor, Vec<DynIndex>), IdxTensorError> {
151    if operands.is_empty() {
152        return Err(IdxTensorError::from(anyhow::anyhow!(
153            "direct_sum requires at least one operand"
154        )));
155    }
156    let Some(kind) = DenseKind::common(operands) else {
157        return Err(IdxTensorError::from(anyhow::anyhow!(
158            "direct_sum requires every operand to have the same dense scalar type (f32, f64, Complex32 or Complex64)"
159        )));
160    };
161    if groups.is_empty() {
162        return Err(IdxTensorError::from(anyhow::anyhow!(
163            "direct_sum requires at least one index group"
164        )));
165    }
166    direct_sum_dispatch(kind, operands, Groups::Lists(groups))
167}
168
169/// The dense scalar types `direct_sum` supports.
170#[derive(Clone, Copy, PartialEq, Eq)]
171enum DenseKind {
172    F32,
173    F64,
174    C32,
175    C64,
176}
177
178impl DenseKind {
179    fn of(tensor: &IdxTensor) -> Option<Self> {
180        if tensor.is_f64() {
181            Some(Self::F64)
182        } else if tensor.is_c64() {
183            Some(Self::C64)
184        } else if tensor.is_f32() {
185            Some(Self::F32)
186        } else if tensor.is_c32() {
187            Some(Self::C32)
188        } else {
189            None
190        }
191    }
192
193    /// The type every operand shares, or `None` when they differ (or one is
194    /// not a supported dense type). `operands` is non-empty.
195    fn common(operands: &[&IdxTensor]) -> Option<Self> {
196        let kind = Self::of(operands[0])?;
197        operands[1..]
198            .iter()
199            .all(|operand| Self::of(operand) == Some(kind))
200            .then_some(kind)
201    }
202}
203
204/// Run the typed kernel for operands that share the dense type `kind`, with
205/// non-empty `operands` and `groups`.
206fn direct_sum_dispatch(
207    kind: DenseKind,
208    operands: &[&IdxTensor],
209    groups: Groups<'_>,
210) -> std::result::Result<(IdxTensor, Vec<DynIndex>), IdxTensorError> {
211    match kind {
212        DenseKind::F32 => direct_sum_typed::<f32>(operands, groups),
213        DenseKind::F64 => direct_sum_typed::<f64>(operands, groups),
214        DenseKind::C32 => direct_sum_typed::<num_complex::Complex32>(operands, groups),
215        DenseKind::C64 => direct_sum_typed::<num_complex::Complex64>(operands, groups),
216    }
217    .map_err(IdxTensorError::from)
218}
219
220/// "first", "second", ... for operand `i` in error messages.
221fn ordinal(i: usize) -> String {
222    match i {
223        0 => "first".to_string(),
224        1 => "second".to_string(),
225        2 => "third".to_string(),
226        _ => format!("{}-th", i + 1),
227    }
228}
229
230/// The grouped indices of a direct sum, read in place: the binary path's
231/// pairs or the N-ary path's lists, without converting one into the other.
232#[derive(Clone, Copy)]
233enum Groups<'a> {
234    Pairs(&'a [(DynIndex, DynIndex)]),
235    Lists(&'a [Vec<DynIndex>]),
236}
237
238impl<'a> Groups<'a> {
239    fn len(self) -> usize {
240        match self {
241            Groups::Pairs(pairs) => pairs.len(),
242            Groups::Lists(lists) => lists.len(),
243        }
244    }
245
246    /// Number of indices listed in group `g`.
247    fn width(self, g: usize) -> usize {
248        match self {
249            Groups::Pairs(_) => 2,
250            Groups::Lists(lists) => lists[g].len(),
251        }
252    }
253
254    /// Operand `i`'s index of group `g`; `i < self.width(g)`.
255    fn index(self, g: usize, i: usize) -> &'a DynIndex {
256        match self {
257            Groups::Pairs(pairs) if i == 0 => &pairs[g].0,
258            Groups::Pairs(pairs) => &pairs[g].1,
259            Groups::Lists(lists) => &lists[g][i],
260        }
261    }
262}
263
264/// Setup data for direct sum computation.
265struct DirectSumSetup {
266    /// Per operand: its dims, computed once.
267    operand_dims: Vec<Vec<usize>>,
268    /// Per operand: the position, in the operand's own index order, of each
269    /// result axis (common indices, then the operand's index of each group).
270    operand_axes: Vec<Vec<usize>>,
271    /// Per operand: its own column-major strides.
272    operand_strides: Vec<Vec<usize>>,
273    result_indices: Vec<DynIndex>,
274    result_dims: Vec<usize>,
275    result_total: usize,
276    new_indices: Vec<DynIndex>,
277    n_common: usize,
278}
279
280fn setup_direct_sum(operands: &[&IdxTensor], groups: Groups<'_>) -> Result<DirectSumSetup> {
281    use std::collections::{HashMap, HashSet};
282
283    let n = operands.len();
284    let operand_dims: Vec<Vec<usize>> = operands.iter().map(|operand| operand.dims()).collect();
285    // Build maps from full index metadata to positions. Same-id indices that
286    // differ by prime level or tags are distinct axes.
287    let index_maps: Vec<HashMap<&DynIndex, usize>> = operands
288        .iter()
289        .map(|operand| {
290            operand
291                .indices
292                .iter()
293                .enumerate()
294                .map(|(i, idx)| (idx, i))
295                .collect()
296        })
297        .collect();
298
299    // Build the set of grouped indices of every operand.
300    let mut grouped: Vec<HashSet<&DynIndex>> = vec![HashSet::new(); n];
301    for g in 0..groups.len() {
302        if groups.width(g) != n {
303            return Err(anyhow::anyhow!(
304                "index group {g} has {} entries, expected one per operand ({n})",
305                groups.width(g)
306            ));
307        }
308        for (i, operand_grouped) in grouped.iter_mut().enumerate() {
309            let idx = groups.index(g, i);
310            if !index_maps[i].contains_key(idx) {
311                return Err(anyhow::anyhow!(
312                    "Index not found in {} tensor (direct_sum)",
313                    ordinal(i)
314                ));
315            }
316            if !operand_grouped.insert(idx) {
317                return Err(anyhow::anyhow!(
318                    "index {idx:?} of the {} tensor appears in two groups (direct_sum)",
319                    ordinal(i)
320                ));
321            }
322        }
323    }
324
325    // Identify common (non-grouped) indices. Every non-grouped index of an
326    // operand must be a non-grouped index of every other one: an index left on
327    // one side only has no axis in the result, so accepting it would silently
328    // read that operand at coordinate 0 (tensor4all/tensor4all-rs#1018).
329    // Iterate over the first operand's indices (Vec) to preserve
330    // deterministic order, using the other maps only for lookups.
331    let unpaired_mismatch = |i: usize, idx: &DynIndex| {
332        let other = if n == 2 {
333            "the other operand"
334        } else {
335            "every other operand"
336        };
337        anyhow::Error::new(IdxTensorError::ShapeMismatch {
338            operation: "direct_sum",
339            expected: format!(
340                "every non-paired index of the {} operand to be a non-paired index of {other}",
341                ordinal(i)
342            ),
343            actual: format!("{idx:?} has no non-paired counterpart"),
344        })
345    };
346    let first = operands[0];
347    let first_dims = &operand_dims[0];
348    let mut operand_axes: Vec<Vec<usize>> = Vec::with_capacity(n);
349    operand_axes.push(
350        (0..first.indices.len())
351            .filter(|&pos| !grouped[0].contains(&first.indices[pos]))
352            .collect(),
353    );
354    let n_common = operand_axes[0].len();
355    for (i, operand) in operands.iter().enumerate().skip(1) {
356        let dims = &operand_dims[i];
357        let mut axes = Vec::with_capacity(operand.indices.len());
358        for &first_pos in &operand_axes[0][..n_common] {
359            let idx = &first.indices[first_pos];
360            let pos = match index_maps[i].get(idx) {
361                Some(&pos) if !grouped[i].contains(idx) => pos,
362                _ => return Err(unpaired_mismatch(0, idx)),
363            };
364            if first_dims[first_pos] != dims[pos] {
365                return Err(anyhow::anyhow!(
366                    "Dimension mismatch for common index: {} vs {}",
367                    first_dims[first_pos],
368                    dims[pos]
369                ));
370            }
371            axes.push(pos);
372        }
373        if let Some(idx) = operand.indices.iter().find(|&idx| {
374            !grouped[i].contains(idx)
375                && !(index_maps[0].contains_key(idx) && !grouped[0].contains(idx))
376        }) {
377            return Err(unpaired_mismatch(i, idx));
378        }
379        operand_axes.push(axes);
380    }
381    for (i, axes) in operand_axes.iter_mut().enumerate() {
382        axes.extend((0..groups.len()).map(|g| index_maps[i][groups.index(g, i)]));
383    }
384
385    // Create new indices for grouped dimensions.
386    let mut new_indices: Vec<DynIndex> = Vec::with_capacity(groups.len());
387    for g in 0..groups.len() {
388        let new_dim = (0..n).try_fold(0usize, |acc, i| {
389            acc.checked_add(operand_dims[i][operand_axes[i][n_common + g]])
390                .ok_or_else(|| anyhow::anyhow!("direct_sum index dimension overflowed usize"))
391        })?;
392        let new_index = DynIndex::new_link(new_dim)
393            .map_err(|e| anyhow::anyhow!("Failed to create index: {:?}", e))?;
394        new_indices.push(new_index);
395    }
396
397    // Common indices first, then the new indices; the new indices preserve
398    // the full index identity semantics (id + plev + tags).
399    let result_rank = n_common + new_indices.len();
400    let mut result_indices: Vec<DynIndex> = Vec::with_capacity(result_rank);
401    let mut result_dims: Vec<usize> = Vec::with_capacity(result_rank);
402    for &pos in &operand_axes[0][..n_common] {
403        result_indices.push(first.indices[pos].clone());
404        result_dims.push(first_dims[pos]);
405    }
406    for new_idx in &new_indices {
407        result_indices.push(new_idx.clone());
408        result_dims.push(new_idx.dim());
409    }
410
411    let result_total = checked_product(&result_dims, "direct_sum result")?;
412    let operand_strides = operand_dims
413        .iter()
414        .map(|dims| checked_strides(dims, "direct_sum operand"))
415        .collect::<Result<Vec<_>>>()?;
416
417    Ok(DirectSumSetup {
418        operand_dims,
419        operand_axes,
420        operand_strides,
421        result_indices,
422        result_dims,
423        result_total,
424        new_indices,
425        n_common,
426    })
427}
428
429fn checked_product(dims: &[usize], name: &str) -> Result<usize> {
430    dims.iter().try_fold(1usize, |acc, &dim| {
431        acc.checked_mul(dim)
432            .ok_or_else(|| anyhow::anyhow!("{name} shape product overflowed usize"))
433    })
434}
435
436fn checked_strides(dims: &[usize], name: &str) -> Result<Vec<usize>> {
437    let mut strides = vec![1usize; dims.len()];
438    for i in 1..dims.len() {
439        strides[i] = strides[i - 1]
440            .checked_mul(dims[i - 1])
441            .ok_or_else(|| anyhow::anyhow!("{name} stride overflowed usize"))?;
442    }
443    Ok(strides)
444}
445
446fn direct_sum_typed<T: TensorElement + Zero>(
447    operands: &[&IdxTensor],
448    groups: Groups<'_>,
449) -> Result<(IdxTensor, Vec<DynIndex>)> {
450    if operands.iter().any(|operand| operand.tracks_grad()) {
451        return Err(anyhow::anyhow!(
452            "direct_sum does not support tracked tensors until an AD-preserving block path is available"
453        ));
454    }
455    let setup = setup_direct_sum(operands, groups)?;
456    let result_strides = checked_strides(&setup.result_dims, "direct_sum result")?;
457    // INVARIANT: the zero fill is semantic: every entry outside the diagonal
458    // blocks is zero.
459    let mut result_data: Vec<T> = vec![T::zero(); setup.result_total];
460    let mut cursor = vec![0usize; setup.result_dims.len()];
461
462    // Operand `i` starts, along every new axis, after the blocks of operands
463    // `0..i`.
464    let mut offsets = vec![0usize; groups.len()];
465    for (i, operand) in operands.iter().enumerate() {
466        let dims = &setup.operand_dims[i];
467        let axes = &setup.operand_axes[i];
468        let layout = BlockLayout {
469            dims: axes.iter().map(|&axis| dims[axis]).collect(),
470            src_strides: axes
471                .iter()
472                .map(|&axis| setup.operand_strides[i][axis])
473                .collect(),
474            dst_strides: &result_strides,
475            dst_start: offsets
476                .iter()
477                .zip(&result_strides[setup.n_common..])
478                .map(|(offset, stride)| offset * stride)
479                .sum(),
480        };
481        operand.with_dense_slice::<T, _>(|values| {
482            copy_block(values, &mut result_data, &layout, &mut cursor)
483        })?;
484        for (offset, &axis) in offsets.iter_mut().zip(&axes[setup.n_common..]) {
485            *offset += dims[axis];
486        }
487    }
488
489    let result = IdxTensor::from_dense(setup.result_indices, result_data)?;
490    Ok((result, setup.new_indices))
491}
492
493/// Where one operand's block goes: its extents in result axis order, the
494/// operand's own (column-major) stride of each result axis, the result's
495/// strides, and the result offset of the block's first element.
496struct BlockLayout<'a> {
497    dims: Vec<usize>,
498    src_strides: Vec<usize>,
499    dst_strides: &'a [usize],
500    dst_start: usize,
501}
502
503/// Copy one operand, read in its own layout, into its diagonal block of the
504/// result.
505///
506/// The leading result axes along which both layouts are contiguous are merged
507/// into one run moved with `copy_from_slice`. When not even the first axis is
508/// contiguous in the operand, the inner loop walks that axis with its operand
509/// stride. An odometer steps the remaining axes once per run, not once per
510/// element, so no multi-index is decoded per element.
511fn copy_block<T: Copy>(
512    values: &[T],
513    result: &mut [T],
514    layout: &BlockLayout<'_>,
515    cursor: &mut [usize],
516) {
517    let rank = layout.dims.len();
518    let mut merged = 0;
519    let mut run = 1usize;
520    while merged < rank && layout.src_strides[merged] == run && layout.dst_strides[merged] == run {
521        run *= layout.dims[merged];
522        merged += 1;
523    }
524    // With no merged axis, axis 0 is walked element by element (its result
525    // stride is 1, its operand stride `src_strides[0]`).
526    let (inner_len, inner_stride, first_outer) = if merged == 0 {
527        (layout.dims[0], layout.src_strides[0], 1)
528    } else {
529        (run, 1, merged)
530    };
531    cursor.fill(0);
532    let mut src = 0usize;
533    let mut dst = layout.dst_start;
534    // INVARIANT: `cursor[a] < dims[a]` on every axis, so `src` stays inside the
535    // operand's `prod(dims)` elements and `dst` inside the operand's block,
536    // which `setup_direct_sum` sized to lie inside the result. `rank >= 1`
537    // (at least one pair) and `inner_len > 0`, because an `IdxTensor` has no
538    // zero dimension (`checked_total_size` rejects one at construction).
539    loop {
540        if inner_stride == 1 {
541            result[dst..dst + inner_len].copy_from_slice(&values[src..src + inner_len]);
542        } else {
543            for (k, slot) in result[dst..dst + inner_len].iter_mut().enumerate() {
544                *slot = values[src + k * inner_stride];
545            }
546        }
547        let mut axis = first_outer;
548        loop {
549            if axis == rank {
550                return;
551            }
552            cursor[axis] += 1;
553            src += layout.src_strides[axis];
554            dst += layout.dst_strides[axis];
555            if cursor[axis] < layout.dims[axis] {
556                break;
557            }
558            src -= layout.src_strides[axis] * layout.dims[axis];
559            dst -= layout.dst_strides[axis] * layout.dims[axis];
560            cursor[axis] = 0;
561            axis += 1;
562        }
563    }
564}
565
566#[cfg(test)]
567mod tests;