Article

Free access

Analysis of algorithms, a case study: Determinants of polynomials

Authors:

W. M. Gentleman,

S. C. JohnsonAuthors Info & Claims

STOC '73: Proceedings of the fifth annual ACM symposium on Theory of computing

Pages 135 - 141

https://doi.org/10.1145/800125.804044

Published: 30 April 1973 Publication History

PDF eReader

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]

Gentleman, W.M., "Optimal Multiplication Chains for Computing a Power of a Symbolic Polynomial" SIGSAM Bulletin No. 18, April 1971, which appears in Math. of Comp. Vol.26, No. 120, Oct.'72.

Digital Library

Google Scholar

[2]

Heindel, L.E., "Computation of Powers of Multivariate Polynomials over the Integers", Journal of Computer and System Science, vol. No. 1, Feb. 1972.

Google Scholar

[3]

Fateman, Richard J., "On the Computational Powers of Polynomials", Department of Mathematics Report, M.I.T. Cambridge, Mass.

Google Scholar

[4]

Bareiss, E.H., "Silvester's Identity and Multistep Integer-Preserving Gaussian Elimination", Math. Comp., 22 (1968), pp. 565-578.

Google Scholar

[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.

Google Scholar

Cited By

View all

Taheri SBoostanpour JMohammadi B(2013)A Novel Algorithm for determinant calculation of N×N matrix2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI)10.1109/ICACCI.2013.6637270(764-769)Online publication date: Aug-2013
https://doi.org/10.1109/ICACCI.2013.6637270
Moenck RCarter J(2005)Approximate algorithms to derive exact solutions to systems of linear equationsSymbolic and Algebraic Computation10.1007/3-540-09519-5_60(65-73)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-09519-5_60
Wang PMinamikawa TGriesmer JCaviness B(1976)Taking advantage of zero entries in the exact inverse of sparse matricesProceedings of the third ACM symposium on Symbolic and algebraic computation10.1145/800205.806354(346-350)Online publication date: 10-Aug-1976
https://dl.acm.org/doi/10.1145/800205.806354
Show More Cited By

Index Terms

Analysis of algorithms, a case study: Determinants of polynomials
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials
2. Theory of computation
  1. Models of computation
    1. Computability

Recommendations

Sum Amusements: A Case Study from the Analysis of Algorithms
A study of Hensel series in general case
SNC '11: Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation

The Hensel series is a series expansion of multivariate algebraic function at its singular point. The Hensel series is computed by the (extended) Hensel construction, and it is expressed in a well-structured form. In previous papers, we clarified ...
Complexity analysis of algorithms in algebraic computation

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '73: Proceedings of the fifth annual ACM symposium on Theory of computing

April 1973

282 pages

ISBN:9781450374309

DOI:10.1145/800125

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 1973

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
135
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)5

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Taheri SBoostanpour JMohammadi B(2013)A Novel Algorithm for determinant calculation of N×N matrix2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI)10.1109/ICACCI.2013.6637270(764-769)Online publication date: Aug-2013
https://doi.org/10.1109/ICACCI.2013.6637270
Moenck RCarter J(2005)Approximate algorithms to derive exact solutions to systems of linear equationsSymbolic and Algebraic Computation10.1007/3-540-09519-5_60(65-73)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-09519-5_60
Wang PMinamikawa TGriesmer JCaviness B(1976)Taking advantage of zero entries in the exact inverse of sparse matricesProceedings of the third ACM symposium on Symbolic and algebraic computation10.1145/800205.806354(346-350)Online publication date: 10-Aug-1976
https://dl.acm.org/doi/10.1145/800205.806354
Yun DGriesmer JCaviness B(1976)Algebraic algorithms using p-adic constructionsProceedings of the third ACM symposium on Symbolic and algebraic computation10.1145/800205.806343(248-259)Online publication date: 10-Aug-1976
https://dl.acm.org/doi/10.1145/800205.806343
Griss MGosden JJohnson O(1976)An efficient sparse minor expansion algorithmProceedings of the 1976 annual conference10.1145/800191.805633(429-434)Online publication date: 20-Oct-1976
https://dl.acm.org/doi/10.1145/800191.805633
Moses J(1974)MACSYMA - the fifth yearACM SIGSAM Bulletin10.1145/1086837.10868578:3(105-110)Online publication date: 1-Aug-1974
https://dl.acm.org/doi/10.1145/1086837.1086857

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Sum Amusements: A Case Study from the Analysis of Algorithms

A study of Hensel series in general case

Complexity analysis of algorithms in algebraic computation