Fast Path Opportunities Assessment

Topic: internal.planning.fast-path-opportunities

Comprehensive analysis of 15+ high-priority opportunities for IntPoly and NumericMatrix fast-paths across MathHook's algebra, calculus, and matrix operations. Identifies concrete performance improvements through direct numeric computation instead of Expression tree operations.

Fast Path Opportunities Assessment

Date: 2025-12-06T21:53 Context: Post-IntPoly implementation analysis Goal: Identify remaining opportunities for fast-path optimizations

Executive Summary

This document catalogs 15+ high-priority opportunities for IntPoly and NumericMatrix fast-paths across MathHook's algebra, calculus, and matrix operations.

Key Insight: Many operations currently use Expression trees when they could operate entirely on numeric types (IntPoly, RationalPoly, NumericMatrix).

Potential Impact: 10-100x speedups for common operations like:

Polynomial GCD and factorization
System of equations solving
Matrix decompositions and solving
Differentiation and integration

Methodology

For each opportunity, we assess:

Current State: How the operation works today
Opportunity: What fast-path could be added
Impact: Expected performance improvement
Complexity: Implementation difficulty (Low/Medium/High)
Priority: P0 (critical) to P3 (nice-to-have)

Priority Levels:

P0: Critical bottlenecks, used in hot paths
P1: High-frequency operations, significant impact
P2: Moderate impact, less common operations
P3: Niche use cases, polish/completeness

Category 1: Polynomial Operations

1. Polynomial GCD

File: crates/mathhook-core/src/algebra/gcd.rs

Current State:

Expression::gcd() has IntPoly fast-path for univariate integer polynomials
Falls back to symbolic GCD for rational coefficients
Symbolic GCD uses Euclidean algorithm on Expression trees

Opportunity: Add RationalPoly fast-path

#![allow(unused)]
fn main() {
// Current fallback
if vars.len() == 1 {
    // Try IntPoly
    if IntPoly::can_convert(self, &vars[0]) { /* ... */ }

    // NEW: Try RationalPoly
    if RationalPoly::can_convert(self, &vars[0]) {
        let p1 = RationalPoly::try_from_expression(self, &vars[0])?;
        let p2 = RationalPoly::try_from_expression(other, &vars[0])?;
        return Ok(p1.gcd(&p2).to_expression(&vars[0]));
    }

    // Fall back to symbolic
    return symbolic_gcd_euclidean(self, other, &vars[0]);
}
}

Impact: 10-50x speedup for rational coefficient polynomials

Complexity: Low (reuse IntPoly pattern)

Priority: P1 (common in symbolic math)

2. Polynomial Division

File: crates/mathhook-core/src/algebra/polynomial_division.rs

Current State:

polynomial_division() has IntPoly fast-path (lines 85-106)
Falls back to symbolic division for rational coefficients

Opportunity: Add RationalPoly fast-path

#![allow(unused)]
fn main() {
// After IntPoly check
if RationalPoly::can_convert(&dividend, var) && RationalPoly::can_convert(&divisor, var) {
    let p_dividend = RationalPoly::try_from_expression(&dividend, var)?;
    let p_divisor = RationalPoly::try_from_expression(&divisor, var)?;

    let (quotient_poly, remainder_poly) = p_dividend.div_rem(&p_divisor);

    return Ok((
        quotient_poly.to_expression(var),
        remainder_poly.to_expression(var),
    ));
}
}

Impact: 10-50x speedup for rational polynomials

Complexity: Low

Priority: P1

3. Polynomial Factorization

File: crates/mathhook-core/src/core/polynomial/algorithms/factorization.rs

Current State:

Square-free factorization operates on Expression trees
Calls GCD and division repeatedly (each call bridges Expression ↔ IntPoly)

Opportunity: Operate entirely in Poly

