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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Mittagsseminar Talk Information

Date and Time: Thursday, September 15, 2011, 12:15 pm

Duration: 30 minutes

Location: ML J37.1

Speaker: Philipp Hupp (TU München)

On the I/O Complexity of Stencil Computations on 2 Dimensional Grids

Over the past years computer architecture has changed and the gap between floating point performance and memory bandwidth has expanded. Furthermore the size of datasets increases continuously. Therefore the bottleneck limiting the performance of many computations seems to be more and more given by the memory subsystem. Important kernels in scientific computing are stencil computations. They can be used to model the evaluation of an interpolation function or solving a partial differential equation. While memory efficient algorithms to evaluate stencils are usually known, they have not been studied from an theoretical I/O point of view and the lower bounds are missing. Here we derive the first two terms of the I/O complexity of the 5-point stencil which arises when differential quotients are approximated in two dimensions. The research prepares future analysis of stencil computations in higher dimensions and on sparse grids, a variation of grids that reduce the number of grid points to tackle high dimensional problems.

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