COMPUTING EXACT DETERMINANT OF MATRICES WITH POLYNOMIAL ENTRIES

作     者：HOROWITZ, E SAHNI, S 

作者机构：UNIV SO CALIFCOMP SCI PROGRAMLOS ANGELESCA 90007 UNIV MINNESOTADEPT COMP INFORMATION & CONTROL SCIMINNEAPOLISMN 55455 

出 版 物：《JOURNAL OF THE ACM》 (J. ACM)

年 卷 期：1975年第22卷第1期

页      面：38-50页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：characteristic polynomial determinants expansion by minors Gaussian elimination matrix of polynomials 

摘      要：The problem of computing the determinant of a matrix of polynomials is considered. Four algorithms are compared- expansion by minors, Gausslan elimination over the integers, a method based on evaluation and interpolation, and a procedure which computes the characteristic polynomial of the matrix. Each method m analyzed with respect to its computing time and storage requirements using several models for polynomial growth. First, the asymptotic time and storage is developed for each method within each model. In addition to these asymptotm results, the analysis is done exactly for certain especially small, yet practical and important cases Then the results of empirical studies are given which support conclusions about which of the methods will work best within an actual computing environment. © 1975, ACM. All rights reserved.