Handbook of Data Structures and Applications, 2nd Edition

61

Elimination Structures in Scientific Computing*

Alex Pothen

Purdue University

Sivan Toledo

Tel Aviv University

61.1The Elimination Tree

The Elimination Game•The Elimination Tree Data Structure•An Algorithm•A Skeleton Graph•Supernodes

61.2Applications of Etrees

Efficient Symbolic Factorization•Predicting Row and Column Nonzero Counts•Three Classes of Factorization Algorithms•Scheduling Parallel Factorizations•Scheduling Out-of-Core Factorizations

61.3The Clique Tree

Chordal Graphs and Clique Trees•Design of Efficient Algorithms with Clique Trees•Compact Clique Trees

61.4Clique Covers and Quotient Graphs

Clique Covers•Quotient Graphs•The Problem of Degree Updates•Covering the Column-Intersection Graph and Biclique Covers

61.5Column Elimination ...