tensor4all_core/defaults/
direct_sum.rs1use 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
19pub 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
88pub 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#[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 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
204fn 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
220fn 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#[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 fn width(self, g: usize) -> usize {
248 match self {
249 Groups::Pairs(_) => 2,
250 Groups::Lists(lists) => lists[g].len(),
251 }
252 }
253
254 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
264struct DirectSumSetup {
266 operand_dims: Vec<Vec<usize>>,
268 operand_axes: Vec<Vec<usize>>,
271 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 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 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 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 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 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 let mut result_data: Vec<T> = vec![T::zero(); setup.result_total];
460 let mut cursor = vec![0usize; setup.result_dims.len()];
461
462 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
493struct BlockLayout<'a> {
497 dims: Vec<usize>,
498 src_strides: Vec<usize>,
499 dst_strides: &'a [usize],
500 dst_start: usize,
501}
502
503fn 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 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 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;