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.

Masters Theses in the Pure and Applied Sciences was first conceived, published, and disseminated by the Center for Information and Numerical Data Analysis and Synthesis (CINDAS) * at Purdue University in 1 957, starting its coverage of theses with the academic year 1955. Beginning with Volume 13, the printing and dissemination phases of the activity were transferred to University Microfilms/Xerox of Ann Arbor, Michigan, with the thought that such an arrangement would be more beneficial to the academic and general scientific and technical community. After five years of this joint undertaking we had concluded that it was in the interest of all con cerned if the printing and distribution of the volumes were handled by an interna tional publishing house to assure improved service and broader dissemination. Hence, starting with Volume 18, Masters Theses in the Pure and Applied Sciences has been disseminated on a worldwide basis by Plenum Publishing Cor poration of New York, and in the same year the coverage was broadened to include Canadian universities. All back issues can also be ordered from Plenum. We have reported in Volume 32 (thesis year 1987) a total of 12,483 theses titles from 22 Canadian and 176 United States universities. We are sure that this broader base for these titles reported will greatly enhance the value of this important annual reference work. While Volume 32 reports theses submitted in 1987, on occasion, certain univer sities do report theses submitted in previous years but not reported at the time.