Event Details
Sky Background

Welcome to UD

From student events and academic activities to the performing arts and athletic competitions, @UD is the campus hub where you can find everything happening at the University of Delaware.

Events

Facebook Foursquare YouTube Twitter Share this page

CIS SIGTheory

Monday, January 21, 2013 at 11:00am to 12:00pm

Smith Hall, Room 426 Smith Hall, University of Delaware, Newark, DE 19716, USA

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

Share

Subscribe
Event Type

Academics, College of Engineering, Lectures & Programs, Students, Lectures and Programs, Community

Calendar

Group

ENGR - Computer & Information Sciences

Hashtag

#cis_sigtheory

Contact Email

saunders@udel.edu

Contact Name

Dr. David Saunders

Contact Phone

302-831-6238

Recent Activity

People Going

Getting Here

Facebook Foursquare YouTube Twitter