基于指针数组的Gr?bner基方法的优化

门级整数乘法器电路的验证是形式化验证领域内的一个难题,目前最有效的方法是Grӧbner基方法。在基于此方法的验证过程中,多项式的表示对内存的使用情况有很大的影响。在验证工具Teluma中,多项式表示为单项式的链表。由于链表结点需要同时存储数据元素本身的信息和一个指示其直接后继的信息,这会占用较大的内存空间。针对这一问题,本文对多项式的数据结构进行了优化,采用了动态数组存储单项式,指针数组表示多项式的方法。实验结果表明,该优化方法减少了验证过程中内存的使用。

基于ZBDD的布尔多项式Grbner基算法的实现

零压缩二元判定树ZBDD(Zero-suppressed Binary Decision Diagrams)作为一种近年来兴起的存储布尔多项式的数据结构能更有效地平衡内存消耗与计算速度;基于它的布尔多项式Grbner基算法可以在运算中保持ZBDD结构的不变性从而进一步提高计算效率。用C++实现了布尔多项式的Grbner基计算并对其进行既约化处理,验证了该算法的可行性以及在运算效率上的提高。

模的Grbner基理论及在纠错码译码中的应用

针对如何提高纠错码译码过程中的效率问题,讨论了利用模的Grbner基理论计算纠错码中错误位置和错误值。计算过程中,首先将译码过程中关键方程的求解问题化为不同偏序下模的Grbner基的计算,然后利用一种偏序关系下已知的Grbner基计算另一种序下的Grbner基以得到错位及错误图样。该方法可以将错位多项式和错误值多项式同时求出。基于模的Grbner基理论的译码方法适用于二进制及多进制循环码的译码问题,并有助于提高译码的性能。

诺特赋值环上Grbner基的性质

本文主要研究了诺特赋值环上多项式理想的Grbner基的性质.利用Buchberger算法,证明了约化Grbner基的存在性及当其首项系数为单位元时的唯一性.推广了极小Grbner基和约化Grbner基的概念.同时,我们给出了求极小Grbner基和约化Grbner基的算法.

有限域上基于Grbner基的高级综合优化方法

提出了基于多项式符号代数的高级综合方法,并使用元件库中的元件构建多项式符号代数所表示的数据通路,计算出其Grbner基.利用Grbner基对多项式进行一些基本操作,例如,多变元多项式分解、最大公因式提取、库单元映射等,从而实现了有限域上的数据通路优化.最后进行了算法复杂性分析和实验,实验在SUN工作站上通过调用Maple10来完成,实验结果证实了本方法的有效性.

基于Gröbner基的图动态染色求解方案

考察了一般有限连通图的动态染色方案以及动态色数,首先利用多元多项式方程组对其进行建模,然后利用方程组对应的Grbner基来判定方程组解存在性,进而达到判定图的动态染色方案的存在性的目的,最后给出求动态色数及相应动态染色方案的方法,并给予实例验证.

构造过渡代数曲线的Grbner基方法

利用计算代数中理想的Grbner基理论,研究平面过渡代数曲线问题,对代数曲线的0至2阶几何连续拟合进行了较为具体的研究,最后通过实例验证了本文方法的有效性与准确性。

不变理想的Grbner基提升算法(英文)

采用Grbner基方法,可以把一个在有限群作用下不变的多项式写成不变环的生成元的多项式.核心问题是如何有效地计算这个正维不变理想的Grbner基.本文引入一个有效提升算法来计算这组Grbner基.当用straight line program模型对整个计算过程进行复杂度分析时,可以把计算开销控制在多项式时间内.

可除的四元数代数上多项式环的Grbner基(英文)

设F是一个特征不等于2的域,A是F上的一个可除代数。本文研究了A上多项式环A[x1,x2,…,xn]中理想是有限生成的,以及它的Gr bner基;也表明F[x1,x2,…,xn]中有限子集G是F[x1,x2,…,xn]的Gr bner基当且仅当G是A[x1,x2,…,xn]中的Gr bner基。

二项式斜多项式环的Grbner基

对于二次代数A=k〈X〉/(■),当关系■满足某种对称关系时,代数A是ArtinSchelter正则PBW代数,进一步,存在X上的一种重排,使得A是二项式斜多项式环.

一类图中k-圈的Grbner基求解方法

将无环无重边的有限无向图G中是否含有k(k∈Ζ+)个顶点的圈(简称k-圈)的问题转化为可使用Grbner基的性质来解决的多元多项式的问题.此外,通过实例验证G中的所有k-圈等价于计算转换后的多元多项式方程组在{-1,0,1}范围内的解集.

Gro¨ bner基方法验证乘法器的Maple实现

