|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
It's Easy to Compute Exactly, but Hard to Minimize Fill-in
This talk will present two types of results concerning matrix
decompositions over the rational numbers. Basically, just think of
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.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.3392 | admin login