#![allow(unused)]
fn main() {
// NEW: Internal implementation
fn square_free_factorization_poly<T: Ring>(poly: &Poly<T>) -> Vec<(Poly<T>, usize)> {
    let derivative = poly.derivative();
    let g = poly.gcd(&derivative);
    let (h, _) = poly.div_rem(&g);

    // Yun's algorithm - ALL in Poly<T>, no conversions
    let mut factors = Vec::new();
    let mut current_g = g;
    let mut current_h = h;
    let mut multiplicity = 1;

    while !current_h.is_one() {
        let s = current_g.gcd(&current_h);
        let (factor, _) = current_h.div_rem(&s);

        if !factor.is_one() {
            factors.push((factor, multiplicity));
        }

        current_g = current_g.div_rem(&s).0;
        current_h = s;
        multiplicity += 1;
    }

    factors
}

// Public wrapper converts once at entry/exit
pub fn square_free_factorization(
    poly: &Expression,
    var: &Symbol,
) -> Result<Vec<(Expression, usize)>> {
    if IntPoly::can_convert(poly, var) {
        let p = IntPoly::try_from_expression(poly, var)?;
        let factors = square_free_factorization_poly(&p);
        return Ok(factors.into_iter()
            .map(|(f, m)| (f.to_expression(var), m))
            .collect());
    }
    // ... RationalPoly, symbolic fallback
}
}

Impact: 50-200x speedup (eliminates O(n) conversions for multiplicity n)

Complexity: Medium (refactor existing algorithm)

Priority: P0 (hot path in factorization)

4. Polynomial Evaluation

File: crates/mathhook-core/src/core/expression/mod.rs (eval methods)

Current State:

Expression.eval() walks entire Expression tree
Polynomial evaluation is O(n) tree walk even for simple polynomials

Opportunity: Detect polynomial structure, evaluate with Horner's method

#![allow(unused)]
fn main() {
impl Expression {
    pub fn eval(&self, var: &Symbol, value: &Expression) -> Expression {
        // NEW: Try polynomial fast-path
        if self.is_polynomial_in(&[var.clone()]) {
            if let Some(poly) = IntPoly::try_from_expression(self, var) {
                if let Ok(val_i64) = value.as_integer() {
                    return Expression::integer(poly.evaluate_i64(val_i64));
                }
            }
            // Try RationalPoly if IntPoly fails
        }

        // Fall back to tree walk
        self.eval_tree(var, value)
    }
}
}

Impact: 5-20x speedup for polynomial evaluation

Complexity: Low

Priority: P1 (common operation)

5. Polynomial Derivative (Symbolic)

File: crates/mathhook-core/src/calculus/derivatives/symbolic.rs

Current State:

derivative() walks Expression tree applying rules
For polynomials, this is inefficient (power rule on each term)

Opportunity: Polynomial fast-path using Poly::derivative()

#![allow(unused)]
fn main() {
pub fn derivative(expr: &Expression, var: &Symbol) -> Expression {
    // NEW: Polynomial fast-path
    if expr.is_polynomial_in(&[var.clone()]) {
        if let Some(poly) = IntPoly::try_from_expression(expr, var) {
            return poly.derivative().to_expression(var);
        }
        if let Some(poly) = RationalPoly::try_from_expression(expr, var) {
            return poly.derivative().to_expression(var);
        }
    }

    // Fall back to symbolic rules
    derivative_symbolic(expr, var)
}
}

Impact: 10-50x speedup for polynomial derivatives

Complexity: Low

Priority: P1

6. Polynomial Integration (Definite)

File: crates/mathhook-core/src/calculus/integration/definite.rs

Current State:

Definite integration uses symbolic integration + evaluation
For polynomials, this is overkill

Opportunity: Direct polynomial antiderivative + numeric evaluation

#![allow(unused)]
fn main() {
pub fn definite_integral(
    expr: &Expression,
    var: &Symbol,
    lower: &Expression,
    upper: &Expression,
) -> Result<Expression> {
    // NEW: Polynomial fast-path
    if expr.is_polynomial_in(&[var.clone()]) {
        if let (Some(poly), Ok(a), Ok(b)) = (
            IntPoly::try_from_expression(expr, var),
            lower.as_integer(),
            upper.as_integer(),
        ) {
            let antiderivative = poly.antiderivative();
            let f_b = antiderivative.evaluate_i64(b);
            let f_a = antiderivative.evaluate_i64(a);
            return Ok(Expression::integer(f_b - f_a));
        }
    }

    // Fall back to symbolic
    definite_integral_symbolic(expr, var, lower, upper)
}
}

