auslander 0.8.0

Computational representation theory of finite-dimensional bound quiver algebras
Documentation
use crate::algebra::Algebra;

use super::super::cochain::next_usize;
use super::super::limits::{BarCoordinate, BarStage};
use super::tuple::walk_tuples;
use super::{Budget, BuildResult, Ledger};

#[derive(Clone, Debug)]
pub(crate) struct Layout {
    pub(crate) coordinates: Vec<BarCoordinate>,
    pub(crate) offsets: Vec<usize>,
}

#[derive(Clone, Debug)]
pub(crate) struct TupleOffsets {
    pub(crate) offsets: Vec<usize>,
    pub(crate) segments: Vec<(usize, u32, u32)>,
}

#[derive(Clone, Debug)]
pub(crate) struct Shape {
    pub(crate) tuples: usize,
    pub(crate) cochain_dim: usize,
    pub(crate) starts: Vec<usize>,
}

fn square_work(n: usize, ledger: &Ledger, degree: usize) -> BuildResult<u128> {
    let budget = ledger.budget(degree, BarStage::Shape);
    let square = budget.product([n as u128, n as u128])?;
    let cubic = budget.product([square, n as u128])?;
    budget.sum(cubic, square)
}

fn reserve_power_shape(vertices: usize, ledger: &mut Ledger, degree: usize) -> BuildResult<()> {
    ledger.work(
        degree,
        BarStage::Shape,
        square_work(vertices, ledger, degree)?,
    )?;
    let budget = ledger.budget(degree, BarStage::Shape);
    let entries = budget.product([vertices as u128, vertices as u128])?;
    budget.size(entries).map(|_| ())
}

fn power_entry(
    source: usize,
    target: usize,
    current: Option<&[Vec<usize>]>,
    algebra: &Algebra,
    budget: Budget<'_>,
) -> BuildResult<usize> {
    let mut total = 0u128;
    let vertices = algebra.quiver().num_vertices() as usize;
    for middle in 0..vertices {
        let current_count =
            current.map_or(usize::from(source == middle), |power| power[source][middle]);
        let radical_count = algebra
            .paths_between(middle as u32, target as u32)
            .len()
            .checked_sub(usize::from(middle == target))
            .expect("every vertex idempotent is a normal word");
        let product = budget.product([current_count as u128, radical_count as u128])?;
        total = budget.sum(total, product)?;
    }
    budget.size(total)
}

pub(crate) fn advance_power(
    current: Option<&[Vec<usize>]>,
    algebra: &Algebra,
    ledger: &mut Ledger,
    degree: usize,
) -> BuildResult<Vec<Vec<usize>>> {
    let vertices = algebra.quiver().num_vertices() as usize;
    reserve_power_shape(vertices, ledger, degree)?;
    let budget = ledger.budget(degree, BarStage::Shape);
    let mut next = vec![vec![0; vertices]; vertices];
    for (source, next_row) in next.iter_mut().enumerate() {
        for (target, entry) in next_row.iter_mut().enumerate() {
            *entry = power_entry(source, target, current, algebra, budget)?;
        }
    }
    Ok(next)
}

fn shape_row(
    algebra: &Algebra,
    budget: Budget<'_>,
    source: usize,
    row: &[usize],
) -> BuildResult<(u128, u128, usize)> {
    let mut tuples = 0u128;
    let mut from_source = 0u128;
    let mut cochain_dim = 0u128;
    for (target, &count) in row.iter().enumerate() {
        tuples = budget.sum(tuples, count as u128)?;
        from_source = budget.sum(from_source, count as u128)?;
        let addend = budget.product([
            count as u128,
            algebra.paths_between(source as u32, target as u32).len() as u128,
        ])?;
        cochain_dim = budget.sum(cochain_dim, addend)?;
    }
    let start = budget.size(from_source)?;
    Ok((tuples, cochain_dim, start))
}

