Analysis of algorithms, a case study: Determinants of polynomials

ABSTRACT

We consider the problem of computing the determinant of a matrix of polynomials; we compare two algorithms (expansion by minors and Gaussian elimination), examining each under two models for polynomial computation (dense univariate and totally sparse). The results, while interesting in themselves, also serve to display two points: 1. Asymptotic results are sometimes misleading for noninfinite (e.g., practical) problems. 2. Models of computation are by definition simplifications of reality: Algorithmic analysis should be carried out under several distinct computational models, and should be supported by empirical data.

REFERENCES

• 1: W. Morven Gentleman, Optimal multiplication chains for computing a power of a symbolic polynomial, ACM SIGSAM Bulletin [doi>10.1145/1093425.1093426]
• 2: Heindel, L.E., "Computation of Powers of Multivariate Polynomials over the Integers", Journal of Computer and System Science, vol. No. 1, Feb. 1972.
• 3: Fateman, Richard J., "On the Computational Powers of Polynomials", Department of Mathematics Report, M.I.T. Cambridge, Mass.
• 4: Bareiss, E.H., "Silvester's Identity and Multistep Integer-Preserving Gaussian Elimination", Math. Comp., 22 (1968), pp. 565-578.
• 5: Lipson, J.D., “Symbolic Methods for the Computer Solution of Linear Equations with Applications to Flow-graphs", in P.G. Tobey, (Ed.), Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, I.B.M. Programming Laboratory Report FSC69-0312, June 1969.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory

General Terms:
Theory