• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >Asymptotically Fast Triangularization of Matrices over Rings.
【24h】

Asymptotically Fast Triangularization of Matrices over Rings.

机译：环上矩阵的渐近快速三角化。

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider problems related to the computation of Hermite and Smith normal forms of integer matrices, and more generally matrices over a principal ideal ring. First, we show that if the matrix A is m (times) n, with rank m and integer entries bounded in absolute value by T, then the Hermite normal form can be computed in O(m(sup 2)nB(m log(mT))) bit operations, where B(t) denotes a function that bounds the time required to perform the extended Euclidean algorithm on two t bit integers. Furthermore we show that the Smith normal form can be computed in O(m(sup 3)nB(m log(mT))log(mT)) bit operations. In the second part of the paper we apply fast matrix multiplication techniques to the problem of triangularizing a matrix over a ring using elementary column operations. We also prove that matrix inversion and multiplication are equivalent in complexity over an arbitrary Principal Ideal Domain, generalizing a result of Bunch and Hopcroft. We then apply our general results to obtain an algorithm for triangularizing integer matrices that has a faster running timer than the known Hermite normal form algorithms. The triangular matrix that is computed has small entries like the Hermite normal form, and will suffice for many applications. In the last part of the paper, we discuss a probabilistic method for calculating Smith normal forms. 17 refs.

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号