Analysis of Algorithms, A Case Study: Determinants of Matrices With Polynomial Entries W. M. GENTLEMAN University of Waterloo and S. C. JOHNSON Bell Telephone Laboratories The problem of computing the deternunant of a matrix of polynomials IS considered; two algo. rithms (expansion by minors and expansion by Gaussian ehmmatmn) are compared; and each is examined under two models for polynomial computatmn (dense univanate and totally sparse). The results, while interesting in themselves, also serve to display two points: (1) Asymptotic results are sometimes misleading for noninfimte (e.g. practical) problems. (2) Models of computa- tion are by definition simplifications of reahty: algorithmic analysis should be carried out under several distract computatmnal models and should be supported by empirical data. Key Words and Phrases: symbohc algebraic computation, analysm of algorithms, determinants of polynomial matrices CR Categories: 5.25, 5.7 1. INTRODUCTION Some algorithms which are efficient for integer computations are distinctly sub- optimal for the analogous polynomial computations. As an example, Gentleman E3] studied powering of polynomials and showed that, even in the computation of p4, it can be faster to compute this as ((p~)p)p than as (p2)2 (as one would for fixed-length integers). Heindel [-4~ and Fireman [-2J have also studied this prob- lem, using more than one model. We examine the computation of determinants of n-by-n matrices with poly- nomial entries. At the outset we shall restrict our problem still further by ignoring the important case where the matrix has many zero entries and by assuming that the entries in the matrix are all the same size. Our analysis focuses on two algo- rithms, Gaussian elimination and expansion by minors, and two computational models, dense univariate and totally sparse; Section 2 describes the algorithms; Section 3 describes the models; and Section 4 describes the application of these Copyright (~) 1976, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted provided that ACM's copyright notice is given and that reference is made to the pubhcatlon, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery. This work was supported in part by the National Research Council of Canada under Grant A7407 Authors' addresses: W.M Gentleman, Mathematics Faculty Computing Faclhty, University of Waterloo, Waterloo, Ont., Canada, S.C. Johnson, Bell Telephone Laboratories, Murray Hill, NJ 07974. ACM Transactions on Mathematical Software, Vol. 2, No. 3, September 1976, Pages 232-241.Analysis of Algorithms 233 models to the two algorithms. Finally, Sections 5 through 7 discuss the results of the theoretical analysis and give some empirical data in support of these results. 2. THE DETERMINANT PROBLEM Suppose we are given an n-by-n matrix of polynomials. We consider two ways of computing the determinant of this matrix: Gaussian elimination and expansion by minors. We assume that all the entries in the matrix are of equal size. We first describe the Gaussian elimination method, using exact division, which is appropriate for computations over the integers; an Altran program is given in Appendix I. If we ignore pivoting, the algorithm consists of n-1 steps, indexed by a variable k running from 1 to n- 1. The kth step involves the computation of an n-k+l by n-k+l matrix, which we shall call A(k+l); the entries will be de- noted a~ +1), with k < z, j _< n. The original matrix is identified with A (1). For each k, the entry a~ +1) is computed by the formula a(k+l) f,~ (k) ~ (k) ,~ (k) ~ (k) ~/,~ (k--l) *3 ~ \~kk ~,j -- ~" ,k ~'k3 ]/~k--l,k--1 for k+l < ,, j < n, where ,(0) is taken to be 1. The division is always exact, so __ __ wOO (k) is a polynomial, and -(") is the determinant of A (n) that each a, (tnn An analysis of this algorithm (see Bareiss [-1~, Lipson [-5~) shows that each a(k) is a determinant (minor) of some k-by-k submatrix of the original matrix. ~3 Since we assumed all entries in the original matrix to be of the same size, we may expect that all elements in A (k), for a given/z, are the same size. To compute a~ ) takes two multiplications, a subtraction, and a division. In general, the cost of multiplying two polynomials will depend on their size; in our situation the size is assumed to depend only on the order of the minor making up the element. Thus we shall use numbers C~, to compute the cost of our algorithm, C,, is the cost of multiplying a minor of order r by a minor of order s. Notice that C~.I is the cost of multiplying two elements from the original matrix. We assume also that an exact division of A by B to yield C has the same cost as a multiplica- tion of B by C, and we ignore the costs of addition and subtraction. We can now write the cost for Gaussian elimination in terms of the C,~. To com- pute a~ +1) requires two multiplications of cost Ckk, a division of cost Ck-~.k+~, and a subtraction whose cost we do not count. There are, for a given/~, (n- k) 2 elements a~+i); so the total cost for the Gaussian elimination is n--1 G = ~ (n- k)~(2C~ + C~_~,~+~). k~l Note that, when C~, = 1 for all r and s, representing the familiar floating-point or fixed-length integer case, the cost becomes n--1 G = 3 ~_, (n-k) 2 = n 3- ~n 2-{- ½n. k~l We now turn our attention to the expansion by minors algorithm; an Altran pro- gram for this is given in Appendix II. We again have n--1 steps, indexed by k from 2 to n. At each step, we compute all of the k-by-k minors from the first /~ ACM Transactions on MathematmM Software, ¥ol. 2, No 3, September 197fi234 W.M. Gentleman and S. C. Johnson columns (there are (~) of them), using the k- 1 by k- 1 minors from the first k- 1 columns, computed in the previous step. We ignore the bookkeeping and concen- trate on the cost of the polynomial operations. Computing each k-by-k minor in- volves k multiplications, and k-1 additions and subtractions, which we ignore. Thus, using the C~,, each