Browsing by Author "Keenan, Michael A."

Now showing 1 - 4 of 4
  • Thumbnail Image
    Algorithms and Orders for Finding Noncummutative Gröbner Bases
    Keller, Benjamin J. (Virginia Tech, 1997-03-17)
    The problem of choosing efficient algorithms and good admissible orders for computing Gröbner bases in noncommutative algebras is considered. Gröbner bases are an important tool that make many problems in polynomial algebra computationally tractable. However, the computation of Gröbner bases is expensive, and in noncommutative algebras is not guaranteed to terminate. The algorithm, together with the order used to determine the leading term of each polynomial, are known to affect the cost of the computation, and are the focus of this thesis. A Gröbner basis is a set of polynomials computed, using Buchberger's algorithm, from another set of polynomials. The noncommutative form of Buchberger's algorithm repeatedly constructs a new polynomial from a triple, which is a pair of polynomials whose leading terms overlap and form a nontrivial common multiple. The algorithm leaves a number of details underspecified, and can be altered to improve its behavior. A significant improvement is the development of a dynamic dictionary matching approach that efficiently solves the pattern matching problems of noncommutative Gröbner basis computations. Three algorithmic alternatives are considered: the strategy for selecting triples (selection), the strategy for removing triples from consideration (triple elimination), and the approach to keeping the set interreduced (set reduction). Experiments show that the selection strategy is generally more significant than the other techniques, with the best strategy being the one that chooses the triple with the shortest common multiple. The best triple elimination strategy ignoring resource constraints is the Gebauer-Müller strategy. However, another strategy is defined that can perform as well as the Gebauer-Müller strategy in less space. The experiments also show that the admissible order used to determine the leading term of a polynomial is more significant than the algorithm. Experiments indicate that the choice of order is dependent on the input set of polynomials, but also suggest that the length lexicographic order is a good choice for many problems. A more practical approach to chosing an order may be to develop heuristics that attempt to find an order that minimizes the number of overlaps considered during the computation.
  • Thumbnail Image
    A Custom Computing Machine Solution for Simulation of Discretized Domain Physical Systems
    Paar, Kevin J. (Virginia Tech, 1996-06-05)
    This thesis describes the implementation of a two-dimensional heat transfer simulation system using a Splash-2 Custom Computing Machine (CCM). This application was implemented as a proof of concept for utilizing CCMs in the simulation of physical systems. This paper discusses physical systems simulation and the need for discretizing the domain of such systems, along with the techniques used for mathematical simulation. Also discussed is the nature of CCMs, and why they are well suited to this application. A detailed description of the approach and implementation is included to full document the design, along with an analysis of the performance of the resulting system.
  • Thumbnail Image
    A Method for Assessing the Development Process of Small Organizations
    Henry, Joel; Keenan, Susan L.; Keenan, Michael A.; Henry, Sallie M. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
    This paper describes a two-phase method for assessing the s.oftware development process of small organizations. The initial phase involves using the Software Engineering Institute (SEI) assessment method to establish the activities comprising the development process. The second phase consists of follow-up interviews to discover the implementation technique for each existing activity and investigate the effectiveness of the techniques. Procedures for generating recommendations are outlined. The data acquired is statistically valid and allows discovery of significant problem areas. Recommendations based on the SEI framework and accepted software engineering practices are described. The assessment method is evaluated and future work is outlined.
  • Thumbnail Image
    Representation and simulation of a high level language using VHDL
    Edwards, Carleen Marie (Virginia Tech, 1994-12-05)
    This paper presents an approach for representing and simulating High Level Languages (HLL) using VHDL behavioral models. The graphical representation, a Data Flow Graph (DFG), is used as a base for the VHDL representation and simulation of a High Level Language (C). A package of behavioral models for the functional units for the High Level Language as well as individual entities has been developed using VHDL. An algorithm, Graph2VHDL, accepts a Data Flow Graph representation of a High Level Language and constructs a VHDL model for that graph. The representation of a High Level Language in VHDL frees users of custom computing platforms from the tedious job of developing a hardware model for a desired application. The algorithm also constructs a test file that is used with a pre-existing program, Test Bench Generation (TBG), to create a test-bench for the VHDL model of a Data Flow Graph. The test bench that is generated is used to simulate the representation of the High Level Language in the Data Flow Graph format. Experimental results verify the representation of the High Level Language in the Data Flow Graph format and in VHDL is correct.