Impact: 20-100x speedup for definite polynomial integrals

Complexity: Low (add antiderivative() to Poly)

Priority: P1

Category 2: Matrix Operations

7. Matrix-Vector Multiplication

File: crates/mathhook-core/src/matrices/operations.rs

Current State:

Matrix multiplication operates on Expression elements
Each operation goes through Expression arithmetic

Opportunity: NumericMatrix fast-path for numeric matrices

#![allow(unused)]
fn main() {
impl Matrix {
    pub fn multiply_vector(&self, vec: &[Expression]) -> Vec<Expression> {
        // NEW: Numeric fast-path
        if self.is_numeric() && vec.iter().all(|e| e.is_numeric()) {
            let mat = NumericMatrix::from_expressions(self);
            let vec_numeric: Vec<f64> = vec.iter()
                .map(|e| e.as_numeric().unwrap())
                .collect();

            let result = mat.multiply_vector(&vec_numeric);
            return result.into_iter()
                .map(Expression::from_float)
                .collect();
        }

        // Symbolic multiplication
        self.multiply_vector_symbolic(vec)
    }
}
}

Impact: 50-500x speedup for numeric matrix-vector products

Complexity: Medium (create NumericMatrix type)

Priority: P0 (extremely common operation)

8. Matrix Inversion

File: crates/mathhook-core/src/matrices/inverse.rs

Current State:

Gauss-Jordan elimination on Expression matrices
Each arithmetic operation is symbolic

Opportunity: NumericMatrix fast-path with LU decomposition

#![allow(unused)]
fn main() {
impl Matrix {
    pub fn inverse(&self) -> Result<Matrix> {
        // NEW: Numeric fast-path
        if self.is_numeric() {
            let mat = NumericMatrix::from_expressions(self);
            let inv = mat.inverse_lu()?;
            return Ok(Matrix::from_numeric(&inv));
        }

        // Symbolic Gauss-Jordan
        self.inverse_gauss_jordan()
    }
}
}

Impact: 100-1000x speedup for numeric matrices

Complexity: Medium (implement NumericMatrix with BLAS)

Priority: P0

9. Matrix Determinant

File: crates/mathhook-core/src/matrices/determinant.rs

Current State:

Determinant via cofactor expansion (O(n!)) or LU decomposition on Expression

Opportunity: NumericMatrix fast-path with LU decomposition

#![allow(unused)]
fn main() {
impl Matrix {
    pub fn determinant(&self) -> Expression {
        // NEW: Numeric fast-path
        if self.is_numeric() {
            let mat = NumericMatrix::from_expressions(self);
            let det = mat.determinant_lu();
            return Expression::from_float(det);
        }

        // Symbolic determinant
        self.determinant_symbolic()
    }
}
}

Impact: 50-500x speedup for numeric determinants

Complexity: Low (reuse LU decomposition)

Priority: P1

10. System of Linear Equations

File: crates/mathhook-core/src/algebra/solvers/systems.rs

Current State:

solve_nxn_system() uses Gaussian elimination on Expression matrices
No numeric fast-path

Opportunity: NumericMatrix fast-path for numeric systems

#![allow(unused)]
fn main() {
fn solve_nxn_system(
    &self,
    equations: &[Expression],
    variables: &[Symbol],
) -> SolverResult {
    let (a_matrix, b_vec) = self.build_system_matrix(equations, variables);

    // NEW: Numeric fast-path
    if a_matrix.is_numeric() && b_vec.iter().all(|e| e.is_numeric()) {
        let a_numeric = NumericMatrix::from_expressions(&a_matrix);
        let b_numeric: Vec<f64> = b_vec.iter()
            .map(|e| e.as_numeric().unwrap())
            .collect();

        match a_numeric.solve_lu(&b_numeric) {
            Ok(solution) => {
                let expr_solution: Vec<Expression> = solution.into_iter()
                    .map(Expression::from_float)
                    .collect();
                return SolverResult::Multiple(expr_solution);
            }
            Err(_) => return SolverResult::NoSolution,
        }
    }

    // Symbolic Gaussian elimination
    self.solve_nxn_system_symbolic(&a_matrix, &b_vec)
}
}

