leto-ops 0.45.2

Math, reduction, SIMD, and parallel kernels for Leto arrays
Documentation
//! Integer matrix power `Aᵏ` via exponentiation by squaring.

use super::dense::{identity, mul};
use crate::domain::scalar::Scalar;
use leto::{Array2, ArrayView2, LetoError, Result};

/// Raise a square matrix to a non-negative integer power: `Aᵏ`.
///
/// # Theorem (exponentiation by squaring)
/// Writing `k` in binary as `k = Σᵢ bᵢ 2ⁱ` (`bᵢ ∈ {0,1}`),
/// `Aᵏ = ∏_{i : bᵢ = 1} A^{2ⁱ}`. The repeated-squaring sequence
/// `A^{2⁰}, A^{2¹}, …` is generated by `A^{2^{i+1}} = (A^{2ⁱ})²`, so the product
/// is accumulated in `⌊log₂ k⌋ + 1` squarings and at most as many
/// multiplications — `Θ(log k)` matmuls instead of the naive `k − 1`. By
/// associativity of matrix multiplication the grouping is exact (`A⁰ = I`). ∎
///
/// `matpow` is generic over [`Scalar`], so it is exact for integer matrices as
/// well as floating-point ones (no transcendental functions are used).
///
/// # Errors
/// [`LetoError::ShapeMismatch`] if `matrix` is not square.
pub fn matpow<T: Scalar>(matrix: &ArrayView2<'_, T>, exponent: u32) -> Result<Array2<T>> {
    let [rows, cols] = matrix.shape();
    if rows != cols {
        return Err(LetoError::ShapeMismatch {
            lhs: vec![rows, cols],
            rhs: vec![rows, rows],
        });
    }

    let mut result = identity::<T>(rows); // A⁰ = I
    if exponent == 0 {
        return Ok(result);
    }

    let mut base = matrix.to_contiguous(); // A^{2⁰}
    let mut remaining = exponent;
    loop {
        if remaining & 1 == 1 {
            result = mul(&result.view(), &base.view())?;
        }
        remaining >>= 1;
        if remaining == 0 {
            break;
        }
        base = mul(&base.view(), &base.view())?; // A^{2^{i+1}} = (A^{2ⁱ})²
    }
    Ok(result)
}