• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of complexity >Computing syzygies in finite dimension using fast linear algebra
【24h】

Computing syzygies in finite dimension using fast linear algebra

机译：使用快速线性代数计算有限尺寸的Syzygies

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider the computation of syzygies of multivariate polynomials in a finite-dimensional setting: for a K[X-1,..., X-r]-module M of finite dimension D as a K-vector space, and given elements f(1),...,f(m) in M, the problem is to compute syzygies between the f(i)'s, that is, polynomials (p(1),...,p(m)) in K[X-1,...,X-r](m) such that p(1)f(1) + ... + p(m)f(m) = 0 in M. Assuming that the multiplication matrices of the r variables with respect to some basis of M are known, we give an algorithm which computes the reduced Grobner basis of the module of these syzygies, for any monomial order, using O(mD(omega-1) + rD(omega) log(D)) operations in the base field K, where. is the exponent of matrix multiplication. Furthermore, assuming that M is itself given as M = K[X-1,...,X-r](n)/N, under some assumptions on N we show that these multiplication matrices can be computed from a Grobner basis of N within the same complexity bound. In particular, taking n = 1, m = 1 and f1 = 1 in M, this yields a change of monomial order algorithm along the lines of the FGLM algorithm with a complexity bound which is sub-cubic in D. (C) 2020 Elsevier Inc. All rights reserved.
机译：我们考虑在有限尺寸设定中计算多变量多项式的Syzygies：用于有限尺寸D作为K-载体空间的K [X-1，...，XR] - 给定元素F（1 ），...，f（m）在m中，问题是计算f（i）的syzygies，即，多项式（p（1），...，p（m））在k中[ X-1，...，XR]（M），使得P（1）F（1）+ ... + P（M）F（M）= 0在M.假设R变量的乘法矩阵关于M的某种基础是已知的，我们提供了一种算法，其使用O（MD（OMEGA-1）+ Rd（OMEGA）Log（D）为任何单项顺序计算这些Syzygies模块的模块的降低基础）基础字段K中的操作，其中。是矩阵乘法的指数。此外，假设M本身作为m = k [x-1，...，xr]（n）/ n在n上的某些假设下，我们示出了这些乘法矩阵可以从N内的GROBNER计算相同的复杂性绑定。特别地，在m中取n = 1，m = 1和f1 = 1，这产生了沿着FLM算法的线的单体阶算法的变化，其复杂性绑定在D.（c）2020 eleorvier中是子立方Inc.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号