FAST PARALLEL COMPUTATION OF HERMITE AND SMITH FORMS OF POLYNOMIAL-MATRICES

作     者：KALTOFEN, E KRISHNAMOORTHY, MS SAUNDERS, BD 

作者机构：UNIV DELAWAREDEPT COMP & INFORMAT SCINEWARKDE 19716 

出 版 物：《SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS》 

年 卷 期：1987年第8卷第4期

页      面：683-690页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：15A21 68Q40 15A54 parallel algorithm Hermite normal form Smith normal form polynomial-time complexity probabilistic algorithm matrix normal form polynomial matrix invariant factor 

摘      要：Boolean circuits of polynomial size and polylogarithmic depth are given for computing the Hermite and Smith normal forms of polynomial matrices over finite fields and the field of rational numbers. The circuits for the Smith normal form computation are probabilistic ones and also determine very efficient sequential algorithms. Furthermore, we give a polynomial-time deterministic sequential algorithm for the Smith normal form over the rationals. The Smith normal form algorithms are applied to the rational canonical form of matrices over finite fields and the field of rational numbers.