use super::helpers::{factor_through_epi, negate};
use super::{NonSplitWitness, ShortExactSequence, SplitStatus, SplitWitness};
use crate::decompose::add_morphisms;
use crate::field::{Fp, PrimeField};
use crate::hom::{Morphism, identity};
use crate::linalg::DenseMat;
use crate::quiver::ArrowId;
impl ShortExactSequence {
pub fn split_status(&self) -> SplitStatus {
let field = self.middle.field();
let (a, b) = retraction_system(self);
match a.solve(&b, &field) {
Some(x) => SplitStatus::Split(self.split_witness(&x)),
None => {
let (reduced, pivots) = augmented_with_dual(&a, &b, &field);
let cols = a.cols();
let pivot_row = pivots
.iter()
.position(|&c| c == cols)
.expect("an unsolvable system pivots in the right-side column");
SplitStatus::NonSplit(non_split_witness(&reduced, pivot_row, cols, a.rows()))
}
}
}
pub(crate) fn split_status_one_pass(&self) -> SplitStatus {
let field = self.middle.field();
let (a, b) = retraction_system(self);
let (rows, cols) = (a.rows(), a.cols());
let (reduced, pivots) = augmented_with_dual(&a, &b, &field);
if let Some(pivot_row) = pivots.iter().position(|&c| c == cols) {
return SplitStatus::NonSplit(non_split_witness(&reduced, pivot_row, cols, rows));
}
let mut x = vec![Fp::ZERO; cols];
for (i, &pc) in pivots.iter().enumerate().filter(|&(_, &c)| c < cols) {
x[pc] = reduced.get(i, cols);
}
SplitStatus::Split(self.split_witness(&x))
}
fn split_witness(&self, x: &[Fp]) -> SplitWitness {
let retraction = self.retraction_from_solution(x);
let e_idem = retraction
.then(&self.inclusion)
.expect("the retraction ends at the sub");
let p = add_morphisms(&identity(&self.middle), &negate(&e_idem));
SplitWitness {
section: factor_through_epi(&self.projection, &p),
retraction,
}
}
fn retraction_from_solution(&self, x: &[Fp]) -> Morphism {
let nv = self.middle.algebra().quiver().num_vertices();
let mut maps = Vec::with_capacity(nv as usize);
let mut offset = 0;
for v in 0..nv {
let (de, dn) = (self.middle.dim_at(v), self.sub.dim_at(v));
let block = DenseMat::from_flat(de, dn, &x[offset..offset + de * dn]);
offset += de * dn;
maps.push(block);
}
Morphism::new(&self.middle, &self.sub, maps)
.expect("the solved system contains every commuting square")
}
}
fn non_split_witness(
reduced: &DenseMat,
pivot_row: usize,
cols: usize,
rows: usize,
) -> NonSplitWitness {
NonSplitWitness {
dual: (0..rows)
.map(|r| reduced.get(pivot_row, cols + 1 + r))
.collect(),
}
}
fn augmented_with_dual(a: &DenseMat, b: &[Fp], field: &PrimeField) -> (DenseMat, Vec<usize>) {
let (rows, cols) = (a.rows(), a.cols());
let mut aug = DenseMat::zero(rows, cols + 1 + rows);
for (r, &rhs) in b.iter().enumerate() {
for c in 0..cols {
aug.set(r, c, a.get(r, c));
}
aug.set(r, cols, rhs);
aug.set(r, cols + 1 + r, field.one());
}
aug.into_rref(field)
}
fn arrow_retraction_rows(
e: &crate::module::Module,
n: &crate::module::Module,
offsets: &[usize],
total: usize,
field: &PrimeField,
arrow: ArrowId,
) -> (Vec<Vec<Fp>>, Vec<Fp>) {
let quiver = e.algebra().quiver();
let (s, t) = (quiver.source(arrow), quiver.target(arrow));
let ea = e.map(arrow);
let na = n.map(arrow);
let mut rows = Vec::new();
let mut rhs = Vec::new();
for i in 0..e.dim_at(s) {
for j in 0..n.dim_at(t) {
let mut row = vec![Fp::ZERO; total];
for c in 0..n.dim_at(s) {
let col = offsets[s as usize] + i * n.dim_at(s) + c;
row[col] = field.add(row[col], na.get(c, j));
}
for k in 0..e.dim_at(t) {
let col = offsets[t as usize] + k * n.dim_at(t) + j;
row[col] = field.sub(row[col], ea.get(i, k));
}
rows.push(row);
rhs.push(Fp::ZERO);
}
}
(rows, rhs)
}
fn inclusion_retraction_rows(
sequence: &ShortExactSequence,
offsets: &[usize],
total: usize,
field: &PrimeField,
) -> (Vec<Vec<Fp>>, Vec<Fp>) {
let e = &sequence.middle;
let n = &sequence.sub;
let nv = e.algebra().quiver().num_vertices();
let iota = &sequence.inclusion;
let mut rows = Vec::new();
let mut rhs = Vec::new();
for v in 0..nv {
let iv = iota.map_at(v);
let dn = n.dim_at(v);
for i in 0..dn {
for j in 0..dn {
let mut row = vec![Fp::ZERO; total];
for k in 0..e.dim_at(v) {
let col = offsets[v as usize] + k * dn + j;
row[col] = field.add(row[col], iv.get(i, k));
}
rows.push(row);
rhs.push(field.elem((i == j) as i64));
}
}
}
(rows, rhs)
}
pub(super) fn retraction_system(sequence: &ShortExactSequence) -> (DenseMat, Vec<Fp>) {
let e = &sequence.middle;
let n = &sequence.sub;
let field: PrimeField = e.field();
let quiver = e.algebra().quiver();
let nv = quiver.num_vertices();
let mut offsets = vec![0usize; nv as usize];
let mut total = 0usize;
for vertex in 0..nv {
offsets[vertex as usize] = total;
total += e.dim_at(vertex) * n.dim_at(vertex);
}
let mut rows: Vec<Vec<Fp>> = Vec::new();
let mut rhs: Vec<Fp> = Vec::new();
for idx in 0..quiver.num_arrows() {
let (arrow_rows, arrow_rhs) =
arrow_retraction_rows(e, n, &offsets, total, &field, ArrowId(idx as u32));
rows.extend(arrow_rows);
rhs.extend(arrow_rhs);
}
let (inclusion_rows, inclusion_rhs) =
inclusion_retraction_rows(sequence, &offsets, total, &field);
rows.extend(inclusion_rows);
rhs.extend(inclusion_rhs);
let a = DenseMat::from_rows_with_cols(&rows, total);
(a, rhs)
}
impl SplitWitness {
pub fn verify(&self, sequence: &ShortExactSequence) -> bool {
let_or_false!(Ok(left) = sequence.inclusion.then(&self.retraction));
let_or_false!(Ok(right) = self.section.then(&sequence.projection));
left == identity(&sequence.sub) && right == identity(&sequence.quotient)
}
}
impl NonSplitWitness {
pub fn verify(&self, sequence: &ShortExactSequence) -> bool {
let (a, b) = retraction_system(sequence);
verify_guard!(self.dual.len() == a.rows());
let field = sequence.middle.field();
let y = DenseMat::from_flat(1, self.dual.len(), &self.dual);
let left = y.mul(&a, &field);
let right = y
.mul(&DenseMat::from_flat(b.len(), 1, &b), &field)
.get(0, 0);
left.row(0).iter().all(|value| value.is_zero()) && right == field.one()
}
}