Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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**: OAT S15/S16/S17

**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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 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.4803M | admin login