use std::sync::Arc;
use crate::algebra::{Algebra, BasisIdx};
use crate::field::{Fp, PrimeField};
use crate::hom::{Morphism, matrix_is_zero};
use crate::linalg::DenseMat;
use crate::profile::{Site, hit};
use crate::quiver::{ArrowId, PathWord, QuiverError};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ModuleError {
DimsLengthMismatch { expected: usize, got: usize },
MapCountMismatch { expected: usize, got: usize },
MapShapeMismatch {
arrow: ArrowId,
expected: (usize, usize),
got: (usize, usize),
},
NonCanonicalEntry {
arrow: ArrowId,
row: usize,
col: usize,
},
RelationActsNonzero { index: usize },
}
display_error! { error ModuleError {
Self::DimsLengthMismatch { expected, got } => "dims has {got} entries, quiver has {expected} vertices";
Self::MapCountMismatch { expected, got } => "maps has {got} matrices, quiver has {expected} arrows";
Self::MapShapeMismatch { arrow, expected, got } => "map for arrow {} is {}x{}, expected {}x{}", arrow.0, got.0, got.1, expected.0, expected.1;
Self::NonCanonicalEntry { arrow, row, col } => "map for arrow {} has a non-canonical entry at ({row}, {col}) for the algebra's field", arrow.0;
Self::RelationActsNonzero { index } => "relation {index} acts as a nonzero matrix";
} }
#[derive(Clone, Debug)]
pub struct Module(Arc<ModuleInner>);
#[derive(Debug)]
struct ModuleInner {
algebra: Arc<Algebra>,
dims: Vec<usize>,
maps: Vec<DenseMat>,
}
fn zero_maps(algebra: &Algebra, dims: &[usize]) -> Vec<DenseMat> {
let quiver = algebra.quiver();
(0..quiver.num_arrows())
.map(|i| {
let arrow = ArrowId(i as u32);
DenseMat::zero(
dims[quiver.source(arrow) as usize],
dims[quiver.target(arrow) as usize],
)
})
.collect()
}
fn basis_data(
algebra: &Arc<Algebra>,
vertex: u32,
incoming: bool,
kind: &str,
) -> (Vec<usize>, Vec<usize>) {
let quiver = algebra.quiver();
assert!(
vertex < quiver.num_vertices(),
"{kind}: vertex {vertex} out of range"
);
let mut positions = vec![usize::MAX; algebra.dim()];
let mut dims = vec![0usize; quiver.num_vertices() as usize];
for w in 0..quiver.num_vertices() {
let component = if incoming {
algebra.paths_between(w, vertex)
} else {
algebra.paths_between(vertex, w)
};
dims[w as usize] = component.len();
for (index, &basis) in component.iter().enumerate() {
positions[basis] = index;
}
}
(dims, positions)
}
pub(crate) fn same_representation(a: &Module, b: &Module) -> bool {
Arc::ptr_eq(a.algebra(), b.algebra())
&& a.dim_vector() == b.dim_vector()
&& a.0.maps == b.0.maps
}
pub(crate) fn same_morphism_data(a: &Morphism, b: &Morphism) -> bool {
same_representation(a.source(), b.source())
&& same_representation(a.target(), b.target())
&& (0..a.source().algebra().quiver().num_vertices()).all(|v| a.map_at(v) == b.map_at(v))
}
pub(crate) fn same_slice<T>(left: &[T], right: &[T], same: impl Fn(&T, &T) -> bool) -> bool {
left.len() == right.len() && left.iter().zip(right).all(|(a, b)| same(a, b))
}
impl Module {
fn from_parts(algebra: Arc<Algebra>, dims: Vec<usize>, maps: Vec<DenseMat>) -> Module {
Module(Arc::new(ModuleInner {
algebra,
dims,
maps,
}))
}
pub fn new(
algebra: Arc<Algebra>,
dims: Vec<usize>,
maps: Vec<DenseMat>,
) -> Result<Module, ModuleError> {
hit(Site::ModuleNew);
let field = algebra.field();
let quiver = algebra.quiver();
let num_vertices = quiver.num_vertices() as usize;
if dims.len() != num_vertices {
return Err(ModuleError::DimsLengthMismatch {
expected: num_vertices,
got: dims.len(),
});
}
if maps.len() != quiver.num_arrows() {
return Err(ModuleError::MapCountMismatch {
expected: quiver.num_arrows(),
got: maps.len(),
});
}
for (i, map) in maps.iter().enumerate() {
let arrow = ArrowId(i as u32);
let expected = (
dims[quiver.source(arrow) as usize],
dims[quiver.target(arrow) as usize],
);
let got = (map.rows(), map.cols());
if got != expected {
return Err(ModuleError::MapShapeMismatch {
arrow,
expected,
got,
});
}
if let Some((row, col)) = map.first_noncanonical(&field) {
return Err(ModuleError::NonCanonicalEntry { arrow, row, col });
}
}
for (index, relation) in algebra.relations().iter().enumerate() {
hit(Site::ModuleRelationCheck);
let source = relation.source() as usize;
let target = relation.target() as usize;
let mut acc = DenseMat::zero(dims[source], dims[target]);
for (coeff, word) in relation.terms() {
let mut action = DenseMat::identity(dims[source]);
for &a in word.arrows() {
action = action.mul(&maps[a.index()], &field);
}
acc.add_scaled_assign(&action, *coeff, &field);
}
if !matrix_is_zero(&acc) {
return Err(ModuleError::RelationActsNonzero { index });
}
}
Ok(Module::from_parts(algebra, dims, maps))
}
pub(crate) fn from_relation_checked(
algebra: Arc<Algebra>,
dims: Vec<usize>,
maps: Vec<DenseMat>,
) -> Module {
debug_assert!(
Module::new(algebra.clone(), dims.clone(), maps.clone()).is_ok(),
"from_relation_checked: the representation data does not define a module"
);
Module::from_parts(algebra, dims, maps)
}
accessor_methods! {
pub ptr_eq(other: &Module) -> bool = |this| Arc::ptr_eq(&this.0, &other.0);
pub(crate) addr() -> usize = |this| Arc::as_ptr(&this.0) as usize;
}
pub fn zero(algebra: &Arc<Algebra>) -> Module {
let dims = vec![0; algebra.quiver().num_vertices() as usize];
let maps = zero_maps(algebra, &dims);
Module::new(algebra.clone(), dims, maps).expect("the zero module is a module")
}
pub fn simple(algebra: &Arc<Algebra>, v: u32) -> Module {
let quiver = algebra.quiver();
assert!(v < quiver.num_vertices(), "simple: vertex {v} out of range");
let dims: Vec<usize> = (0..quiver.num_vertices())
.map(|w| usize::from(w == v))
.collect();
let maps = zero_maps(algebra, &dims);
Module::new(algebra.clone(), dims, maps).expect("S_v is a module")
}
pub fn projective(algebra: &Arc<Algebra>, v: u32) -> Module {
hit(Site::ModuleProjective);
let quiver = algebra.quiver();
let (dims, pos) = basis_data(algebra, v, false, "projective");
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (s, t) = (quiver.source(a), quiver.target(a));
let mut mat = DenseMat::zero(dims[s as usize], dims[t as usize]);
for (row, &p) in algebra.paths_between(v, s).iter().enumerate() {
for &(q, c) in algebra.right_mul(p, a) {
mat.set(row, pos[q], c);
}
}
mat
})
.collect();
Module::new(algebra.clone(), dims, maps).expect("P_v is a module")
}
pub fn injective(algebra: &Arc<Algebra>, v: u32) -> Module {
hit(Site::ModuleInjective);
let quiver = algebra.quiver();
let (dims, pos) = basis_data(algebra, v, true, "injective");
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (s, t) = (quiver.source(a), quiver.target(a));
let mut mat = DenseMat::zero(dims[s as usize], dims[t as usize]);
for (col, &p) in algebra.paths_between(t, v).iter().enumerate() {
for &(q, c) in algebra.left_mul(a, p) {
mat.set(pos[q], col, c);
}
}
mat
})
.collect();
Module::new(algebra.clone(), dims, maps).expect("I_v is a module")
}
accessor_methods! {
pub algebra() -> &Arc<Algebra> = |this| &this.0.algebra;
pub field() -> PrimeField = |this| this.0.algebra.field();
pub dim_vector() -> &[usize] = |this| &this.0.dims;
pub dim_at(v: u32) -> usize = |this| this.0.dims[v as usize];
pub total_dim() -> usize = |this| this.0.dims.iter().sum();
pub is_zero() -> bool = |this| this.0.dims.iter().all(|&d| d == 0);
pub map(a: ArrowId) -> &DenseMat = |this| &this.0.maps[a.index()];
}
pub fn word_action(&self, word: &PathWord) -> Result<DenseMat, QuiverError> {
hit(Site::WordAction);
word.validate_in(self.0.algebra.quiver())?;
let field = self.field();
let mut acc = DenseMat::identity(self.0.dims[word.source() as usize]);
for &a in word.arrows() {
acc = acc.mul(&self.0.maps[a.index()], &field);
}
Ok(acc)
}
pub fn element_action(&self, terms: &[(BasisIdx, Fp)]) -> DenseMat {
hit(Site::ElementAction);
assert!(!terms.is_empty(), "element_action: terms are empty");
let basis = self.0.algebra.basis();
let source = basis[terms[0].0].source();
let target = basis[terms[0].0].target();
let field = self.field();
let mut acc = DenseMat::zero(self.0.dims[source as usize], self.0.dims[target as usize]);
for &(index, coeff) in terms {
let word = &basis[index];
assert!(
word.source() == source && word.target() == target,
"element_action: terms mix sources or targets"
);
let action = self
.word_action(word)
.expect("algebra basis words are valid in their own quiver");
acc.add_scaled_assign(&action, coeff, &field);
}
acc
}
}
pub fn direct_sum(summands: &[&Module]) -> (Module, Vec<Morphism>, Vec<Morphism>) {
hit(Site::DirectSum);
assert!(!summands.is_empty(), "direct_sum: needs a summand");
let first = summands[0];
assert!(
summands[1..]
.iter()
.all(|s| Arc::ptr_eq(first.algebra(), s.algebra())),
"direct_sum: mixed algebras"
);
let quiver = first.algebra().quiver();
let n = quiver.num_vertices() as usize;
let field = first.field();
let mut offsets = vec![vec![0usize; n]; summands.len()];
let mut dims = vec![0usize; n];
for (k, s) in summands.iter().enumerate() {
for (v, dim) in dims.iter_mut().enumerate() {
offsets[k][v] = *dim;
*dim += s.dim_vector()[v];
}
}
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (u, w) = (quiver.source(a) as usize, quiver.target(a) as usize);
let mut mat = DenseMat::zero(dims[u], dims[w]);
for (k, s) in summands.iter().enumerate() {
let block = s.map(a);
for r in 0..block.rows() {
for c in 0..block.cols() {
mat.set(offsets[k][u] + r, offsets[k][w] + c, block.get(r, c));
}
}
}
mat
})
.collect();
let sum = Module::new(first.algebra().clone(), dims, maps)
.expect("a direct sum of modules is a module");
let mut inclusions = Vec::with_capacity(summands.len());
let mut projections = Vec::with_capacity(summands.len());
for (k, s) in summands.iter().enumerate() {
let mut incl = Vec::with_capacity(n);
let mut proj = Vec::with_capacity(n);
for (v, &offset) in offsets[k].iter().enumerate() {
let mut inc = DenseMat::zero(s.dim_vector()[v], sum.dim_vector()[v]);
let mut prj = DenseMat::zero(sum.dim_vector()[v], s.dim_vector()[v]);
for i in 0..s.dim_vector()[v] {
inc.set(i, offset + i, field.one());
prj.set(offset + i, i, field.one());
}
incl.push(inc);
proj.push(prj);
}
inclusions.push(Morphism::new_unchecked(s, &sum, incl));
projections.push(Morphism::new_unchecked(&sum, s, proj));
}
(sum, inclusions, projections)
}
pub(crate) fn summand_sum(
algebra: &Arc<Algebra>,
vertices: &[u32],
build: fn(&Arc<Algebra>, u32) -> Module,
) -> Module {
match vertices {
[] => Module::zero(algebra),
[vertex] => build(algebra, *vertex),
_ => {
let parts: Vec<Module> = vertices.iter().map(|&v| build(algebra, v)).collect();
direct_sum(&parts.iter().collect::<Vec<_>>()).0
}
}
}
#[cfg(test)]
mod tests;