Date:  11:2012:00, Wednesday, March 25, 2009 
Venue:  FIT Building 1315, Tsinghua University 
Title:  Dynamic Normal Forms and Dynamic Characteristic Polynomial

Speaker:  Gudmund Skovbjerg Frandsen 
Biography: 
Gudmund Skovbjerg Frandsen is a postdoctoral research fellow in department of computer science in University of Aarhus in Denmark. His research interest is in the area of randomized algorithms and dynamic algorithms.

Abstract: 
We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case our algorithm supports rankone updates in almost quadratic randomized time and queries in constant time, whereas in the general case the time in addition grows linearly in the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem in time that additionally grows linearly with the logarithm of the inverse relative error. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithms the hardness of the problem is studied. For the symmetric case we present a quadratic lower bound for rankone updates and a linear lower bound for element updates.
Joint work with Piotr Sankowski
