Computing Hermite Forms of Polynomial Matrices

被引：0
作者：
Gupta, Somit [1 ]
Storjohann, Arne [1 ]
机构：
[1] Univ Waterloo, David R Cheriton Sch Comp Sci, Waterloo, ON N2L 3G1, Canada
来源：
ISSAC 2011: PROCEEDINGS OF THE 36TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION | 2011年
关键词：
Hermite form; Polynomial matrices; COMPUTATION;
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
This paper presents a new algorithm for computing the Hermite form of a polynomial matrix. Given a nonsingular n x n matrix A filled with degree d polynomials with coefficients from a field, the algorithm computes the Hermite form of A using an expected number of (n(3)d)(1+0(1)) field operations. This is the first algorithm that is both softly linear in the degree d and softly cubic in the dimension n. The algorithm is randomized of the Las Vegas type.
引用
收藏
页码：155 / 162
页数：8
相关论文
共 28 条
  • [1] Beckermann B, 1999, ISSAC 99: PROCEEDINGS OF THE 1999 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, P189, DOI 10.1145/309831.309929
  • [2] A UNIFORM APPROACH FOR THE FAST COMPUTATION OF MATRIX-TYPE PADE APPROXIMANTS
    BECKERMANN, B
    LABAHN, G
    [J]. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1994, 15 (03) : 804 - 823
  • [3] Normal forms for general polynomial matrices
    Beckermann, Bernhard
    Labahn, George
    Villard, Gilles
    [J]. JOURNAL OF SYMBOLIC COMPUTATION, 2006, 41 (06) : 708 - 737
  • [4] Cohen H., 1996, A Course in Computational Algebraic Number Theory
  • [5] HERMITE NORMAL-FORM COMPUTATION USING MODULO DETERMINANT ARITHMETIC
    DOMICH, PD
    KANNAN, R
    TROTTER, LE
    [J]. MATHEMATICS OF OPERATIONS RESEARCH, 1987, 12 (01) : 50 - 59
  • [6] DOMICH PD, 1983, THESIS CORNELL U ITH
  • [7] DOMICH PD, 1985, THESIS CORNELL U ITH
  • [8] On computing the determinant and Smith form of an integer matrix
    Eberly, W
    Giesbrecht, M
    Villard, G
    [J]. 41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, : 675 - 685
  • [9] Giorgi Pascal, 2003, P ISSAC, P135, DOI [10.1145/860854.860889, DOI 10.1145/860854.860889]
  • [10] Gupta S., 2010, TRIANGULAR X B UNPUB, V10
123