Impact: 50-500x speedup for numeric systems

Complexity: Medium

Priority: P0

Category 3: Algebraic Operations

11. Rational Function Simplification

File: crates/mathhook-core/src/algebra/rational.rs

Current State:

Rational simplification uses Expression GCD
For polynomial rationals, this is inefficient

Opportunity: Poly fast-path for polynomial numerator/denominator

#![allow(unused)]
fn main() {
pub fn simplify_rational(
    numerator: &Expression,
    denominator: &Expression,
) -> (Expression, Expression) {
    // NEW: Polynomial fast-path
    if let Some(var) = common_variable(numerator, denominator) {
        if let (Some(num_poly), Some(den_poly)) = (
            IntPoly::try_from_expression(numerator, &var),
            IntPoly::try_from_expression(denominator, &var),
        ) {
            let gcd = num_poly.gcd(&den_poly);
            let (simplified_num, _) = num_poly.div_rem(&gcd);
            let (simplified_den, _) = den_poly.div_rem(&gcd);

            return (
                simplified_num.to_expression(&var),
                simplified_den.to_expression(&var),
            );
        }
    }

    // Symbolic GCD
    simplify_rational_symbolic(numerator, denominator)
}
}

Impact: 10-50x speedup for polynomial rationals

Complexity: Low

Priority: P1

12. Partial Fraction Decomposition

File: crates/mathhook-core/src/algebra/partial_fractions.rs

Current State:

Partial fractions uses symbolic operations throughout
Factorization, polynomial division, solving for coefficients all symbolic

Opportunity: Multi-level fast-path strategy

#![allow(unused)]
fn main() {
pub fn partial_fraction_decomposition(
    numerator: &Expression,
    denominator: &Expression,
    var: &Symbol,
) -> Result<Vec<RationalTerm>> {
    // Step 1: Factor denominator (uses square-free fast-path)
    let factors = square_free_factorization(denominator, var)?;

    // Step 2: For each factor, solve for coefficients
    // NEW: Use Poly<T> operations instead of symbolic
    if IntPoly::can_convert(numerator, var) {
        let num_poly = IntPoly::try_from_expression(numerator, var)?;

        let mut terms = Vec::new();
        for (factor, multiplicity) in factors {
            let factor_poly = IntPoly::try_from_expression(&factor, var)?;

            // Solve for coefficients using polynomial arithmetic
            let coeffs = solve_coefficients_poly(&num_poly, &factor_poly, multiplicity);

            terms.extend(coeffs);
        }

        return Ok(terms);
    }

    // Symbolic fallback
    partial_fraction_symbolic(numerator, denominator, var)
}
}

Impact: 20-100x speedup for polynomial partial fractions

Complexity: Medium (refactor coefficient solving)

Priority: P2

13. Polynomial Remainder Theorem

File: crates/mathhook-core/src/algebra/theorems.rs

Current State:

Remainder theorem uses symbolic division

