学位论文 > 优秀研究生学位论文题录展示

IBM主机代数库的开发和Gr（?）bner基算法的研究

作　者: 何海龙
导　师: 许毅
学　校: 电子科技大学
专　业: 计算机应用技术
关键词: 约化 Gr(o ¨)bner基 S-多项式 序关系 S-簇
分类号: TP311.52
类　型: 硕士论文
年　份: 2008年
下　载: 20次
引　用: 0次
阅　读: 论文下载
 

内容摘要


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

全文目录


摘要  4-5
Abstract  5-11
第一章 引言  11-20
  1.1 历史背景  11-14
  1.2 Gr(o|¨)bner基算法研究的发展历史与现状  14-17
  1.3 论文研究的内容和所做的实际工作  17-19
  1.4 论文结构组织  19-20
第二章 理论背景  20-47
  2.1 大整数的表示及其运算  20-33
    2.1.1 大整数的表示  22-26
    2.1.2 大整数的运算  26-31
    2.1.3 IBM 主机系统下的实现和调试  31-33
  2.2 多项式的表示和运算  33-38
    2.2.1 多项式的存储结构  33-34
    2.2.2 多项式的乘法运算的实现  34-35
    2.2.3 多项式的除法运算的实现  35-37
    2.2.4 IBM 主机系统下的实现和调试  37-38
  2.3 多项式环与理想的基本概念  38-40
  2.4 问题提出  40
  2.5 降幂约化的原理及方法  40-43
    2.5.1 降幂约化的原理  40-42
    2.5.2 算法与编程  42-43
  2.6 开发环境及工具简介  43-46
    2.6.1 IBM 主机系统概述  43-44
    2.6.2 Maple简介  44-46
  2.7 本章小结  46-47
第三章 问题的提出  47-53
  3.1 Gr(o|¨)bner基及其求Gr(o|¨)bner基的经典算法  47-51
    3.1.1 Gr(o|¨)bner 基的基本理论  47-49
    3.1.2 Buchberger 算法  49-51
  3.2 Gr(o|¨)bnerRefined算法  51
  3.3 本章小结  51-53
第四章 算法的改进和实现  53-60
  4.1 改进的基本原理  53-54
  4.2 Gr(o|¨)bnerRefined算法的改进  54-55
  4.3 测试分析  55-59
  4.4 本章小结  59-60
第五章 Gr(o|¨)bner 基的应用  60-68
  5.1 Gr(o|¨)bner基及约化在图中的应用  60-64
    5.1.1 引言  60-61
    5.1.2 Gr(o|¨)bner 基及约化求图的最短路径  61-64
  5.2 其他应用  64-66
    5.2.1 代数几何中的代数簇包含问题  64-65
    5.2.2 几何定理自动证明  65
    5.2.3 专家系统  65-66
    5.2.4 铁路联锁系统  66
  5.3 本章小结  66-68
第六章 结论  68-70
致谢  70-71
参考文献  71-74
附录一 大整数链表表示函数  74-79
附录二 多元多项式的输入转换函数  79-83
附录三 Gr(o|¨)bnerRefined 算法  83-84
在学期间研究成果及发表的学术论文  84-85

相似论文

  1. 带有多项式基的径向点插值无网格方法的研究及应用,O241
  2. 腈纶生产线移动装箱机的设计与研究,TH248
  3. 基于功能节点的无线传感器网络多对密钥管理协议研究,TP212.9
  4. 中学数学竞赛中二次多项式与二次函数问题的研究,G633.6
  5. 七维稳定耗散系统的代数条件及动力学性质,O175
  6. 阿特拉津降解菌生物学特性的研究，关键降解酶基因克隆及基因簇的构建,X172
  7. 簇毛麦6V染色体短臂小片段易位系的分子细胞遗传学鉴定,S512.1
  8. 涉及微分多项式和例外函数的正规定则,O174
  9. 基于行为可信的无线传感器网络入侵检测技术的研究,TP212.9
  10. 基于无线传感器网络的农田环境监测系统路由协议的研究,TN915.04
  11. 咪唑离子液体在溶液中的簇集和微观结构研究,O645.1
  12. 抑制糖皮质激素受体（GR）表达建立肾阳虚小鼠模型,R-332
  13. 移动WSN基于虚拟簇头数据收集策略的研究,TP212.9
  14. 基于多层WSN结构的非均匀簇路由协议研究,TP212.9
  15. 簇毛麦抗白粉病基因Hv-S/TPK的抗病机理分析及其旁侧抗病基因类似物的克隆,S512.1
  16. 躯体传感器网络自适应通信协议研究,TP212.9
  17. 整系数多项式的因式分解方法研究,O174.14
  18. WnC0,±（n=1-6）团簇的密度泛函理论研究,O641.1
  19. (OsnN)0, ±（n=1-6）团簇结构与性能的理论研究,O641.1
  20. 无线传感器网络中基于簇的路由协议研究,TP212.9
  21. 基于分簇的移动sink传感网路由算法研究,TP212.9

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 软件工程 > 软件开发
© 2012 www.xueweilunwen.com