use crate::endo::{EndoAlgebra, SplitMix64};
use crate::field::Fp;
use crate::hom::{Morphism, identity, submodule_with_inclusion};
use crate::linalg::DenseMat;
use crate::module::Module;
use crate::profile::{Site, hit_module};
use super::outcome::{Certificate, Decomposition};
use super::split::Split;
const FITTING_ATTEMPTS: u32 = 64;
pub(crate) const DECOMPOSE_SEED: u64 = 0x000a_0512_a11d_e12b;
pub fn decompose(m: &Module) -> Decomposition {
let root = (!m.is_zero()).then(|| EndoAlgebra::new(m));
decompose_with_root_endo(m, root)
}
pub(crate) fn decompose_with_root_endo(m: &Module, root: Option<EndoAlgebra>) -> Decomposition {
hit_module(Site::Decompose, m);
let mut rng = SplitMix64(DECOMPOSE_SEED);
let mut parts = Vec::new();
if let Some(endo) = root {
split_recursively(m, endo, identity(m), identity(m), &mut rng, &mut parts);
}
let mut summands = Vec::with_capacity(parts.len());
let mut inclusions = Vec::with_capacity(parts.len());
let mut projections = Vec::with_capacity(parts.len());
let mut certificates = Vec::with_capacity(parts.len());
let mut endos = Vec::with_capacity(parts.len());
for part in parts {
summands.push(part.summand);
inclusions.push(part.include);
projections.push(part.project);
certificates.push(part.certificate);
endos.push(part.endo);
}
let split = Split::new(m, summands, inclusions, projections)
.expect("recursive splits compose to a verified split");
Decomposition::from_parts(split, certificates, endos)
}
struct Part {
summand: Module,
endo: EndoAlgebra,
include: Morphism,
project: Morphism,
certificate: Certificate,
}
fn split_recursively(
m: &Module,
endo: EndoAlgebra,
include: Morphism,
project: Morphism,
rng: &mut SplitMix64,
out: &mut Vec<Part>,
) {
if endo.is_local() {
finish_part(m, endo, include, project, Certificate::Indecomposable, out);
return;
}
let split = deterministic_split(m, &endo, rng)
.or_else(|| singular_split(m, &endo, rng))
.or_else(|| fitting_split(m, &endo, rng));
let Some(split) = split else {
finish_part(
m,
endo,
include,
project,
Certificate::Undetermined {
attempts: FITTING_ATTEMPTS,
},
out,
);
return;
};
for k in 0..split.summands().len() {
let summand = &split.summands()[k];
if summand.is_zero() {
continue;
}
let summand_endo = EndoAlgebra::from_summand(
summand,
&endo,
&split.inclusions()[k],
&split.projections()[k],
);
let summand_include = split.inclusions()[k]
.then(&include)
.expect("inclusion chains compose");
let summand_project = project
.then(&split.projections()[k])
.expect("projection chains compose");
split_recursively(
summand,
summand_endo,
summand_include,
summand_project,
rng,
out,
);
}
}
fn finish_part(
m: &Module,
endo: EndoAlgebra,
include: Morphism,
project: Morphism,
certificate: Certificate,
out: &mut Vec<Part>,
) {
out.push(Part {
summand: m.clone(),
endo,
include,
project,
certificate,
});
}
pub(crate) fn deterministic_split(
m: &Module,
endo: &EndoAlgebra,
rng: &mut SplitMix64,
) -> Option<Split> {
let e = endo.morphism(&endo.split_idempotent(rng)?);
let field = m.field();
let n = m.algebra().quiver().num_vertices();
let mut first = Vec::with_capacity(n as usize);
let mut second = Vec::with_capacity(n as usize);
for v in 0..n {
let ev = e.map_at(v);
let mut complement = DenseMat::identity(ev.rows());
complement.add_scaled_assign(ev, field.neg(field.one()), &field);
first.push(ev.row_space_basis(&field));
second.push(complement.row_space_basis(&field));
}
split_from_bases(m, first, second)
}
fn singular_split(m: &Module, endo: &EndoAlgebra, rng: &mut SplitMix64) -> Option<Split> {
let coords = endo.singular_element(rng, FITTING_ATTEMPTS)?;
fitting_split_along(m, &endo.morphism(&coords))
}
fn fitting_split(m: &Module, endo: &EndoAlgebra, rng: &mut SplitMix64) -> Option<Split> {
let field = m.field();
let p = field.modulus();
for _ in 0..FITTING_ATTEMPTS {
let coords: Vec<Fp> = (0..endo.dim())
.map(|_| field.elem(rng.below(p) as i64))
.collect();
if let Some(split) = fitting_split_along(m, &endo.morphism(&coords)) {
return Some(split);
}
}
None
}
fn fitting_split_along(m: &Module, phi: &Morphism) -> Option<Split> {
let field = m.field();
let psi = morphism_power(m, phi, m.total_dim());
let n = m.algebra().quiver().num_vertices();
let mut kernel = Vec::with_capacity(n as usize);
let mut image = Vec::with_capacity(n as usize);
for v in 0..n {
kernel.push(psi.map_at(v).left_kernel_basis(&field));
image.push(psi.map_at(v).row_space_basis(&field));
}
if kernel.iter().all(|b| b.rows() == 0) || image.iter().all(|b| b.rows() == 0) {
return None;
}
split_from_bases(m, kernel, image)
}
fn morphism_power(m: &Module, phi: &Morphism, exp: usize) -> Morphism {
binary_power!(phi.clone(), identity(m), exp, |left, right| left
.then(right)
.expect("endomorphisms compose"))
}
fn split_from_bases(m: &Module, first: Vec<DenseMat>, second: Vec<DenseMat>) -> Option<Split> {
let field = m.field();
let n = m.algebra().quiver().num_vertices() as usize;
let mut proj_first = Vec::with_capacity(n);
let mut proj_second = Vec::with_capacity(n);
for v in 0..n {
let k1 = first[v].rows();
let k2 = second[v].rows();
if k1 + k2 != m.dim_vector()[v] {
return None;
}
let stacked = DenseMat::stack(&[&first[v], &second[v]], m.dim_vector()[v]);
let inverse = stacked.inverse(&field)?;
let mut p1 = DenseMat::zero(inverse.rows(), k1);
let mut p2 = DenseMat::zero(inverse.rows(), k2);
for r in 0..inverse.rows() {
for c in 0..k1 {
p1.set(r, c, inverse.get(r, c));
}
for c in 0..k2 {
p2.set(r, c, inverse.get(r, k1 + c));
}
}
proj_first.push(p1);
proj_second.push(p2);
}
let (sub1, incl1) = submodule_with_inclusion(m, first);
let (sub2, incl2) = submodule_with_inclusion(m, second);
let proj1 = Morphism::new_unchecked(m, &sub1, proj_first);
let proj2 = Morphism::new_unchecked(m, &sub2, proj_second);
Split::new(m, vec![sub1, sub2], vec![incl1, incl2], vec![proj1, proj2]).ok()
}