auslander 0.10.0

Computational representation theory of finite-dimensional bound quiver algebras
Documentation
use std::sync::Arc;

use crate::algebra::{Algebra, BasisIdx};
use crate::completion::CompletionLimits;
use crate::field::{Fp, PrimeField};
use crate::linalg::DenseMat;
use crate::quiver::{ArrowId, Quiver};
use crate::relation::{Presentation, Relation};

fn add_entry(matrix: &mut DenseMat, row: usize, column: usize, value: Fp, field: &PrimeField) {
    matrix.set(row, column, field.add(matrix.get(row, column), value));
}

fn full_signed(value: Fp, negative: bool, field: &PrimeField) -> Fp {
    if negative { field.neg(value) } else { value }
}

fn full_tuples(dimension: usize, degree: usize) -> Vec<Vec<BasisIdx>> {
    let mut tuples = vec![Vec::new()];
    for _ in 0..degree {
        let mut next = Vec::with_capacity(tuples.len() * dimension);
        for tuple in tuples {
            for basis in 0..dimension {
                let mut extended = tuple.clone();
                extended.push(basis);
                next.push(extended);
            }
        }
        tuples = next;
    }
    tuples
}

fn full_rank(tuple: &[BasisIdx], dimension: usize) -> usize {
    tuple
        .iter()
        .fold(0, |rank, &basis| rank * dimension + basis)
}

fn add_full_product(
    matrix: &mut DenseMat,
    row: usize,
    target_rank: usize,
    dimension: usize,
    product: &[(BasisIdx, Fp)],
    negative: bool,
    field: &PrimeField,
) {
    for &(output, coefficient) in product {
        add_entry(
            matrix,
            row,
            target_rank * dimension + output,
            full_signed(coefficient, negative, field),
            field,
        );
    }
}

fn full_differential(algebra: &Algebra, degree: usize) -> DenseMat {
    let field = algebra.field();
    let dimension = algebra.dim();
    let source = full_tuples(dimension, degree);
    let target = full_tuples(dimension, degree + 1);
    let mut differential = DenseMat::zero(source.len() * dimension, target.len() * dimension);
    for (target_rank, tuple) in target.iter().enumerate() {
        for output in 0..dimension {
            if degree == 0 {
                add_full_product(
                    &mut differential,
                    output,
                    target_rank,
                    dimension,
                    &algebra.mul_basis(tuple[0], output),
                    false,
                    &field,
                );
                add_full_product(
                    &mut differential,
                    output,
                    target_rank,
                    dimension,
                    &algebra.mul_basis(output, tuple[0]),
                    true,
                    &field,
                );
                continue;
            }
            let first = full_rank(&tuple[1..], dimension) * dimension + output;
            add_full_product(
                &mut differential,
                first,
                target_rank,
                dimension,
                &algebra.mul_basis(tuple[0], output),
                false,
                &field,
            );
            for i in 1..=degree {
                let mut shortened = Vec::with_capacity(degree);
                shortened.extend_from_slice(&tuple[..i - 1]);
                for &(middle, coefficient) in &algebra.mul_basis(tuple[i - 1], tuple[i]) {
                    shortened.push(middle);
                    shortened.extend_from_slice(&tuple[i + 1..]);
                    let row = full_rank(&shortened, dimension) * dimension + output;
                    add_entry(
                        &mut differential,
                        row,
                        target_rank * dimension + output,
                        full_signed(coefficient, i % 2 == 1, &field),
                        &field,
                    );
                    shortened.truncate(i - 1);
                }
            }
            let last = full_rank(&tuple[..degree], dimension) * dimension + output;
            add_full_product(
                &mut differential,
                last,
                target_rank,
                dimension,
                &algebra.mul_basis(output, tuple[degree]),
                (degree + 1) % 2 == 1,
                &field,
            );
        }
    }
    differential
}

pub(super) fn full_bar_dimensions(algebra: &Algebra, max_degree: usize) -> Vec<usize> {
    let field = algebra.field();
    let mut dimensions = Vec::with_capacity(max_degree + 1);
    let mut previous: Option<DenseMat> = None;
    for degree in 0..=max_degree {
        let differential = full_differential(algebra, degree);
        if let Some(previous) = &previous {
            assert!(
                previous
                    .mul(&differential, &field)
                    .entries_u64()
                    .iter()
                    .flatten()
                    .all(|&x| x == 0)
            );
        }
        let cocycles = differential.left_kernel_basis(&field);
        let coboundaries =
            previous.map_or(0, |matrix: DenseMat| matrix.row_space_basis(&field).rows());
        dimensions.push(cocycles.rows() - coboundaries);
        previous = Some(differential);
    }
    dimensions
}

