论文部分内容阅读
多数计算机代数系统对计算机硬件有较高的要求,在进行符号运算时,通常需要很大的内存和较长的计算时间,而精确的代数运算是以时间和空间为代价的。目前,IBM主机系统下尚未有当今流行的代数系统的移植,在主机系统下开发代数函数库能够利用大型机强大的科学计算处理能力高效地解决计算机代数领域中许多对时空要求很高的代数操作,如大整数的乘除运算、多项式组的约化以及求解理想的Grobner基等等。Buchberger在求Grobner基的原有算法的基础上应用标准表示理论提出了改进的GrobnerRefined算法,尽管在理论上很成熟,但是在实践中很难实现,主要原因是其运算过程中的中间项的次数急剧膨胀。利用降幂约化的方法进行改进的算法能够降低Grobncr基在求解过程中中间项的太多和幂次过高的情形;同时,这种算法占用的内存相对较少,能够在利用其解决大规模的代数运算的情形下节省很大的存储空间。
本文围绕改进Grobner基算法的中心思想:对S-多项式首先进行降幂约化处理,介绍了大整数在IBM主机系统下的表示方法及其四则运算;突破常规的多元多项式数组或链表存储方法,研究了将多项式作为一个整体结构进行存储的方法,同时在此基础上实现了多元多项式在IBM主机系统下的四则运算;在多项式的约化过程中,采用动态的序关系机制,也就是说每经过一次约化就对序关系进行一次修正,来防止化简过程当中某些变元的幂增长过高;引入S-簇的概念和相关定理首先对生成的S-多项式进行相关项的分类,然后利用降幂约化的算法对每个相关项集合进行约化处理以达到对原有Grobner基算法的优化。
作者在熟悉了IBM主机系统的交互式集成环境SDSF和在此环境下进行C程序开发的基础上,具体实现了能够进行长整数和多元多项式四则运算的函数INTEGER、POLYADD、POLYMUL和POLYQUO;用Maple语言描述了多项式降幂约化的算法;用Maple语言和相关的伪代码描述了改进后的Grobner基算法。