ON DYNAMIC ALGORITHMS FOR FACTORIZATION INVARIANTS IN NUMERICAL MONOIDS

作     者：Barron, Thomas O'Neill, Christopher Pelayo, Roberto 

作者机构：Univ Kentucky Dept Math Lexington KY 40506 USA Texas A&M Univ Dept Math College Stn TX 77843 USA Univ Calif Davis Dept Math One Shields Ave Davis CA 95616 USA Univ Hawaii Dept Math Hilo HI 96720 USA 

出 版 物：《MATHEMATICS OF COMPUTATION》 (计算数学)

年 卷 期：2017年第86卷第307期

页      面：2429-2447页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Direct For Mathematical & Physical Scien Division Of Mathematical Sciences Funding Source: National Science Foundation 

主　　题：Monoid computer use factorization dynamic algorithms Quotient group Dynamic algorithms Runtime Invariant 

摘      要：Studying the factorization theory of numerical monoids relies on understanding several important factorization invariants, including length sets, delta sets, and w-primality. While progress in this field has been accelerated by the use of computer algebra systems, many existing algorithms are computationally infeasible for numerical monoids with several irreducible elements. In this paper, we present dynamic algorithms for the factorization set, length set, delta set, and w-primality in numerical monoids and demonstrate that these algorithms give significant improvements in runtime and memory usage. In describing our dynamic approach to computing w-primality, we extend the usual definition of this invariant to the quotient group of the monoid and show that several useful results naturally extend to this broader setting.