乘法器电路验证问题是一项极其重要而又极具挑战性的难题。当前主流的方法是先将其建模成交换代数中的理想成员问题,然后使用Mathematica、Singular等计算机代数系统中的Gröbner基方法进行判定。本文使用计算机代数系统Maple对这一方法给出了全新实现并在计算机上进行了对比实验。实验结果表明:Maple的实现在某种程度上具有更高的验证效率,可成为乘法器电路强有力的验证平台。

基于一种选择策略的Gr?bner基算法

在GrÖbner基算法GRÖBNERNEW2算法之上,增加了选择策略,即基于对的首单项式的最小公倍式次数最低来选择准则对,构建了一种改进的GrÖbner基算法.在计算变元个数较多的多项式理想的GrÖbner基时,避免了计算效率低,程序运行时间较长的问题,提高了GrÖbner基的计算效率.

神经理想的Gröbner基与典范形式集

神经环和神经理想这一概念是由Curto等(2013)提出的,它们是用于整理和分析神经编码中复杂组合信息的一种有用的代数方法.文章主要研究了神经理想的典范形式集与Gröbner基之间的关系,并根据Gröbner基中的元素给出了3种新类型的RF-关系.

基于指针操作的乘法器验证程序优化

乘法器电路验证是算术电路验证领域内的一个重大难题。Gröbner基方法是其中目前最为有效的验证方法之一。基于此方法开发的Amulet程序通过减少中间变量数量提高了验证效率,但是对于大型乘法器,验证速度慢的问题仍存在。本文对Amulet的关键算法进行了进一步优化,通过指针操作对函数进行重写,缩短了验证的时间,并根据实验数据体现了其在大型乘法器验证中的应用优势,为形式化验证技术的未来研究提供了参考。The verification of multiplier circuits is a significant challenge in the field of arithmetic circuit verification. The Gröbner basis method is currently one of the most effective verification methods available. The Amulet program, developed based on this method, improves verification efficiency by reducing the number of intermediate variables. However, for large multipliers, the verification speed remains an issue. This paper further optimizes the key algorithms of Amulet, by rewriting functions through pointer operations, reduces verification time. Experimental results demonstrate its advantages in the verification of large multipliers. It provides a reference for future research in formal verification techniques.

基于Grbner基的纠错码译码方法

译码作为编码理论中的一个重要过程,算法的优劣直接决定信息的处理速度。叙述了如何将Grbner基方法用在译码过程的计算中以提高译码效率。首先,介绍了Grbner基和译码过程中的相关理论。然后,分析了纠错码的译码过程并导出伴随式方程组,即多项式方程组。因为变元字典序的Grbner基具有消元的性质,故译码时使用字典序的Grbner基求解得到的方程组。利用了Grbner基求解非线性代数方程组的高效性。该方法具有很强的通用性。

Toric理想I_(A_d)的Grbner基

给出Toric环、Toric理想的概念,利用已知的Grbner基求配置矩阵A的Toric理想I_A的Grbner基.特别对一类无法用计算机计算其Grbner基的理想I_(A_d),给出了它的Grbner基的具体形式并通过实例验证其结论.

差分-微分模上多个序的Grbner基及多变量维数多项式

基于2008年Zhou和Winkler给出的计算有限生成的差分-微分双滤模的希尔伯特多项式的算法,文章构造了差分-微分模上相对多个序的的Grbner基,并给出和证明了计算这种Grbner基的算法.作为其应用,给出了计算差分-微分模的多变量维数多项式的新算法.推广了Zhou和Winkler(2008)所得结果,也推进了Levin(2007)所得结果.

基于动态数组的加法器重写优化算法

乘法器电路验证是算术电路验证领域内的一个重大难题。当前最有效的代数验证方法是Gröbner基方法。基于此方法提出的加法器重写算法是一项重大创新,但识别加法器的过程需要穷举遍历电路变量,并且十分低效。为了解决这一问题,本文对加法器重写算法进行了优化,使用动态数组存储搜索加法器所需的门变量,并以逆拓扑序的顺序来遍历,从而消除了冗余。实验结果表明,结合动态数组来识别加法器能够有效提高Gröbner基的生成效率和验证速度。

基于散列表的加法器重写优化算法

在大规模算术集成电路设计领域中,乘法器电路的验证是一重大难题。当前主流的方法是Gröbner基法。在此基础上,研究者们提出了加法器重写等优化方法,但重写过程依赖进位变量且需遍历全部变量,导致验证效率降低。为此,本文利用散列表对该方法进行优化,使用散列表存储所有和位输出变量,遍历表中元素进行扩充,再结合加法器的结构特性去识别加法器,从而不再依赖进位变量并且减少了需要遍历的变量数目。由实验结果可知,优化算法提高了Gröbner基的生成效率,也提高了乘法器的验证效率。