use crate::backend_ops::BackendOps;
use coeus_core::{CpuAddressableStorage, CpuAddressableStorageMut, Scalar};
use coeus_tensor::Tensor;
fn parse_subscript(subscript: &str) -> (Vec<&str>, &str) {
let subscript = subscript.trim();
let (lhs, rhs) = if let Some(pos) = subscript.find("->") {
(&subscript[..pos], &subscript[pos + 2..])
} else {
(subscript, "")
};
let operands: Vec<&str> = lhs.split(',').map(str::trim).collect();
(operands, rhs.trim())
}
#[inline]
pub fn einsum<T: Scalar, B: BackendOps<T> + Default>(
subscript: &str,
operands: &[&Tensor<T, B>],
backend: &B,
) -> Result<Tensor<T, B>, B::Error>
where
B::DeviceBuffer<T>: CpuAddressableStorage<T> + CpuAddressableStorageMut<T>,
{
let (lhs_parts, rhs) = parse_subscript(subscript);
assert_eq!(
lhs_parts.len(),
operands.len(),
"einsum: subscript has {} operand(s) but {} tensor(s) provided",
lhs_parts.len(),
operands.len()
);
if operands.len() == 1 {
let a = operands[0];
let lhs = lhs_parts[0];
if lhs == "ij" && rhs == "ji" {
assert_eq!(a.ndim(), 2, "einsum ij->ji: requires 2-D input");
return Ok(a.to_contiguous().permute(&[1, 0]).to_contiguous_on(backend));
}
if a.ndim() >= 2 {
let chars: Vec<char> = lhs.chars().collect();
let rhs_chars: Vec<char> = rhs.chars().collect();
if chars.len() == rhs_chars.len() {
let n = chars.len();
let mut expected_rhs = chars.clone();
expected_rhs.swap(n - 2, n - 1);
if rhs_chars == expected_rhs {
let mut perm: Vec<usize> = (0..a.ndim()).collect();
perm.swap(a.ndim() - 2, a.ndim() - 1);
return Ok(a.to_contiguous().permute(&perm).to_contiguous_on(backend));
}
}
}
if lhs == "ii" && rhs.is_empty() {
assert_eq!(a.ndim(), 2, "einsum ii->: requires 2-D input");
let n = a.shape()[0].min(a.shape()[1]);
let a_cont = a.to_contiguous();
let a_s = a_cont.as_slice();
let stride = a.shape()[1];
let trace = (0..n)
.map(|i| a_s[i * stride + i])
.fold(T::zero(), |acc, x| acc + x);
return Ok(Tensor::from_slice(vec![1], &[trace]));
}
panic!("einsum: unsupported single-operand pattern '{subscript}'");
}
assert_eq!(operands.len(), 2, "einsum: expected 1 or 2 operands");
let a = operands[0];
let b_t = operands[1];
let a_lhs = lhs_parts[0];
let b_lhs = lhs_parts[1];
if a_lhs == "i" && b_lhs == "i" && rhs.is_empty() {
assert_eq!(a.ndim(), 1, "einsum i,i->: a must be 1-D");
assert_eq!(b_t.ndim(), 1, "einsum i,i->: b must be 1-D");
let a_cont = a.to_contiguous();
let b_cont = b_t.to_contiguous();
let dot = a_cont
.as_slice()
.iter()
.zip(b_cont.as_slice().iter())
.map(|(&x, &y)| x * y)
.fold(T::zero(), |acc, v| acc + v);
return Ok(Tensor::from_slice(vec![1], &[dot]));
}
if a_lhs == "i" && b_lhs == "j" && rhs == "ij" {
assert_eq!(a.ndim(), 1, "einsum i,j->ij: a must be 1-D");
assert_eq!(b_t.ndim(), 1, "einsum i,j->ij: b must be 1-D");
let m = a.shape()[0];
let n = b_t.shape()[0];
let a_cont = a.to_contiguous();
let b_cont = b_t.to_contiguous();
let a_s = a_cont.as_slice();
let b_s = b_cont.as_slice();
let data: Vec<T> = (0..m)
.flat_map(|i| (0..n).map(move |j| a_s[i] * b_s[j]))
.collect();
return Ok(Tensor::from_slice(vec![m, n], &data));
}
if a_lhs == "ij" && b_lhs == "j" && rhs == "i" {
assert_eq!(a.ndim(), 2, "einsum ij,j->i: a must be 2-D");
assert_eq!(b_t.ndim(), 1, "einsum ij,j->i: b must be 1-D");
let m = a.shape()[0];
let k = a.shape()[1];
assert_eq!(k, b_t.shape()[0], "einsum ij,j->i: k-dim mismatch");
let a_cont = a.to_contiguous();
let b_cont = b_t.to_contiguous();
let a_s = a_cont.as_slice();
let b_s = b_cont.as_slice();
let data: Vec<T> = (0..m)
.map(|i| {
(0..k)
.map(|j| a_s[i * k + j] * b_s[j])
.fold(T::zero(), |acc, v| acc + v)
})
.collect();
return Ok(Tensor::from_slice(vec![m], &data));
}
if a_lhs == "ij" && b_lhs == "kj" && rhs == "ik" {
assert_eq!(a.ndim(), 2, "einsum ij,kj->ik: a must be 2-D");
assert_eq!(b_t.ndim(), 2, "einsum ij,kj->ik: b must be 2-D");
let m = a.shape()[0];
let k = a.shape()[1];
let n = b_t.shape()[0];
assert_eq!(k, b_t.shape()[1], "einsum ij,kj->ik: k-dim mismatch");
let a_cont = a.to_contiguous();
let b_cont = b_t.to_contiguous();
let a_s = a_cont.as_slice();
let b_s = b_cont.as_slice();
let data: Vec<T> = (0..m)
.flat_map(|i| {
(0..n).map(move |j| {
(0..k)
.map(|l| a_s[i * k + l] * b_s[j * k + l])
.fold(T::zero(), |acc, v| acc + v)
})
})
.collect();
return Ok(Tensor::from_slice(vec![m, n], &data));
}
if a_lhs == "ij" && b_lhs == "jk" && rhs == "ik" {
assert_eq!(a.ndim(), 2, "einsum ij,jk->ik: a must be 2-D");
assert_eq!(b_t.ndim(), 2, "einsum ij,jk->ik: b must be 2-D");
return Ok(crate::matmul::matmul(a, b_t, backend));
}
if a_lhs == "bij" && b_lhs == "bjk" && rhs == "bik" {
assert_eq!(a.ndim(), 3, "einsum bij,bjk->bik: a must be 3-D");
assert_eq!(b_t.ndim(), 3, "einsum bij,bjk->bik: b must be 3-D");
let batch = a.shape()[0];
let m = a.shape()[1];
let k = a.shape()[2];
let n = b_t.shape()[2];
assert_eq!(b_t.shape()[0], batch);
assert_eq!(b_t.shape()[1], k);
let a_cont = a.to_contiguous();
let b_cont = b_t.to_contiguous();
let a_s = a_cont.as_slice();
let b_s = b_cont.as_slice();
let data: Vec<T> = (0..batch)
.flat_map(|bi| {
(0..m).flat_map(move |i| {
(0..n).map(move |j| {
(0..k)
.map(|l| a_s[bi * m * k + i * k + l] * b_s[bi * k * n + l * n + j])
.fold(T::zero(), |acc, v| acc + v)
})
})
})
.collect();
return Ok(Tensor::from_slice(vec![batch, m, n], &data));
}
if a_lhs == "bik" && b_lhs == "bk" && rhs == "bi" {
assert_eq!(a.ndim(), 3, "einsum bik,bk->bi: a must be 3-D");
assert_eq!(b_t.ndim(), 2, "einsum bik,bk->bi: b must be 2-D");
let batch = a.shape()[0];
let m = a.shape()[1];
let k = a.shape()[2];
assert_eq!(b_t.shape()[0], batch);
assert_eq!(b_t.shape()[1], k);
let a_cont = a.to_contiguous();
let b_cont = b_t.to_contiguous();
let a_s = a_cont.as_slice();
let b_s = b_cont.as_slice();
let data: Vec<T> = (0..batch)
.flat_map(|bi| {
(0..m).map(move |i| {
(0..k)
.map(|j| a_s[bi * m * k + i * k + j] * b_s[bi * k + j])
.fold(T::zero(), |acc, v| acc + v)
})
})
.collect();
return Ok(Tensor::from_slice(vec![batch, m], &data));
}
if a_lhs == "bi" && b_lhs == "bj" && rhs == "bij" {
assert_eq!(a.ndim(), 2, "einsum bi,bj->bij: a must be 2-D");
assert_eq!(b_t.ndim(), 2, "einsum bi,bj->bij: b must be 2-D");
let batch = a.shape()[0];
let m = a.shape()[1];
let n = b_t.shape()[1];
assert_eq!(b_t.shape()[0], batch);
let a_cont = a.to_contiguous();
let b_cont = b_t.to_contiguous();
let a_s = a_cont.as_slice();
let b_s = b_cont.as_slice();
let data: Vec<T> = (0..batch)
.flat_map(|bi| {
(0..m).flat_map(move |i| (0..n).map(move |j| a_s[bi * m + i] * b_s[bi * n + j]))
})
.collect();
return Ok(Tensor::from_slice(vec![batch, m, n], &data));
}
panic!("einsum: unsupported pattern '{subscript}'");
}
#[inline]
pub fn einsum3<T: Scalar, B: BackendOps<T> + Default>(
subscript: &str,
a: &Tensor<T, B>,
b: &Tensor<T, B>,
c: &Tensor<T, B>,
backend: &B,
) -> Result<Tensor<T, B>, B::Error>
where
B::DeviceBuffer<T>: CpuAddressableStorage<T> + CpuAddressableStorageMut<T>,
{
let sub = subscript.trim();
match sub {
"ij,jk,kl->il" => {
let ab = einsum("ij,jk->ik", &[a, b], backend)?;
einsum("ij,jk->ik", &[&ab, c], backend)
}
"bij,bjk,bkl->bil" => {
let ab = einsum("bij,bjk->bik", &[a, b], backend)?;
einsum("bij,bjk->bik", &[&ab, c], backend)
}
_ => panic!("einsum3: unsupported 3-operand pattern '{subscript}'"),
}
}
#[cfg(test)]
mod tests {
use super::*;
use coeus_core::SequentialBackend;
use coeus_tensor::Tensor;
fn b() -> SequentialBackend {
SequentialBackend::new()
}
#[test]
fn einsum_matmul() {
let a = Tensor::from_slice(vec![2, 3], &[1.0f32, 2.0, 3.0, 4.0, 5.0, 6.0]);
let bt = Tensor::from_slice(vec![3, 2], &[7.0f32, 8.0, 9.0, 10.0, 11.0, 12.0]);
let out = einsum("ij,jk->ik", &[&a, &bt], &b()).expect("valid einsum test shapes");
assert_eq!(out.shape(), &[2, 2]);
assert_eq!(out.as_slice(), &[58.0, 64.0, 139.0, 154.0]);
}
#[test]
fn einsum_transpose() {
let a = Tensor::from_slice(vec![2, 3], &[1.0f32, 2.0, 3.0, 4.0, 5.0, 6.0]);
let out = einsum("ij->ji", &[&a], &b()).expect("valid einsum test shapes");
assert_eq!(out.shape(), &[3, 2]);
assert_eq!(out.as_slice(), &[1.0, 4.0, 2.0, 5.0, 3.0, 6.0]);
}
#[test]
fn einsum_dot_product() {
let a = Tensor::from_slice(vec![4], &[1.0f32, 2.0, 3.0, 4.0]);
let bt = Tensor::from_slice(vec![4], &[5.0f32, 6.0, 7.0, 8.0]);
let out = einsum("i,i->", &[&a, &bt], &b()).expect("valid einsum test shapes");
assert_eq!(out.shape(), &[1]);
assert_eq!(
out.as_slice(),
&[1.0 * 5.0 + 2.0 * 6.0 + 3.0 * 7.0 + 4.0 * 8.0]
);
}
#[test]
fn einsum_trace() {
let a = Tensor::from_slice(
vec![3, 3],
&[1.0f32, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0],
);
let out = einsum("ii->", &[&a], &b()).expect("valid einsum test shapes");
assert_eq!(out.as_slice(), &[1.0 + 5.0 + 9.0]);
}
#[test]
fn einsum_outer_product() {
let a = Tensor::from_slice(vec![2], &[1.0f32, 2.0]);
let bt = Tensor::from_slice(vec![3], &[3.0f32, 4.0, 5.0]);
let out = einsum("i,j->ij", &[&a, &bt], &b()).expect("valid einsum test shapes");
assert_eq!(out.shape(), &[2, 3]);
assert_eq!(out.as_slice(), &[3.0, 4.0, 5.0, 6.0, 8.0, 10.0]);
}
#[test]
fn einsum_matvec() {
let a = Tensor::from_slice(vec![2, 3], &[1.0f32, 2.0, 3.0, 4.0, 5.0, 6.0]);
let v = Tensor::from_slice(vec![3], &[1.0f32, 0.0, 1.0]);
let out = einsum("ij,j->i", &[&a, &v], &b()).expect("valid einsum test shapes");
assert_eq!(out.shape(), &[2]);
assert_eq!(out.as_slice(), &[4.0, 10.0]);
}
#[test]
fn einsum_batched_matmul() {
let a = Tensor::from_slice(vec![1, 2, 2], &[1.0f32, 2.0, 3.0, 4.0]);
let bt = Tensor::from_slice(vec![1, 2, 2], &[5.0f32, 6.0, 7.0, 8.0]);
let out = einsum("bij,bjk->bik", &[&a, &bt], &b()).expect("valid einsum test shapes");
assert_eq!(out.shape(), &[1, 2, 2]);
assert_eq!(out.as_slice(), &[19.0, 22.0, 43.0, 50.0]);
}
#[test]
fn einsum_three_operand_matmul_chain() {
let a = Tensor::from_slice(vec![2, 2], &[1.0f32, 2.0, 3.0, 4.0]);
let bt = Tensor::from_slice(vec![2, 2], &[5.0f32, 6.0, 7.0, 8.0]);
let c = Tensor::from_slice(vec![2, 2], &[9.0f32, 10.0, 11.0, 12.0]);
let out = einsum3("ij,jk,kl->il", &a, &bt, &c, &b())
.expect("valid three-operand einsum test shapes");
assert_eq!(out.shape(), &[2, 2]);
assert_eq!(out.as_slice(), &[413.0, 454.0, 937.0, 1030.0]);
}
}