Opportunity: Direct polynomial evaluation (Horner's method)

#![allow(unused)]
fn main() {
pub fn remainder_theorem(
    poly: &Expression,
    divisor_root: &Expression,
    var: &Symbol,
) -> Expression {
    // Remainder when dividing by (x - a) is just p(a)

    // NEW: Polynomial fast-path
    if let Some(p) = IntPoly::try_from_expression(poly, var) {
        if let Ok(a) = divisor_root.as_integer() {
            return Expression::integer(p.evaluate_i64(a));
        }
    }

    // Symbolic evaluation
    poly.eval(var, divisor_root)
}
}

Impact: 5-20x speedup

Complexity: Low

Priority: P2

Category 4: Higher-Level Operations

14. Groebner Basis Computation

File: crates/mathhook-core/src/algebra/groebner/buchberger.rs

Current State:

Buchberger's algorithm operates on multivariate Expression polynomials
S-polynomial computation, reduction all symbolic

Opportunity: Multivariate Poly representation

Complexity: High (requires multivariate polynomial type)

Priority: P3 (complex, lower frequency)

Note: This is a Phase 10+ optimization requiring architectural changes.

15. Resultant and Discriminant

File: crates/mathhook-core/src/algebra/resultant.rs

Current State:

Resultant computed via Sylvester matrix determinant (symbolic)

Opportunity: Polynomial coefficient extraction + numeric determinant

#![allow(unused)]
fn main() {
pub fn resultant(
    poly1: &Expression,
    poly2: &Expression,
    var: &Symbol,
) -> Expression {
    // NEW: Polynomial fast-path
    if let (Some(p1), Some(p2)) = (
        IntPoly::try_from_expression(poly1, var),
        IntPoly::try_from_expression(poly2, var),
    ) {
        let sylvester = build_sylvester_matrix_numeric(&p1, &p2);
        let det = sylvester.determinant_lu();
        return Expression::integer(det as i64);
    }

    // Symbolic resultant
    resultant_symbolic(poly1, poly2, var)
}
}

Impact: 50-200x speedup for polynomial resultants

Complexity: Medium

Priority: P2

Implementation Priorities

Phase 1 (P0 - Critical)

Polynomial Square-Free Factorization (eliminate bridging)
NumericMatrix System Solver (50-500x speedup)
NumericMatrix Inverse (100-1000x speedup)
NumericMatrix-Vector Multiply (50-500x speedup)

Phase 2 (P1 - High Impact)

RationalPoly GCD
RationalPoly Division
Polynomial Evaluation Fast-Path
Polynomial Derivative Fast-Path
Polynomial Integration (Definite)
Matrix Determinant (Numeric)
Rational Function Simplification

Phase 3 (P2 - Moderate Impact)

Partial Fraction Decomposition
Polynomial Remainder Theorem
Resultant/Discriminant

Phase 4 (P3 - Polish/Completeness)

Groebner Basis (requires multivariate Poly)

Performance Impact Estimates

By Operation Category

Category	Current Avg Time	With Fast-Paths	Speedup
Polynomial GCD	500μs	10μs	50x
Polynomial Division	200μs	5μs	40x
Square-Free Factorization	2ms	20μs	100x
Matrix Inversion (10x10)	50ms	50μs	1000x
System Solver (10x10)	30ms	60μs	500x
Polynomial Evaluation	100μs	5μs	20x

Cumulative Impact

Scenario: Symbolic algebra workflow (factor, simplify, solve)

Before Fast-Paths:

Factor polynomial: 2ms
Simplify rational: 1ms
Solve system: 30ms
Total: 33ms

After Fast-Paths:

Factor polynomial: 20μs
Simplify rational: 20μs
Solve system: 60μs
Total: 100μs

Overall Speedup: 330x

Implementation Strategy

Pattern: Poly Generic Operations

For each operation, follow this pattern:

Internal Generic Implementation:

#![allow(unused)]
fn main() {
fn operation_poly<T: Ring>(poly: &Poly<T>, ...) -> Result<Poly<T>> {
    // Operate entirely in Poly<T>, no Expression
}
}

Public Expression Wrapper:

#![allow(unused)]
fn main() {
pub fn operation(expr: &Expression, ...) -> Result<Expression> {
    // Try IntPoly
    if IntPoly::can_convert(expr, var) {
        let p = IntPoly::try_from_expression(expr, var)?;
        let result = operation_poly(&p, ...)?;
        return Ok(result.to_expression(var));
    }

    // Try RationalPoly
    if RationalPoly::can_convert(expr, var) {
        let p = RationalPoly::try_from_expression(expr, var)?;
        let result = operation_poly(&p, ...)?;
        return Ok(result.to_expression(var));
    }

    // Symbolic fallback
    operation_symbolic(expr, ...)
}
}

Test Cross-Language Consistency:

#![allow(unused)]
fn main() {
#[test]
fn test_operation_intpoly_matches_symbolic() {
    let cases = vec![
        (expr!(x^2 + 2*x + 1), ...),
        (expr!(x^3 - 1), ...),
    ];

    for (input, ...) in cases {
        let fast_result = operation_fast_path(&input, ...);
        let symbolic_result = operation_symbolic(&input, ...);
        assert_eq!(fast_result, symbolic_result);
    }
}
}