Mark Giesbrecht, U Waterloo
Quasideterminants, Degree Bounds and ``Fast'' Algorithms for Matrices of Differential and Difference Polynomials
We look at the problem of computational linear algebra over rings of differential and difference operators, as captured by the Ore polynomials. Many algorithms for computing normal forms of matrices of Ore polynomials have been proposed over the past few years. Examples of such computations include the Hermite (triangular) form, the Jacobson (diagonal) form and the Popov form. While some of these new algorithms are quite effective in practice, the complexity of most of them has not been established.
Our goal has been to develop provably polynomial-time algorithms for these problems, and to develop tools by which to analyze other algorithms. 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 the problem for Ore polynomials more difficult than the analogous problems for commutative polynomials has been the lack of the usual determinantal theory, and basic theorems such as Hadamard's bound, Cramer's rule and Sylvester's identity. We instead apply the quasideterminantal theory of Gelfand and Retakh to Ore polynomials and establish tight degree bounds on these determinant-like objects.
This work is in collaboration with Albert Heinle and Myung Sub Kim
Monday, January 21, 2013 at 11:00am to 12:00pm
Smith Hall, Room 426
Smith Hall, University of Delaware, Newark, DE 19716, USA