pub(super) fn center_dimension(algebra: &Algebra) -> usize {
    let field = algebra.field();
    let dimension = algebra.dim();
    let mut equations = DenseMat::zero(dimension, dimension * dimension);
    for central in 0..dimension {
        for basis in 0..dimension {
            for &(output, coefficient) in &algebra.mul_basis(central, basis) {
                add_entry(
                    &mut equations,
                    central,
                    basis * dimension + output,
                    coefficient,
                    &field,
                );
            }
            for &(output, coefficient) in &algebra.mul_basis(basis, central) {
                add_entry(
                    &mut equations,
                    central,
                    basis * dimension + output,
                    field.neg(coefficient),
                    &field,
                );
            }
        }
    }
    equations.left_kernel_basis(&field).rows()
}

fn add_outer_product_pair(
    equations: &mut DenseMat,
    algebra: &Algebra,
    field: &PrimeField,
    dimension: usize,
    left: usize,
    right: usize,
) {
    for &(middle, coefficient) in &algebra.mul_basis(left, right) {
        for output in 0..dimension {
            add_entry(
                equations,
                middle * dimension + output,
                (left * dimension + right) * dimension + output,
                coefficient,
                field,
            );
        }
    }
}

fn add_outer_action_pair(
    equations: &mut DenseMat,
    algebra: &Algebra,
    field: &PrimeField,
    dimension: usize,
    left: usize,
    right: usize,
) {
    for output in 0..dimension {
        for &(product, coefficient) in &algebra.mul_basis(output, right) {
            add_entry(
                equations,
                left * dimension + output,
                (left * dimension + right) * dimension + product,
                field.neg(coefficient),
                field,
            );
        }
        for &(product, coefficient) in &algebra.mul_basis(left, output) {
            add_entry(
                equations,
                right * dimension + output,
                (left * dimension + right) * dimension + product,
                field.neg(coefficient),
                field,
            );
        }
    }
}

fn outer_equations(algebra: &Algebra, field: &PrimeField, dimension: usize) -> DenseMat {
    let mut equations = DenseMat::zero(dimension * dimension, dimension * dimension * dimension);
    for left in 0..dimension {
        for right in 0..dimension {
            add_outer_product_pair(&mut equations, algebra, field, dimension, left, right);
            add_outer_action_pair(&mut equations, algebra, field, dimension, left, right);
        }
    }
    equations
}

fn add_inner_pair(
    inner: &mut DenseMat,
    algebra: &Algebra,
    field: &PrimeField,
    dimension: usize,
    generator: usize,
    input: usize,
) {
    for &(output, coefficient) in &algebra.mul_basis(input, generator) {
        add_entry(
            inner,
            generator,
            input * dimension + output,
            coefficient,
            field,
        );
    }
    for &(output, coefficient) in &algebra.mul_basis(generator, input) {
        add_entry(
            inner,
            generator,
            input * dimension + output,
            field.neg(coefficient),
            field,
        );
    }
}

fn inner_equations(algebra: &Algebra, field: &PrimeField, dimension: usize) -> DenseMat {
    let mut inner = DenseMat::zero(dimension, dimension * dimension);
    for generator in 0..dimension {
        for input in 0..dimension {
            add_inner_pair(&mut inner, algebra, field, dimension, generator, input);
        }
    }
    inner
}

pub(super) fn outer_derivation_dimension(algebra: &Algebra) -> usize {
    let field = algebra.field();
    let dimension = algebra.dim();
    let equations = outer_equations(algebra, &field, dimension);
    let derivations = equations.left_kernel_basis(&field);
    let inner = inner_equations(algebra, &field, dimension).row_space_basis(&field);
    assert!(
        inner
            .mul(&equations, &field)
            .entries_u64()
            .iter()
            .flatten()
            .all(|&value| value == 0)
    );
    assert!(inner.rows() <= derivations.rows());
    derivations.rows() - inner.rows()
}

pub(super) fn inhomogeneous_dual_numbers(field: PrimeField) -> Arc<Algebra> {
    let quiver = Quiver::new(1, &[(0, 0)]).unwrap();
    let relation = Relation::new(
        &quiver,
        field,
        vec![
            (field.one(), vec![ArrowId(0), ArrowId(0)]),
            (field.one(), vec![ArrowId(0), ArrowId(0), ArrowId(0)]),
        ],
    )
    .unwrap();
    let nilpotence = Relation::new(
        &quiver,
        field,
        vec![(
            field.one(),
            vec![ArrowId(0), ArrowId(0), ArrowId(0), ArrowId(0)],
        )],
    )
    .unwrap();
    Algebra::new(
        Presentation::new(quiver, field, vec![relation, nilpotence]).unwrap(),
        &CompletionLimits::default(),
    )
    .unwrap()
}