Computational Algebra Seminar: Monagan -- Factoring Multivariate Polynomials given by Black Boxes

Title: Factoring Multivariate Polynomials given by Black Boxes.
Speaker: Michael Monagan, Department of Mathematics, Simon Fraser University
Time & Place: 15.00-16.00, Thursday 12 March, SMRI Seminar Rm
Abstract:
The black box model for computing with polynomials was introduced
to Computer Algebra by Kaltofen and Trager in 1990.  Kaltofen's PhD
student Angel Diaz subsequently implemented GCD and factorization
algorithms for polynomials represented by a black box in C++.  Little work
has been done since and no Computer Algebra Systems are using the black
box model.

In the last 5 years we have designed and implemented a black box
algorithm for factoring a polynomial given by a black box.  We have used
it to compute the factors of determinants of matrices of polynomials.

In the talk I will present the black box model for a polynomial
f in n variables x1,x2,...xn over a field F.  I will explain why it is
more powerful than the standard sparse representation for polynomials, and
how we can compute with it.  Then I'll present our black box polynomial
factorization algorithm with some timing benchmarks to show how good
it is.

This is joint work with my former PhD student Tian Chen.