Accession Number : ADA188527

Title :   A Graph Separator Theorem and Its Application to Gaussian Elimination to Optimize Boolean Expressions for Parallel Evaluation.

Descriptive Note : Interim rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Sheffler, Thomas J

PDF Url : ADA188527

Report Date : Dec 1987

Pagination or Media Count : 87

Abstract : Gaussian elimination, which has been shown to be applicable to the solution problems in many different domains, is the technique used by COSMOS to symbolically analyze digital MOS networks for their behavior in terms of Boolean expressions. While pivot selection algorithms are known which minimize the total number of operations required to solve a system, this report will focus on pivot selection algorithms that result in expressions of small depth, from which fine-grained parallelism may be extracted. A graph theoretic approach to Gaussian elimination is adopted which allows the structure of sparse systems to be clearly examined, and an elimination ordering based on graph separators is shown to result in expressions of small depth. This report proposes an algorithm related to Gaussian elimination which characterizes graphs in terms of decomposition rules and shows that for graphs which may be reduced by an elimination ordering the results in low total complexity, a reordered elimination sequence may result in expressions of small depth.

Descriptors :   *INTEGRATED CIRCUITS, *NETWORKS, *CIRCUIT ANALYSIS, *COMPUTERIZED SIMULATION, ALGORITHMS, BOOLEAN ALGEBRA, DECOMPOSITION, ELIMINATION, GRAPHS, PARALLEL ORIENTATION, PIVOTS, SELECTION, SEPARATORS, SEQUENCES, SOLUTIONS(GENERAL), TEST AND EVALUATION, THEOREMS, THEORY

Subject Categories : Electricity and Magnetism
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE