자료유형 | 학위논문 |
---|---|
서명/저자사항 | Probability and Machine Learning in Combinatorial Commutative Algebra. |
개인저자 | Silverstein, Lily Rachel. |
단체저자명 | University of California, Davis. Mathematics. |
발행사항 | [S.l.]: University of California, Davis., 2019. |
발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2019. |
형태사항 | 145 p. |
기본자료 저록 | Dissertations Abstracts International 81-04B. Dissertation Abstract International |
ISBN | 9781085797993 |
학위논문주기 | Thesis (Ph.D.)--University of California, Davis, 2019. |
일반주기 |
Source: Dissertations Abstracts International, Volume: 81-04, Section: B.
Advisor: De Loera, Jesus. |
이용제한사항 | This item must not be sold to any third party vendors. |
요약 | Many important computations in commutative algebra are known to be NP-hard. Despite their apparent intractability, these algebra problems---including computing the dimension of an algebraic variety, and computing the Hilbert series, projective dimension, and regularity of a homogeneous ideal---are indispensable in both applications and theoretical work. This dissertation advances our understanding of hard commutative algebra problems in several ways. First, we introduce families of parameterized random models for monomial ideals, and derive the expected values and asymptotic behavior of important algebraic properties of the ideals and their varieties. The surprising result is that many theoretically intractable computations on monomial ideals are easily approximated by simple ratios among number of generators, number of variables, and degrees of generators. Though these approximations are not deterministic, they are guaranteed to hold asymptotically almost surely.We derive threshold functions in the random models for Krull dimension, (strong) genericity, projective dimension, and Cohen-Macaulayness. In particular, we prove that in a rigorous sense, almost all monomial ideals have the maximum projective dimension possible according to the Hilbert Syzygy Theorem, and that almost no monomial ideals are Cohen-Macaulay. Furthermore, we derive specific parameter ranges in the models for which the minimal free resolution of a monomial ideal can be constructed combinatorially via the algebraic Scarf complex. We also give a threshold for every value of the Krull dimension.Following recent advances in optimization and computer science, another chapter of this thesis demonstrates how machine learning can be used as a tool in computational commutative algebra. We use supervised machine learning to train a neural network to select the best algorithm to perform a Hilbert series computation, out of a portfolio of options, for each new instance of this problem. We also explore how accurately a neural network can predict NP-hard monomial ideal invariants such as dimension and projective dimension, using features of the ideals that are computable in polynomial time. We provide compelling evidence that answers to these hard problems can be predicted for new instances based only on the historical data of previously seen examples.Finally, we implement integer linear programming reformulations of computations on ideals, to take advantage of the sophisticated solving methods now available for this particular class of problems. We demonstrate significant timing improvements in computations such as dimension and degree, especially for large instances of these problems. We define new polytopes useful for enumerative problems in commutative algebra, including enumerating all monomial ideals with a particular Hilbert function, and enumerating the possible Betti tables for a particular Hilbert function. |
일반주제명 | Mathematics. |
언어 | 영어 |
바로가기 | ![]() |