In recent years multilevel techniques have become an important algorithmic paradigm for combinatorial problems. Although the recognition of these ideas as a distinct algorithmic approach is fairly recent, multilevel algorithms have been around for a long time. In many of the older applications, these ideas were used to devise efficient algorithms for easy problems, while in the more recent applications they have been used to provide effective heuristics for NP-hard problems. This more recent work has been explicitly patterned after multigrid techniques for continuous problems.
This talk will survey some of this history, and discuss several applications within scientific computing. The emphasis will be on a unified way of thinking about multilevel algorithms and on the essential components required to apply them effectively.
Speaker bio
Presentation (PowerPoint File)
Copyright. All Rights Reserved.