Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 12, 2010, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Yves Brise
This talk will present two types of results concerning matrix decompositions over the rational numbers. Basically, just think of Gaussian elimination.
In the first part we will discuss the fact that Gaussian elimination is strongly polynomial. It is straight-forward that Gaussian elimination is polynomial in the arithmetic model (counting arithmetic operations), but not clear a priori that it is possible in polynomial time with respect to the encoding length of the matrix. This result opens the door for doing exact computations efficiently.
The second part will be concerned with decomposing sparse matrices, i.e., matrices having a lot of zero entries. During the decomposition of such matrices, it can happen that a lot of non-zeros are created. This is refered to as fill-in in the literature. Using an elegant graph theoretical approach it is possible to show that minimizing the fill-in is actually NP-hard for symmetric positive definite matrices.
Automatic MiSe System Software Version 1.4803M | admin login