Browsing by Author "Green, Edward L."
Now showing 1 - 20 of 32
Results Per Page
Sort Options
- Algebraic Geometry of Bayesian NetworksGarcia-Puente, Luis David (Virginia Tech, 2004-01-30)We develop the necessary theory in algebraic geometry to place Bayesian networks into the realm of algebraic statistics. This allows us to create an algebraic geometry--statistics dictionary. In particular, we study the algebraic varieties defined by the conditional independence statements of Bayesian networks. A complete algebraic classification, in terms of primary decomposition of polynomial ideals, is given for Bayesian networks on at most five random variables. Hidden variables are related to the geometry of higher secant varieties. Moreover, a complete algebraic classification, in terms of generating sets of polynomial ideals, is given for Bayesian networks on at most three random variables and one hidden variable. The relevance of these results for model selection is discussed.
- Algebras and VarietiesGreen, Edward L.; Hille, Lutz; Schroll, Sibylle (2020-03)In this paper we introduce new affine algebraic varieties whose points correspond to associative algebras. We show that the algebras within a variety share many important homological properties. In particular, any two algebras in the same variety have the same dimension. The cases of finite dimensional algebras as well as that of graded algebras arise as subvarieties of the varieties we define. As an application we show that for algebras of global dimension two over the complex numbers, any algebra in the variety continuously deforms to a monomial algebra.
- Algorithms and Orders for Finding Noncummutative Gröbner BasesKeller, 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.
- Analysis and Implementation of Algorithms for Noncommutative AlgebraStruble, Craig Andrew (Virginia Tech, 2000-04-24)A fundamental task of algebraists is to classify algebraic structures. For example, the classification of finite groups has been widely studied and has benefited from the use of computational tools. Advances in computer power have allowed researchers to attack problems never possible before. In this dissertation, algorithms for noncommutative algebra, when ab is not necessarily equal to ba, are examined with practical implementations in mind. Different encodings of associative algebras and modules are also considered. To effectively analyze these algorithms and encodings, the encoding neutral analysis framework is introduced. This framework builds on the ideas used in the arithmetic complexity framework defined by Winograd. Results in this dissertation fall into three categories: analysis of algorithms, experimental results, and novel algorithms. Known algorithms for calculating the Jacobson radical and Wedderburn decomposition of associative algebras are reviewed and analyzed. The algorithms are compared experimentally and a recommendation for algorithms to use in computer algebra systems is given based on the results. A new algorithm for constructing the Drinfel'd double of finite dimensional Hopf algebras is presented. The performance of the algorithm is analyzed and experiments are performed to demonstrate its practicality. The performance of the algorithm is elaborated upon for the special case of group algebras and shown to be very efficient. The MeatAxe algorithm for determining whether a module contains a proper submodule is reviewed. Implementation issues for the MeatAxe in an encoding neutral environment are discussed. A new algorithm for constructing endomorphism rings of modules defined over path algebras is presented. This algorithm is shown to have better performance than previously used algorithms. Finally, a linear time algorithm, to determine whether a quotient of a path algebra, with a known Gröbner basis, is finite or infinite dimensional is described. This algorithm is based on the Aho-Corasick pattern matching automata. The resulting automata is used to efficiently determine the dimension of the algebra, enumerate a basis for the algebra, and reduce elements to normal forms.
- A Classification of some Quadratic AlgebrasMcGilvray, H. C. Jr. (Virginia Tech, 1998-07-02)In this paper, for a select group of quadratic algebras, we investigate restrictions necessary on the generators of the ideal for the resulting algebra to be Koszul. Techniques include the use of Gröbner bases and development of Koszul resolutions. When the quadratic algebra is Koszul, we provide the associated linear resolution of the field. When not Koszul, we describe the maps of the resolution up to the instance of nonlinearity.
- The cohomology rings of classical Brauer tree algebrasChasen, Lee A. (Virginia Tech, 1995-07-03)In this dissertation a simple algorithm is given for calculating minimal projective resolutions of nonprojective indecomposable modules over Brauer tree algebras. Those calculated resolutions lead to an algorithm for calculating a minimal set of generators for the cohomology ring of a Brauer tree algebra.
- A Combinatorial Proof of the Positivity of the Lusztig q-Analogue of Weight Multiplicity for Rank 2 Lie AlgebrasGillespie, Jason Michael (Virginia Tech, 2003-12-02)We prove the positivity of Lusztig's q-analogue of weight multiplicity in a purely combinatorial way for rank 2 Lie algebras. Each summand in the polynomial can be interpreted as a linear combination of positive roots. We prove that all negative coefficients are cancelled in the polynomial. Further, the analysis of the root systems allows us to state formulae for every coefficient in Lusztig's q-analogue for rank 2 Lie algebras.
- Combinatorial Properties of the Hilbert Series of Macdonald PolynomialsNiese, Elizabeth M. (Virginia Tech, 2010-03-30)The original Macdonald polynomials Pμ form a basis for the vector space of symmetric functions which specializes to several of the common bases such as the monomial, Schur, and elementary bases. There are a number of different types of Macdonald polynomials obtained from the original Pμ through a combination of algebraic and plethystic transformations one of which is the modified Macdonald polynomial H̃μ. In this dissertation, we study a certain specialization F̃μ(q,t) which is the coefficient of x₁x₂…xN in H̃μ and also the Hilbert series of the Garsia-Haiman module Mμ. Haglund found a combinatorial formula expressing F̃μ as a sum of n! objects weighted by two statistics. Using this formula we prove a q,t-analogue of the hook-length formula for hook shapes. We establish several new combinatorial operations on the fillings which generate F̃μ. These operations are used to prove a series of recursions and divisibility properties for F̃μ.
- Complex Analysis on Planar Cell ComplexesArnold, Rachel Florence (Virginia Tech, 2008-04-29)This paper is an examination of the theory of discrete complex analysis that arises from the framework of a planar cell complex. Construction of this theory is largely integration-based. A combination of two cell complexes, the double and its associated diamond complex, allows for the development of a discrete Cauchy Integral Formula.
- Computational Algebraic Geometry Applied to Invariant TheoryShifler, Ryan M. (Virginia Tech, 2013-06-05)Commutative algebra finds its roots in invariant theory and the connection is drawn from a modern standpoint. The Hilbert Basis Theorem and the Nullstellenstatz were considered lemmas for classical invariant theory. The Groebner basis is a modern tool used and is implemented with the computer algebra system Mathematica. Number 14 of Hilbert\'s 23 problems is discussed along with the notion of invariance under a group action of GLn(C). Computational difficulties are also discussed in reference to Groebner bases and Invariant theory.The straitening law is presented from a Groebner basis point of view and is motivated as being a key piece of machinery in proving First Fundamental Theorem of Invariant Theory.
- Decentralized Trust-Based Access Control for Dynamic Collaborative EnvironmentsAdams, William Joseph (Virginia Tech, 2006-03-31)The goal of this research was to create a decentralized trust-based access control (TBAC) system for a dynamic collaborative environment (DCE). By building a privilege management infrastructure (PMI) based on trust, user access was determined using behavior grading without the need for pre-configured, centrally managed role hierarchies or permission sets. The PMI provided TBAC suitable for deployment in a rapidly assembled, highly fluid, collaborative environment. DCEs were assembled and changed membership as required to achieve the goals of the group. A feature of these environments was that there was no way of knowing who would join the group, no way of refusing anyone entry into group, and no way of determining how long members would remain in the group. DCEs were formed quickly to enable participants to share information while, at the same time, allowing them to retain control over the resources that they brought with them to the coalition. This research progressed the state of the art in the fields of access control and trust management. The Trust Management System developed through this research effectively implemented a decentralized access control scheme. Each resource owner independently evaluated the reputation and risk of network members to make access decisions. Because the PMI system used past behavior as an indication of future performance, no a priori user or resource configuration was required.
- Enhancing Attack Resilience in Cognitive Radio NetworksChen, Ruiliang (Virginia Tech, 2008-02-19)The tremendous success of various wireless applications operating in unlicensed bands has resulted in the overcrowding of those bands. Cognitive radio (CR) is a new technology that enables an unlicensed user to coexist with incumbent users in licensed spectrum bands without inducing interference to incumbent communications. This technology can significantly alleviate the spectrum shortage problem and improve the efficiency of spectrum utilization. Networks consisting of CR nodes (i.e., CR networks)---often called dynamic spectrum access networks or NeXt Generation (XG) communication networks---are envisioned to provide high bandwidth to mobile users via heterogeneous wireless architectures and dynamic spectrum access techniques. In recent years, the operational aspects of CR networks have attracted great research interest. However, research on the security aspects of CR networks has been very limited. In this thesis, we discuss security issues that pose a serious threat to CR networks. Specifically, we focus on three potential attacks that can be launched at the physical or MAC layer of a CR network: primary user emulation (PUE) attack, spectrum sensing data falsification (SSDF) attack, and control channel jamming (CCJ) attack. These attacks can wreak havoc to the normal operation of CR networks. After identifying and analyzing the attacks, we discuss countermeasures. For PUE attacks, we propose a transmitter verification scheme for attack detection. The scheme utilizes the location information of transmitters together with their signal characteristics to verify licensed users and detect PUE attackers. For both SSDF attacks and CCJ attacks, we seek countermeasures for attack mitigation. In particular, we propose Weighted Sequential Probability Ratio Test (WSPRT) as a data fusion technique that is robust against SSDF attacks, and introduce a multiple-rendezvous cognitive MAC (MRCMAC) protocol that is robust against CCJ attacks. Using security analysis and extensive numerical results, we show that the proposed schemes can effectively counter the aforementioned attacks in CR networks.
- Examples and theorems for generalized paracompact topological spacesFast, Stephen Hardin (Virginia Tech, 1990-12-05)In this thesis we answer a number of unsolved problems in generalized paracompact topological spaces. Examples satisfying the T₄ separation axiom are constructed showing the relationship between the properties B(D, ω₀)-refinability, B(D, λ)-refinability, and weak θ̅-refinability. The properties B(D, λ)-refinability and weak θ̅-refinability are shown to be strictly weaker than B(D, ω₀)-refinability. Sum theorems, mapping theorems, and o—product theorems are obtained for B(D, ω₀)-refinability, weak θ̅-refinability, and several other properties. The σ—product theorem for B(D,ω₀)-refinability, weak θ̅-refinability, and other properties are shown to follow from a new special B(D,ω₀) sum theorem.
- Finite Generation of Ext-Algebras for Monomial AlgebrasCone, Randall Edward (Virginia Tech, 2010-11-30)The use of graphs in algebraic studies is ubiquitous, whether the graphs be finite or infinite, directed or undirected. Green and Zacharia have characterized finite generation of the cohomology rings of monomial algebras, and thereafter G. Davis determined a finite criteria for such generation in the case of cycle algebras. Herein, we describe the construction of a finite directed graph upon which criteria can be established to determine finite generation of the cohomology ring of in-spoked cycle" algebras, a class of algebras that includes cycle algebras. We then show the further usefulness of this constructed graph by studying other monomial algebras, including d-Koszul monomial algebras and a new class of monomial algebras which we term "left/right-symmetric" algebras.
- Graphs and Noncommutative Koszul AlgebrasHartman, Gregory Neil (Virginia Tech, 2002-04-23)A new connection between combinatorics and noncommutative algebra is established by relating a certain class of directed graphs to noncommutative Koszul algebras. The directed graphs in this class are called full graphs and are defined by a set of criteria on the edges. The structural properties of full graphs are studied as they relate to the edge criteria. A method is introduced for generating a Koszul algebra Lambda from a full graph G. The properties of Lambda are examined as they relate to the structure of G, with special attention being given to the construction of a projective resolution of certain semisimple Lambda-modules based on the structural properties of G. The characteristics of the Koszul algebra Lambda that is derived from the product of two full graphs G' and G' are studied as they relate to the properties of the Koszul algebras Lambda' and Lambda' derived from G' and G'.
- Groebner Finite Path AlgebrasLeamer, Micah J. (Virginia Tech, 2004-06-04)Let K be a field and Q a finite directed multi-graph. In this paper I classify all path algebras KQ and admissible orders with the property that all of their finitely generated ideals have finite Groebner bases.
- Growth of algebras, words, and graphsEllingsen, Harold W. (Virginia Tech, 1993-04-05)Finitely generated monomial algebras are studied. the bound in Bergman's description of algebras with GK-dimension 1 is improved and similar techniques are used to establish the equivalence of the periodicities of overlap graphs and Hilbert series coefficients.
- Infinite Groebner Bases And Noncommutative Polly Cracker CryptosystemsRai, Tapan S. (Virginia Tech, 2004-03-23)We develop a public key cryptosystem whose security is based on the intractability of the ideal membership problem for a noncommutative algebra over a finite field. We show that this system, which is the noncommutative analogue of the Polly Cracker cryptosystem, is more secure than the commutative version. This is due to the fact that there are a number of ideals of noncommutative algebras (over finite fields) that have infinite reduced Groebner bases, and can be used to generate a public key. We present classes of such ideals and prove that they do not have a finite Groebner basis under any admissible order. We also examine various techniques to realize finite Groebner bases, in order to determine whether these ideals can be used effectively in the design of a public key cryptosystem. We then show how some of these classes of ideals, which have infinite reduced Groebner bases, can be used to design a public key cryptosystem. We also study various techniques of encryption. Finally, we study techniques of cryptanalysis that may be used to attack the cryptosystems that we present. We show how poorly constructed public keys can in fact, reveal the private key, and discuss techniques to design public keys that adequately conceal the private key. We also show how linear algebra can be used in ciphertext attacks and present a technique to overcome such attacks. This is different from the commutative version of the Polly Cracker cryptosystem, which is believed to be susceptible to "intelligent" linear algebra attacks.
- Loop Spaces and Iterated Higher Dimensional EnrichmentForcey, Stefan Andrew (Virginia Tech, 2004-04-15)There is an ongoing massive effort by many researchers to link category theory and geometry, especially homotopy coherence and categorical coherence. This constitutes just a part of the broad undertaking known as categorification as described by Baez and Dolan. This effort has as a partial goal that of understanding the categories and functors that correspond to loop spaces and their associated topological functors. Progress towards this goal has been advanced greatly by the recent work of Balteanu, Fiedorowicz, Schwänzl, and Vogt who show a direct correspondence between k–fold monoidal categories and k–fold loop spaces through the categorical nerve. This thesis pursues the hints of a categorical delooping that are suggested when enrichment is iterated. At each stage of successive enrichments, the number of monoidal products seems to decrease and the categorical dimension to increase, both by one. This is mirrored by topology. When we consider the loop space of a topological space, we see that paths (or 1–cells) in the original are now points (or objects) in the derived space. There is also automatically a product structure on the points in the derived space, where multiplication is given by concatenation of loops. Delooping is the inverse functor here, and thus involves shifting objects to the status of 1–cells and decreasing the number of ways to multiply. Enriching over the category of categories enriched over a monoidal category is defined, for the case of symmetric categories, in the paper on A∞–categories by Lyubashenko. It seems that it is a good idea to generalize his definition first to the case of an iterated monoidal base category and then to define V–(n + 1)–categories as categories enriched over V–n–Cat, the (k−n)–fold monoidal strict (n+1)–category of V–n–categories where k
- Monomial Dynamical Systems over Finite FieldsColon-Reyes, Omar (Virginia Tech, 2005-04-28)Linking the structure of a system with its dynamics is an important problem in the theory of finite dynamical systems. For monomial dynamical systems, that is, a system that can be described by monomials, information about the limit cycles can be obtained from the monomials themselves. In particular, this work contains sufficient and necessary conditions for a monomial dynamical system to have only fixed points as limit cycles.