（计算机应用技术专业论文）ibm主机代数库的开发和grobner基算法的研究.pdf

摘要 摘要 多数计算机代数系统对计算机硬件有较高的要求，在进行符号运算时，通常 需要很大的内存和较长的计算时间，而精确的代数运算是以时间和空间为代价 的。目前，i b m 主机系统下尚未有当今流行的代数系统的移植，在主机系统下开 发代数函数库能够利用大型机强大的科学计算处理能力高效地解决计算机代数领 域中许多对时空要求很高的代数操作，如大整数的乘除运算、多项式组的约化以 及求解理想的g m n e r 基等等。b u c h b e r g e r 在求g r 6 b n e r 基的原有算法的基础上应 用标准表示理论提出了改进的g r 6 b n e r r e ：f i n e d 算法，尽管在理论上很成熟，但是 在实践中很难实现，主要原因是其运算过程中的中间项的次数急剧膨胀。利用降 幂约化的方法进行改进的算法能够降低b n e r 基在求解过程中中间项的太多和 幂次过高的情形；同时，这种算法占用的内存相对较少，能够在利用其解决大规 模的代数运算的情形下节省很大的存储空间。 本文围绕改进g r 6 b n e r 基算法的中心思想：对s 。多项式首先进行降幂约化处 理，介绍了大整数在i b m 主机系统下的表示方法及其四则运算；突破常规的多元 多项式数组或链表存储方法，研究了将多项式作为一个整体结构进行存储的方 法，同时在此基础上实现了多元多项式在i b m 主机系统下的四则运算；在多项式 的约化过程中，采用动态的序关系机制，也就是说每经过一次约化就对序关系进 行一次修正，来防止化简过程当中某些变元的幂增长过高；引入s 簇的概念和相 关定理首先对生成的s 一多项式进行相关项的分类，然后利用降幂约化的算法对每 个相关项集合进行约化处理以达到对原有g 拍b n e r 基算法的优化。 作者在熟悉了i b m 主机系统的交互式集成环境s d s f 和在此环境下进行c 程 序开发的基础上，具体实现了能够进行长整数和多元多项式四则运算的函数 i n t e g e r 、p o u 似d d 、p o i m 小l 和p o l ，y q u o ；用m a p l e 语言描述了多项式 降幂约化的算法；用m a p l e 语言和相关的伪代码描述了改进后的伽b n e r 基算 法。 关键词：约化，g r 6 b n e r 基，s 一多项式，序关系，s 簇 a b s 虹a c t a b s t r a c t m o s tc o m p m e ra l g e b r as y s t e l n sp u tg r e a t 锄p h a s i so nr e q u i r e m e n tf o rc o m p u t e r h a r d w a r e u s l l a l l y ，i tn e e d sag r e a t 锄。嘣o fm 锄。巧a n dt i l n et 0p e r f i o 咖s y t n b 0 1 i c c o m p u t a t i o n h o w e v e r ，l ep r e c i s ea l g e b r a i cm a n i p m a t i o ni sa l wa _ y sa tt h ep r i c eo fm e a 1 1 ds p a 泡a tp d 锱翩t ，1 e h a s n t 趾yp r e 谢l i n ga l g e b r as y s t e m 妞t e g r a t e di n t oi b m m a i l l 仔a m es y s t e m a tm ea d v a n t a g eo fs t r o n gc a p a c i t ) ro fm a j n b m et op e r f o 咖 s c i e n t i 6 cc o m p u t a t i o n ，t 1 1 e 出l v e l o p i n e n to fa l g e b r a i c 劬c t i o ns e tu n d e rm a i n 丘a m e s y s t a nc 锄r e s 0 1 v em a n ya l g e b r a i cm a i l i p u l 撕o l l se 伍c i e n t l y w l l i c hp u t 铲e a td e 玎姗1 d s o nt i m ea n ds p a c e ，s u c ha sm en m l t i p l i c a t i o n 锄dd i v i s i o no fl 鹕ei n t e g e r s ，t h er e d u c i n g o fp 0 1 y n o m i a lg r o u pa i l dg 饥e r a t i n gm eg r 6 b n 嚣b a u s i so fi d e a le t c b u c h b e g e rp u t f o n a r dt h ei r n p r 0 v e d ( 拍b n e 呶e 6 n e da l g o n m m 恤c hm a i n l ya d o p t e d 戗l es t a n d a r d p r e s 饥t i n g 也c o r y a l t h o u g hi ti sp 耐e c tt h e o r e t i c a l l y ，i ti su 1 啦a c t i c a ld l l et o 也ed o 蓼e e o fm i d d l et e n l li 1 1 c r e a s i n gt o of a s ti 1 1 廿1 ep r o c e s so fc o m p m 撕0 n t h ei i n p r o v e d a l g o r i m ma p p l ) ，i n g 戗l e d e g r e e d r o p p i n g r e d u c i n g m e m o dc a ne l i m i i l a t es u c h p h 锄o m e n o n f 试h 踟 i l o r e ，i td e m a n d sl e s sm e m o w 1 1 i c hi sag r e a ta d v a n t a g ei i ll a r g e s c a l ea l g e b r a i cm a i l i p 岷1 a t i o n b a s i n go nm ec 锄臼试i d e ao fi m p r o v e dg r 6 b n e rb a s i sa l g o r i t l l m ，m a ti s ，d e g r e c - d r o p p i n 争砌如c i n gt h es - l o l y i l o m i 吐t h i sp a p e r 砷d u c e s 也ep f e s t 撕o n 觚d 撕恤l e t i co fl a r g ei n t e g e ri l lm ei b mm 豳锄es y 姚n b r e a 玉【i n g 俯o u 出t h er e 鲥a f i d e ao fs t o r i n gp o l y n o m i a li n 也em a c 抽n eu s i l l ga r r a yo r1 i i l l ( - 1 i 瓯i td e v e l o p san e ww a y t 0a c l l i e v en l a tb ys t o r i i 培廿1 ep 0 1 y n o m i a la saw h 0 1 eu i l i ti nt l l em a c i h i i l ea n di m p l 锄e n t s t l l e 砸t h e t i co fp 0 1 ) ，i l o i i l i a li n 也e mm a i n 缸瞄es y s t e m h lt h ep r o c e s so fr 础埘n g p o l y l l o i n j a l ，mo r d e rt ok e 印t l l en m n b e ro fm i d d l et 锄舶mi n c r e a s i l l gt o of 瓠t 锄dt l l e d e 莎e eo fp 0 1 ) ，n o m i a lb e i n gt o ol l i g 也i ta d o p t sam e c h a i l i s mc a l l c dd y i l a i i l i co r d e r r e l a t i o nm a ti s ，m o d i 研n gt h eo r d e rr e l a t i o ni m m e d i a t e l ya r e rp e r f b m i n ga r e d u c i n g i t 锄的d u c e sm ec o n c e p ta l l dr e l a t e dm e o r e m so fs v 撕e t i e s a tf i r s t ，i ti sa d o p t e dt o c a t e g o r i z em es - p 0 1 y i l o i i l i a lb yr e l a t i n gt 咖s ，趾dt h 鸭e v e r yr e l a t i n gt e r i l l ss e ti s p m c e s s e da o c o r d i n gt ot h ed e 伊e e d r o p p i n g r e d u c i n g2 i l g o r i t i l i l l t h l l s ，i tc o m p l e t e st 1 1 e i l i l 】p r 0 v e m e n to fo l da l g 嘶t l l m i i a b s 仃a c t t h ea u t h o rg e t sa c q u a i n t e dw i t hm en e r a c t i n gi n t e 蓼a t e de i l v i r o m e l l ts d s fo f i e ；mm a i n 丘a m es y s t e ma i 】【d 吐l ep r o c e s so fd e v e l o p i n gcp r 0 黟a mu n d e ri t a r e rt h a t ， t h ea u t b o ri m p l 锄e n t ss e v e r a l 如n c t i o n st 0p e d b mm ea r i 也m e t i co fl a r g ei n t e g e r 锄d p o l ”o m i a l n e ya r ei n t e g e rp o l y a d d ，p o l y m u l a n dp o l y q u o a t l a s t ，t 1 1 e a u t l l o rd e s c r i b e st 1 1 ed e g r e e d r o p p i n 争r e d u c i n ga l g o r i 咖：i li nm a p l el a i l g u a g e 锄dt 1 1 e i i i l p r o v e d ( 拍b n e rb 戚sa l g o r i t h mi nm a p l el a i l g u a g ea n d r e l a t e dp s e u d 0c o d e k q w o r d ：r e d u c i n g r 6 b n e rb a s i s ，s - p o l y n o m i a l ，o r d e rr e l a t i o n ，s v a d e t i e s i i i 符号说明 符号说明： a 胁 k 或k l t ( f ) l c ( o h n ( d d e g ( f ) 或a ( f ) l p ( f ) k x 1 ，x 2 ，x n 】 g c d l c m f _ 鸟h s p o l y ( e 曲 d e g x f g b ( d r g b ( i ) i ( ) ( ) v 砥f ) a 整除b 由集合s 中元素生成的子群或者理想 域 多项式f 的领项 多项式f 的领项系数 多项式f 的领式 多项式f 的次数 多项式f 的领项的幂积 域k 上n 变元x 1 ，x 2 ，x n 的多项式环 由多项式，龟，生成的理想或子模 最大公因子 最小公倍式 f 模g 约化到h 多项式f 和g 的s - 多项式 多项式f 相对于变元x 的次数 理想i 的嘶b n e r 基 i 的既约鲫b n e r 基 表示多项式x 的初式 表示多项式f 的代数簇 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：强嘲钐年5 月蜘 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：辑言篓之7 氅 日期：矽7 年歹月2 ，易日 第一章引言 1 1 历史背景 第一章引言 现代计算机以两种不同的方式对数学发生影响：一方面，它使得数学比以往 任何时候都更具威力，直接地影响数学中的价值观念和方法的平衡；另一方面， 通过其创新性的应用，间接地改变着数学的内容和结构。从而给数学带来了前所 未有的繁荣和发展。 计算机己被普遍地用于各类数学研究。即使从来不用计算机的数学家，也可 能要投身到由于计算机的存在而产生的课题的研究中去。在数学的各个方面，计 算机提出了新的课题，给证明和发现提供了新的工具，引进了新的研究方法，并 且在越来越多的情形中改变着证明本身。 可是，反过来我们要说“数学是计算机的灵魂”。计算机可以运算的很快， 但粗糙的计算方法使其复杂度可以很快地超过计算机的处理能力，理论的和实际 的计算之间存在着巨大的鸿沟。对实际的计算来说，一个好的算法是至关重要 的。实际可行性问题不能容忍粗糙的算法。正是在这个意义下，为了扩充有兴趣 的计算机应用领域，要求研究一种新的数学，数学的发展使得计算机有了越来越 强大的生命力。 这种新数学一般称为机械化数学，它对实际可行性比对理论可能性更感兴 趣，实际可行性甚至己经成为衡量数学进步的一个重要准则，在这种新数学中， 算法的实际可行性往往是以牺牲它的完全性或可靠性为代价的。对于一个问题 类，如果找不到实际可行的完全算法，很多时候仅仅给出实际可行的部分算法， 即对问题类的某个子类给出实际可行的完全算法也有着重要意义，有时微不足道 的出错概率可能大量节省计算所需的资源。这些观念强烈地体现着数学发展动力 的现实性的一面，它们在传统的所谓核心数学中却是难以立足的，是被大大忽略 了的。 数学所面临的这些新的机遇和挑战，促使数学的发展由抽象的、结构主义的 道路转向具体的、构造性的、结合实际的、结合计算机的道路。 同时，计算机作为一种强有力的信息处理的工具，作为一个强大的数学载体 也正在改变着数学家的工作方式。它正在逐渐地成为数学家不可替代的可靠助手 电子科技大学硕士学位论文 和新思想的实验场所，它把数学家从繁复的演算中解放出来，使之能把更多的精 力注入到新的发现和创造之中。 从数学发展的历史来看，代数与算法有密切的联系。早在古希腊时代，在 几何原本关于数论的论述中，e u c l i d 就给出了求两个正数的最大公因数的方 法，这就是著名的e u c l i d 算法。代数学的基本问题是解方程组的问题，对于n 元 一次方程组，可以用高斯消元法求解，对于一元二次、三次、四次方程都可以找 到公式解，这些方法都是构造性的方法，可以用算法来实现。但是对于一元五次 和更高次的方程就找不到公式解了，对于多元多项式方程组更没有一般性的算 法。为了解决这些问题，从1 9 世纪以来，一种新的方法引入了代数学的研究， 这就是“公理化方法”。“公理化方法”采用抽象的证明，非构造性的论证研究代数 问题，获得了巨大的成功，现在“公理化方法”己经成为代数学的主要方法。 不过，数学家依然在寻找解决某一类问题的算法解。例如h i l b e n 第十问题【l 】 就是这类问题，这类问题的提出促进了现代数理逻辑的发展。在2 0 世纪3 0 年 代，舢a i lt u 晴n g ，越o n z oc h u r c h 首先提出了可计算性的概念，从数学的角度论证 了算法的含义，k u ng 6 d e l 证明了某些数学问题没有算法解；到了4 0 年代， 砧砌t a r s l ( i 系统地研究了一些代数问题的可解性和不可解性，正是这些逻辑学 家的工作奠定了现代计算机科学的基础。 随着计算机技术的发展，以及计算机的普及，应用计算机解决代数问题成为 可能，计算代数就是在这种条件下出现的一个新的研究方向。从代数的观点看， 计算代数主要探讨代数学中可计算的问题，以及解决这些问题的算法；从计算机 科学的观点来看，我们要考虑代数算法的有效性及复杂性，因此计算代数可以看 作代数学与计算机科学相结合的产物。它没有作为一独立的学科分支，因为它的 演算与推导是以符号为主，因此我们也可以把它归入计算机代数这一学科中。 科学计算可分为两类：一类是纯数值的计算，例如求函数的值，方程的数值 解；另一类计算是符号计算，又称代数运算。这是一种智能化的计算，处理的是 符号。符号可以代表整数，有理数，实数和复数，也可以代表多项式，函数，还 可以代表数学结构如集合、群的表示等等。我们在数学的教学和研究中用笔和纸 进行的数学运算多为符号运算。 计算机代数【2 】( c o m p u t e r 趾g e b r a ) 是用计算机进行符号推演及准确计算的一 门科学，它也称为符号和代数计算，是与数值计算并行的一种数学计算，起源于 上世纪六十年代。与数值计算一样，随着计算机的发展，它本身亦得到迅速发 2 第一章引言 展。现已经成为数学、计算机科学中的一个独立分支，在理论研究及实际中都有 广泛应用。 计算机首先是为数值计算而设计的，自从计算机问世以来数值计算得到了迅 猛发展，但数值计算只是数学演算的一种，许多数学演算是不能或不能只用数值 计算来完成的。例如：求函数的极限，求不定积分，求微分方程解析解等等，它 们都是不同于数值计算的另一类数学演算，要应用有关的数学公式、法则来处理 数学符号才能完成，这类演算就是符号推演。 符号计算是以符号作为运算对象的计算，在准确计算中数字亦被当作符号看 待，符号计算包含了符号推演与准确计算，因此计算机代数亦被简称为符号计 算。符号计算的一个特点就是计算是无误差的，这是与数值计算的一个显著区 别；符号计算的另一个特点就是能进行公式推导和数学恒等式的证明。 计算机代数的成果使计算机能自动进行符号计算，这使它成为数学及其他科 学的一种有效的研究工具，这种成果的实施主要是通过计算机代数系统得以实施 的。计算机代数系统是为进行符号运算而设计的计算机软件包。目前比较流行的 通用计算机代数系统有r e d u c e ，m a p l e 【3 】，m a t h m a t i c a 和m a t l a b 。这 些系统的一个主要的特点就是： 1 用计算机代数系统不但能进行符号运算，还能进行数值计算，这为使用者 进行交互计算提供了方便。 2 这些通用系统面向一般的符号运算，能为各领域从事符号处理的科学工作 者服务。 3 对有些符号运算问题，特别是各个学科特有的问题，使用者均可基于该系 统去编制求解模块，系统语言为用户提供了程序设计语句，用户使用它们 可以编制自己的求解软件。 4 绝大多数通用计算机代数系统是从研究数学符号运算产生的，因而均具有 求解以下数学问题的能力：自然数、整数、有理数、无理数、实数、复 数、代数化简、多项式环、极限、不定积分和微分方程求解析解等。 计算机代数系统( c o m p u t e ra 1 9 e b r as y s t e m ) 的优越性主要在于它能够进 行大规模的代数运算。通常我们用笔和纸进行代数运算只能处理符号较少的算 式，当算式的符号上升到百位数后，手工计算便成为可能而不可行的事，主要原 因是在做大量符号运算时，我们很容易出错，并且缺乏足够的耐心。当算式的符 号个数上升到四位数后，手工计算便成为不可能的事，这时用计算机代数系统进 行运算就可以做到准确，快捷，有效。 3 电子科技大学硕士学位论文 尽管计算机代数系统在代替人进行繁琐的符号运算上有着无比的优越性，但 是，计算机毕竟是机器，它只能执行人们给它的指令。数学软件都有一定的局限 性。首先，多数计算机代数系统对计算机硬件有较高的要求，在进行符号运算 时，通常需要很大的内存和较长的计算时间，而精确的代数运算以时间和空间为 代价的。一些人工计算的简单问题，计算机代数系统却做不出来。用数学软件的 第二个问题是计算结果往往很长，人们很难从结果中看到问题的要害。用计算机 代数系统进行数值计算，虽然计算精度可以到任意位，但由于计算机代数系统是 用软件本身的浮点运算代替硬件算术运算，所以在速度上要比用f o r t r a n 语言算 同样的问题慢百倍甚至千倍。另外，虽然计算机代数系统包含大量的数学知识， 但这仅仅是数学的一小部分，目前有许多数学领域计算机代数系统还未能涉及。 计算机代数系统己经应用到许多应用领域，譬如：电路设计、理论物理、化 学、生物学、人工智能、工程设计和经济学等。 1 2g r 6 b n e r 基算法研究的发展历史与现状 随着社会信息化进程的加快，特别是计算机、互联网的迅速发展，代数与符 号计算的研究受到了科学工作者的高度重视，它的研究已渗透到计算代数、代数 几何、微分方程、概率统计、数值分析、编码、密码、多维系统理论等诸多领 域。g r 6 b n e r 基的理论与方法在代数与符号计算中起着关键作用，例如运用 q 曲n e r 基解大型代数方程纠4 】【5 】，g r 曲n e r 基在法国卫星6 0 0 m b 中的应用【6 】。 g r 硒n e r 基的研究吸引了越来越多的数学与工程计算等领域科学工作者，它的研 究具有十分重要的意义。近四十年来，以多变元多项式求解算法研究为核心的代 数与符号计算理论与技术得到了快速的发展。1 9 6 5 年，b b u c h b e r g e r 使用符号算 法系统地研究了域上多变元多项式环的理想生成元问题，提出了伽b n e r 基的概 念【1 7 1 ，通过计算g r 6 b n e r 基，代数理想成员的判断及数学中许多抽象的问题可以 得到较好的认识和解决。s d l w a 舵研究了( 黼b n e r 基的稳定性【8 】，接着r o b b i a n 0 研究了g 的b n e r 基的元素个数与次数的上界。1 9 8 8 年q a n i l i 运用g 舱b n e r 基研究 了理想的准素分解，同年，k a i l 耐研究了欧氏环上多元多项式环的g 砒n e r 基， 接着他们研究了可解代数( 非交换) 的锄b n e r 基。1 9 9 2 年，m 0 1 e r 利用合冲给出了 g r 6 b n e r 基计算的一个新方法【9 】，同年，f 舵p a t r i c k 运用c 晒b n e r 基较好的解决了 数值逼近中的一些问题【5 j 。1 9 9 6 年，h o n g 研究多项式复合下g r 6 b n e r 基的性质与 计算。 4 第一章引言 众所周知，可用带余除法求一个整数被另一个非零整数所除得的商和余数， 可用辗转相除法求两个整数或多个整数的最大公因子。同样地，对于有理系数多 项式或者系数在一般域上的多项式，可用长除法求一个多项式被另一个非零多项 式除得到的商多项式和余多项式，用欧几里德算法( 即多项式辗转相除法) 求两个 或多个多项式的最大公因子。实际上，这两者非常相似，用代数环论的观点看， 整数全体组成的环和任意域k 上单变元多项式组成的环k x 都是欧几里德环，当 然是主理想环。在这两个环中都有有效的除法算法和基于除法算法的用于求两个 或多个元素的最大公因子的欧几里德算法。在主理想环中，任意给定的几个元素 a l ，a 2 ，砘的最大公因子g c d ( a l ，a 2 ，a n ) 是有a l ，a 2 ，a l i 这几个元素生成的理想i 的 生成元。特别是在整环z 中和环k x 】中，要判断一个元素a 是否属于由a l ，a 2 ，a n 生成的理想i ，只要检验a 是否被g c d ( a l ，a 2 ，柚整除，是则a 属于理想i 。如果余 数或余项不为零，说明a 不能被g c d ( a 1 ，a 2 ，a n ) 整除，则a 不属于理想i 。如果我 们不利用g c d ( a l ，a 2 ，a n ) 或者没有算法可由( a l ，a 2 ，啪求出g c d ( a 1 ，a 2 ，a n ) ，判断 元素a 是否属于理想i 就不会这样简单。事实上，g c d ( a l ，a 2 ，a n ) 作为理想i 的生 成元，它不但具有好的性质，而且又有算法保证可具体求出它，这样才使得理想 成员的判定问题得以解决，用高斯消去法解有理系数或系数在一般域上的线性方 程组也是大家熟悉的，高斯消去法的本质就是将原始的线性方程组化成一组等价 的容易求解的线性方程组。从代数学的观点来看，这也是属于从理想的一组生成 元出发，设法求出一组具有好的性质的理想的另一组生成元。这里有两个问题： ( 1 ) 具有好的性质的理想生成元的代数含意是什么? ( 2 ) 如何求这组生成元? 要解决这两个问题，当然不能只局限于环z 和k x 】，我们希望对基环为一般的交 换环，甚至包括非交换环的多变元多项式环都能解决上述问题。但是，即使是在 域上，例如有理数域上的多变元( 变元个数大于2 ) 的多项式环，问题变得复杂得 多，因为这时的环不再是主理想整环。关于环中的理想，除了知道它们是有限生 成之外，再作进一步的刻画就显得十分困难，当然也就更谈不上直接推广欧几里 德算法了。然而在实际中有大量问题都要求我们能够对环中理想有进一步的刻 画，不只单纯回答与存在性相关的问题，更重要的是能够具体求解。例如，我们 要有办法判断环中一个元素是否属于给定的理想，在代数编码中码字的判别就属 于这类问题；如何检验一个理想是否是素理想，它的解决可用于判别一个代数簇 是否可约；如何计算环中理想的维数及给出理想准素分解的有效算法，因为通常 的诺特环中理想准素分解的理论并没有解决如何将一个理想具体分解；如何求解 5 电子科技大学硕士学位论文 环上，例如整数环z 和同余类环z 珈z 上的线性方程组，这是我们常遇到的问 题。此外，在计算机代数、计算代数、计算代数数论、计算代数几何、多维系统 理论、代数编码和密码学、乃至整数规划等诸多领域的许多问题，最后都可归结 为对系数取自某个环的多项式中理想的计算。确切地说，首先需要一个可执行的 有效算法，用它找到一组具有良好性质的理想生成元，进而利用这组生成元，使 得我们进而能够具有有效的算法解决与理想相关的各种问题。g f 曲n e r 基理论 【1 0 】【1 1 】就是为解决这些问题而产生和发展起来的。g r 6 b n e r 基理论的形成，可以 说经历了几十年的时间，最早我们可以追溯到1 9 2 7 年f s m a c a l l l v 的工作，他首 先将全序的概念引入到多元多项式环中单项式全体组成的集合中，他的目的是研 究理想的某些不变量；经历了将近4 0 年，h h i r o n a l ( a 于己于1 9 6 4 年在研究关于 奇性分解时，引进了多变元多项式的除法算法；在1 9 6 5 年，b b u c h b e r g e r 使用除 法算法系统地研究了域上多变元多项式环的理想生成元问题，他的基本思想是在 单项的集合中引入保持单项式的乘法运算的全序，也称为项序，以保证多项式相 除后所得余多项式唯一，他引进了s 多项式，使得对多项式环中的任一给定的理 想，从它的一组生成元出发，可计算得到一组特殊的生成元，即现在通常称之为 g i 衲n e r 基，在某些文章中也称之为s t a n d a r d 基，它具有“唯一性”的良好性质，利 用g r 6 b n e r 基，理想成员的判断及许多问题都可得到解决。因此它的出现，不只 受到代数界人士的重视，而且受到数学界、应用数学界、计算机科学界等诸多领 域的研究人员的重视，理论方面和应用方面都得到迅速发展。b n e r 基理论最 重要的，或者说b u c h b e r g e r 的最大贡献，是在于g 拍b n e r 基可以计算，而且是可 以真正求出来；此后，h g m u e n 于1 9 7 2 年研究了域上形式幂级数环的相应问 题；g b e r 舯a i l 于1 9 7 8 年对结合( 非交换) 代数和更一般的代数系统研究了 g 硒n e r 基的形式，再次发现b u c h b e r g e r 在交换情形下的算法；1 9 8 3 年， d l a z a r d 提出了用q 曲n e r 基解代数方程组的思想；1 9 8 6 年，l r o b b i a l l o 发展了 比较抽象的g 1 舶n e f 基理论。b u c h b e r g e r 在1 9 8 5 年的文章“r e e e n t 撤l n d s 试 i n u l t i d i m e n s i o n a ls y s t e mm e o r y ，中系统地研究了算法，己成为这个领域的重要文 献。其后，人们将域上多项式环的僦b n e r 基理论先推广到整数环z 上的多项式 环上，进而推广到主理想整环的多元多项式环上以及有零因子的基环，如模m 的 整数同余类环z m z ( 其中m 是一给定的整数) 上的多元多项式环。b u c h b e r g e r 和他 的学生还将g r 6 b n e r 基理论公理化，后来vw e i s p f e l l i l i n g 等人研究了非交换代数 的情形。 6 第一章引言 近十几年来，关于g r 曲懈基的应用研究发展十分迅速，这包括给出切实可 行的域上多项式环中的理想的准素分解算法，其中零维理想的准素分解的研究比 较彻底。虽然早在v a nd e rw a e r d e n 的5 0 年代出版的代数学一书中就讲述了 理想的准素分解，但那只是理论上可行，并没有具体的算法去实现。伽b n e r 基 的应用研究还包括代数方程组的求解，多项式的因子分解，多项式在代数扩域和 代数函数域中的因子分解，素理想的检验，代数流型的分解，纠错编码中循环码 和代数几何码的译码，密码学中多条序列的综合和高维线性递归阵列的分析与综 合，多维系统理论等诸多领域。 特别是在方程的求解方面，方法论大师笛卡尔( r d e s c a r t e s ) 在其著作思维 的法则里，提出了一个大胆的设想( 并对之作了伟大的实践，从而创立了解析几 何学) ： 一切问题可以化为数学问题， 一切数学问题可以化为代数问题， 一切代数问题可以化为方程求解问题。 事情当然不都可以这样一刀切，可仍不失其为一条值得珍藏的锦囊妙计。我 们所讲述的g r 6 b n e r 基的应用的很大一方面就是在方程求解中的应用，只是由于 嘶b n e r 基本身的求解算法还有一定的局限性，及其整套理论虽然是非常的成 熟，可是在计算复杂度上来说还不是很理想，所以目前还没有得到广泛的应用。 计算机代数、计算代数、计算代数几何、结算代数数论等都是近些年发展起 来的计算机科学与数学的交叉学科分支，而伽b n e f 基在其中占有重要地位。随 着计算机的小型化、大容量、高速度，可以断言，伽b n e r 基的应用前景将愈来 愈广泛，同时伽b n e r 基理论和算法的研究将会吸引更多的人。 1 3 论文研究的内容和所做的实际工作 b b u c h b e r g e r 运用g r 6 b n e r r e 丘1 1 e d 算法中应用的标准表示理论来求( 拍b n c r 基，尽管在理论上很成熟，但是在实践中很难实现，主要原因是其运算过程中的 中间项的次数急剧膨胀。在计算一组元的g i 曲n e r 基，其复杂度主要体现在s 多 项式这种中间项太多和次数太高，例如m a y r 和m e y 盱( 1 9 8 2 ) 给出了一个例子说 明，当d 是输入多项式的最大次数，运用改进的g r 6 b n e r 基算法f g l 抽n e r r e f i n e d 算法) ，则计算过程中的中间多项式的次数可高达2 ( 2 d ) ，可见当次数每增加一 次而其计算过程中的次数和中间项都是急剧地增大，同时在这么多项中，特别是 7 电子科技大学硕士学位论文 在通常变元数目不多的情况下，其中有很多项是相关的，于是就可以利用定理首 先进行约化，其中间项在初始就得到了抑制，另外也省去了一次校验的过程。 为了简化生成的s 多项式，本文研究了对多项式的化简。本文对多项式化简 所采用的方法是一种广义的带余除法，是一种条件下的多项式约化，一般的约化 所关心的是消元，而这里所说的化简首先要考虑的是降幂，其次才进行消元。在 计算机进行计算时，首先提出化简通常所要遵循的两个准则是： ( 1 ) 多项式分解因子的各变元的幂尽量低； ( 2 ) 若是变元能减少而对准则( 1 ) 的影响不是很大的话，尽量减少变元； 显然这两个准则就是矛盾的，一般所说的约化往往是能满足( 2 ) ，却难以满足准则 ( 1 ) 。因此必须对约化的方法得以改进，在约化的过程中，有一个前提就是给出了 变元的序关系。而在本文讨论的多项式及方程组，并没有既定的序关系，所以我 们采用一种动态的序关系机制。也就是说每经过一次约化就对序关系进行一次修 正。这样主要是用于在化简的同时防止某些变元的幂增长过高。这种高次多项式 化简的算法，也适用于多元高次方程的求解。在具体的计算过程中，若是次数的 浮动不是很高，且精度要求也不是很高，用一般的计算方法也就够了；但是在精 确计算中或在精度要求比较高的情况下，采用这种先进行化简的过程是很必要 的，同时也是一种有效的计算方法。另外，在符号运算的程序设计中，这类化简 也非常重要，在一般的p c 机上很难以运行m a p l e 里的g r 的n e r 基软件包对稍高 幂的多项式组的求解。例如用m a p l e 中的g r 6 b n 盱基软件包对9 次及其以上次数 的三元多项式求解，就求不出，因此对算法的优化是非常有意义的。 在对多项式化简的过程当中涉及到大量的多项式的四则运算，尤其是乘除运 算。为了提高多项式约化操作的效率，课题利用m m 主机系统强大的科学运算能 力，研究了在其平台下进行多项式四则运算的实施。在多项式的运算中，中间结 果项的系数往往会超出机器字长所表示的范围，这就要求知道怎样在固定字长的 机器中表示大整数，以及进行大整数的四则运算。这也是本文的先行研究内容。 有了以上的基础，本文最后研究了对改进的g r 6 b n e r 基算法q 曲n e r r e f i n e d 算法 的改进。主要要做的工作是对相关项的分类和定理的运用，达到减少复杂度的目 的。较c 拍b n e r r e f i n e d 算法是对整个元进行运算，而本文采用的是一种“各个击 破”的方式，在运算过程中进行的是相关项的集合的运算，另外就是这种算法占 用的内存相对较少，因而减少了存储空间的占用，达到了优化的效果。 本人的具体工作包括： 8 第一章引言 熟悉i b m 主机系统的交互式集成环境s d s f 以及在此环境下进行c 程序的 开发和调试； 研究基于6 4 位机器环境的大整数的表示及其四则运算，并编写成函数库 在i b m 主机系统下实现： 研究基于6 4 位机器环境的多元多项式的存储结构及其四则运算，并编写 成函数库在i b m 主机系统下实现； 研究实现化简s 多项式的降幂约化算法，并用m a p l e 语言实现； 研究基于降幂约化算法的对改进的c 拍b n e r 基算法g r 6 b n e r r e 丘n e d 算法的 改进； 1 4 论文结构组织 第一章介绍了计算机代数和g f 6 b n e r 基算法研究的发展历史和现状，并明确 了本论文的主要工作以及要解决的关键问题； 第二章是为后面介绍算法改进思想做的理论准备，其核心内容是多项式的约 化思想，并介绍了大整数和多元多项式在i b m 主机系统下的表示方法和四则运算 的算法及其实现，同时简单介绍了本课题实施的开发环境和工具； 第三章在讲解g r 6 b n e r 基的基本概念以及求g r 6 b n e r 基的经典算法和改进的 g r 6 b n e r r e 矗n e d 算法的基础上提出了本文的中心问题：运用b u c h b e r g e r 的改进算 法在求g m n e r 基的运算过程中会出现中间项的次数急剧膨胀的现象。 第四章讲述的是求僦b n e r 基算法的改进和实现； 第五章介绍了僦沁n e r 基的应用，其重点讲述的是僦b n e r 基和约化在图中 关于最短路径问题的应用； 第六章对全文进行了总结，强调了本文改进的算法较之原算法的优越之处以 及创新点，同时对作者以后的研究方向和内容做出了期望； 9 电子科技大学硕士学位论文 第二章理论背景 2 1 大整数的表示及其运算 在多项式的运算中，中间结果项的系数往往会超出机器字长所表示的范围， 这就要求知道怎样在固定字长的机器中表示大整数，以及进行大整数的四则运 算。 在计算机代数中，数据的计算必须是精确的，不容许有舍入误差，因此数据 都通过整数来表示。由于计算机的字长有限，例如一台6 4 位计算机所能表示的 整数只能在2 6 3 ，2 6 3 1 之间，这也是本文工作的计算机环境。因此，如何在计算 机上表示大整数就成为计算机代数的数据处理中最基本的问题。实际上，即使所 给的初始数据在计算机的字长可以表示的范围内，计算过程中数据有时也会很快 的膨胀。例如，求多项式 a = x 8 + x 6 3 x 4 3 x 3 + 8 x 2 + 2 x 5 ， b = 3 x 6 + 5 x 4 4 】【2 9 x + 2 l 的最大公因子，若用e u c l i d 算法，并在计算过程中适时地把有理数化成整数，所 得到的余式序列为 1 5 x 4 + 3 x 3 9 ， 1 5 7 9 5 x 2 + 3 0 3 7 5 x 5 9 5 3 5 ， 1 2 5 4 5 4 2 8 7 5 1 4 3 7 5 0 x 一1 6 5 4 6 0 8 3 3 8 4 3 7 5 0 0 ， 1 2 5 9 3 3 3 8 7 9 5 5 0 0 7 4 3 1 0 0 9 3 1 1 4 1 9 9 2 1 8 7 5 0 0 。 由此例看出，虽然初始数据不是很大，但在运算过程中数据膨胀得很快。数据膨 胀现象与计算方法有密切关系，这是不言而喻的。最简单的例子就是有理数，即 分数的乘除法计算。一方面，如果参与运算的有理数不是既约的，即分子分母有 非平凡公因子，那么先约分后乘除与先乘除后约分，两者的中间数据大小显然是 有差别的，这就要求尽可能选择适当的计算方法，以便能有效的控制数据的膨胀 速度；另一方面，现有的计算机字长都有可能无法表示计算过程中所产生的整数 ( 我们称这样的整数为大整数) ，这就要求研究大整数在具有固定字长的计算机 上的表示与运算【2 1 。 因为整数环为e u c l i d 整环，对给定的两个整数a 与b ，存在整数q 与r ，使得 1 0 第二章理论背景 a2q b + r ，osr l ，使其能在计算机 上单精度表示，当要表示的数不超过b 时，该数可以用“一位数”表示，当要表示 的数超过b 时，也要进位。接下来的问题是，对于给定的一正整数a ，它到底可 以表示成多少位? 各个数位上的单精度数应该怎样计算? 其实很简单，利用带余 除法即可求得其位数k + 1 及b o 位，b 1 位上的单精度数字a i 之0 ，i = o ， k 1 ，a l 【 0 ，使得 a = a k b k + a k 1 b k 1 + + a o b o ( 2 2 ) 容易证明这种表示是唯一的，于是a 可以表示成 a = ( a k ，a k i ，a 0 ) 有时为了强调所选的那个单精度数b ，也将该大整数记做 a = ( a k ，a “l ，a o ) b 上述表示称为a 关于基b 的展开。我们称其为k + l 位b 进制整数。 例如取b = 2 ，即为通常的二进制表示，而取b = 1 0 即为十进制。一般的， 为了满足符号计算中的需要，b 可选成2 或1 0 的乘幂。1 0 的乘幂可以使输入输 出容易处理；2 的乘幂可以使内部运算效率更高。同时b 应选得既足够大，又使 计算机能够表示并进行不超过b 的数的各种运算，一般的原则是，b 2 可以用一个 计算机的字表示，对于6 4 位的计算机，b = 1 0 9 。 对于给定的a 和b ，欲求a 关于基b 的展开，可用下列算法。 q 0 2a ； 虬l = 懈n ( q k - l ，b ) ； q k2q u o ( q k - i ，b ) ，k = 1 ， 电子科技大学硕士学位论文 注意到q k 严格单调递减，上述