MATH Seminar

Title: Some Old and New Results on an Elimination Game
Seminar: Numerical Analysis and Scientific Computing
Speaker: Esmond G. Ng of Lawrence Berkeley National Laboratory
Contact: James Nagy, nagy@mathcs.emory.edu
Date: 2014-10-06 at 12:00PM
Venue: MSC W301
Download Flyer
Abstract: Sparse matrix problems arise at the heart of many large-scale scientific and engineering applications. State-of-the-art algorithms for solving these problems involve not only numerical techniques, but may also require knowledge of data structures, graph theory, algorithm design, complexity analysis, and computer architectures. This is particularly true for factorization-based algorithms, such as those for solving sparse systems of linear equations, in which the nonzero entries of a matrix are eliminated according to certain prescribed rules. However, the order in which the nonzero entries are eliminated can have a dramatic effect on the overall performance of the solution process. This is referred to as the ordering problem, which is often posed as an elimination game on a graph. In this talk, an overview of the elimination game will be presented. In particular, previously known results and some recently work will be described.