fn shape_totals(
    algebra: &Algebra,
    radical_power: &[Vec<usize>],
    budget: Budget<'_>,
) -> BuildResult<(usize, usize, Vec<usize>)> {
    let mut tuples = 0u128;
    let mut cochain_dim = 0u128;
    let mut starts = Vec::with_capacity(radical_power.len());
    for (source, row) in radical_power.iter().enumerate() {
        let (row_tuples, row_cochain_dim, start) = shape_row(algebra, budget, source, row)?;
        tuples = budget.sum(tuples, row_tuples)?;
        cochain_dim = budget.sum(cochain_dim, row_cochain_dim)?;
        starts.push(start);
    }
    let tuples = budget.size(tuples)?;
    let cochain_dim = budget.size(cochain_dim)?;
    Ok((tuples, cochain_dim, starts))
}

pub(crate) fn measure_shape(
    algebra: &Algebra,
    radical_power: &[Vec<usize>],
    ledger: &mut Ledger,
    degree: usize,
) -> BuildResult<Shape> {
    let budget = ledger.budget(degree, BarStage::Shape);
    let (tuples, cochain_dim, starts) = shape_totals(algebra, radical_power, budget)?;
    ledger.shape(degree, tuples, cochain_dim)?;
    Ok(Shape {
        tuples,
        cochain_dim,
        starts,
    })
}

pub(crate) fn measure_identity_shape(
    algebra: &Algebra,
    ledger: &mut Ledger,
    degree: usize,
) -> BuildResult<Shape> {
    let budget = ledger.budget(degree, BarStage::Shape);
    let vertices = algebra.quiver().num_vertices() as usize;
    let mut cochain_dim = 0u128;
    for vertex in 0..vertices {
        cochain_dim = budget.sum(
            cochain_dim,
            algebra.paths_between(vertex as u32, vertex as u32).len() as u128,
        )?;
    }
    let cochain_dim = budget.size(cochain_dim)?;
    ledger.shape(degree, vertices, cochain_dim)?;
    Ok(Shape {
        tuples: vertices,
        cochain_dim,
        starts: vec![1; vertices],
    })
}

pub(crate) fn reserve_layout_work(
    current: &Shape,
    next: &Shape,
    degree: usize,
    ledger: &mut Ledger,
) -> BuildResult<()> {
    let budget = ledger.budget(degree, BarStage::Layout);
    let tuple_scan = budget.product([
        next.tuples as u128,
        next_usize(ledger, degree, BarStage::Layout, degree)? as u128,
    ])?;
    let units = budget.sum(tuple_scan, current.cochain_dim as u128)?;
    ledger.work(degree, BarStage::Layout, units)
}

pub(crate) fn build_tuple_offsets(
    algebra: &Algebra,
    degree: usize,
    shape: &Shape,
    starts: &[Vec<usize>],
    ledger: &Ledger,
) -> BuildResult<TupleOffsets> {
    let budget = ledger.budget(degree, BarStage::Layout);
    let capacity = next_usize(ledger, degree, BarStage::Layout, shape.tuples)?;
    let mut offsets = Vec::with_capacity(capacity);
    let mut segments = Vec::new();
    let mut offset = 0usize;
    walk_tuples(
        algebra,
        degree,
        shape.tuples,
        starts,
        |rank, _, source, target| {
            offsets.push(offset);
            let outputs = algebra.paths_between(source, target);
            if !outputs.is_empty() {
                segments.push((rank, source, target));
            }
            offset = budget.size(budget.sum(offset as u128, outputs.len() as u128)?)?;
            Ok::<(), super::Stop>(())
        },
    )?;
    offsets.push(offset);
    debug_assert_eq!(offset, shape.cochain_dim);
    debug_assert_eq!(offsets.len(), capacity);
    Ok(TupleOffsets { offsets, segments })
}

pub(crate) fn build_layout(
    algebra: &Algebra,
    shape: &Shape,
    tuple_offsets: TupleOffsets,
) -> Layout {
    let mut coordinates = Vec::with_capacity(shape.cochain_dim);
    for (rank, source, target) in tuple_offsets.segments {
        assert_eq!(coordinates.len(), tuple_offsets.offsets[rank]);
        coordinates.extend(algebra.paths_between(source, target).iter().map(|&output| {
            BarCoordinate {
                tuple_rank: rank,
                output,
            }
        }));
    }
    assert_eq!(coordinates.len(), shape.cochain_dim);
    assert_eq!(tuple_offsets.offsets.len(), shape.tuples + 1);
    Layout {
        coordinates,
        offsets: tuple_offsets.offsets,
    }
}