• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Symbolic and Algebraic Computation Aug 3-6, 2003 Philadelphia, Pennsylvania, USA >On the Complexity of Polynomial Matrix Computations
【24h】

On the Complexity of Polynomial Matrix Computations

机译：多项式矩阵计算的复杂性

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

摘要

We study the link between the complexity of polynomial matrix multiplication and the complexity of solving other basic linear algebra problems on polynomial matrices. By polynomial matrices we mean n x n matrices in K[x] of degree bounded by d, with K a commutative field. Under the straight-line program model we show that multiplication is reducible to the problem of computing the coefficient of degree d of the determinant. Conversely, we propose algorithms for minimal approximant computation and column reduction that arc based on polynomial matrix multiplication; for the determinant, the straight-line program we give also relies on matrix product over K[x] and provides an alternative to the determinant algorithm of [16, 17]. We further show that all these problems can be solved in particular in O~-(n~ωd) operations in K. Here the "soft O" notation O~~ indicates some missing, log(nd) factors and ω is the exponent of matrix multiplication over K.
机译：我们研究了多项式矩阵乘法的复杂性与解决多项式矩阵上其他基本线性代数问题的复杂性之间的联系。多项式矩阵是指以d为边界的度数K [x]中的n x n个矩阵，其中K是交换场。在直线程序模型下，我们证明了乘法可简化到计算行列式的度数d的问题。相反，我们提出了基于多项式矩阵乘法的最小近似计算和列约简算法。对于行列式，我们给出的直线程序也依赖于K [x]上的矩阵乘积，并提供了行列式算法[16，17]的替代方案。我们进一步证明，所有这些问题都可以在K中的O〜-（n〜ωd）运算中解决。在这里，“软O”表示法O ~~表示一些缺失的log（nd）因子，而ω是K上的矩阵乘法

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号