Title: Quasideterminants and "Fast" Algorithms for Matrices of Ore Polynomials

Speaker: Prof. Mark Giesbrecht, University of Waterloo

Time and Location: Wednesday, November 27, 2013
                   2:00 pm, Seminar room pond, RISC, Hagenberg


Abstract

We look at the problem of computational linear algebra over the ring
of Ore polynomials. A number of algorithms for computing normal forms
of matrices of Ore polynomials have been proposed over the past few
years. Examples include the Hermite (triangular) form and Jacobson
(diagonal) form, which are canonical for one-sided and two-sided
unimodular equivalence respectively. While some of these new
algorithms are effective in practice, their complexity has not been
established. Our goal here is both to develop provably polynomial-time
algorithms for these problems, and also to establish effective
mathematical tools for matrices of Ore polynomials. We will outline
algorithms for the Hermite and Jacobson form which require time
polynomial in the dimension, degree and coefficient-size of the input
matrices.

One aspect which has made problems for matrices of Ore polynomials has
been the lack of a determinantal theory, and basic theorems such as
Hadamard's bound, Cramer's rule and Sylvester's identity. We apply the
quasideterminantal theory of Gelfand and Retakh to Ore polynomials and
establish tight degree bounds on these determinant-like objects. These
are then applied to bound solution sizes and complexities in our algorithms.

We also explore the rigorous use of randomization in our computations,
which has been highly effective for preconditioners for fast
algorithms in linear algebra over the commutative polynomials. Our
algorithms for the Jacobson form of a matrix of Ore polynomials 
uses a simple randomization to simplify the computation to an easier
"generic" case.