skip to main content
10.1145/1277548.1277590acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

Faster algorithms for the characteristic polynomial

Published: 29 July 2007 Publication History

Abstract

A new randomized algorithm is presented for computing the characteristic polynomial of an n x n matrix over a field. Over a suffciently large field the asymptotic expected complexity of the algorithm is O(nθ)field operations, improving by a factor of log n on the worst case complexity of Keller-Gehrig's algorithm [11].

References

[1]
R.A. DeMillio and R.J. Lipton. A probabilistic remark on algebraic program testing. Inf. Proc. Letters 7(4):193--195, 1978.
[2]
J.-G. Dumas, T. Gautier, and C. Pernet. Finite field linear algebra subroutines. In Proc. ISSAC'02 pages 63--74. ACM Press, New York, 2002.
[3]
J.-G. Dumas, P. Giorgi, and C. Pernet. Finite field linear algebra package. In Proc. ISSAC'04 pages 119--126. ACM Press, New York, 2004.
[4]
J.-G. Dumas, C. Pernet, and Z. Wan. Efficient computation of the characteristic polynomial. In Proc. Proc. ISSAC'05 pages 140--147. ACM Press, New York, 2005.
[5]
W. Eberly. Asymptotically efficient algorithms for the Frobenius form. Technical report, Department of Computer Science, University of Calgary, 2000.
[6]
F.R. Gantmacher. The Theory of Matrices volume1. Chelsea Publishing Company, New York, NY, 1990.
[7]
M. Giesbrecht. Nearly Optimal Algorithms for Canonical Matrix Forms PhD thesis, University of Toronto, 1993.
[8]
M. Giesbrecht. Nearly optimal algorithms for canonical matrix forms. SIAM Journal of Computing 24:948--969, 1995.
[9]
K. Hoffman and R. Kunze. Linear Algebra Prentice-Hall, Englewood Clikffs, N.J., 1971.
[10]
O. Ibarra, S. Moran, and R. Hui. A generalization of the fast LUP matrix decomposition algorithm and applications. Journal of Algorithms 3:45--56, 1982.
[11]
W. Keller-Gehrig. Fast algorithms for the characteristic polynomial. Theoretical Computer Science 36:309--317, 1985.
[12]
J.T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27:701--717, 1980.
[13]
A. Storjohann. Algorithms for Matrix Canonical Forms PhD thesis, Swiss Federal Institute of Technology, ETH-Zurich, 2000.
[14]
A. Storjohann. Deterministic computation of the Frobenius form (Extended Abstract). In Proc. 42nd Annual Symp. Foundations of Comp. Sci. pages 368--377, Los Alamitos, California, 2001. IEEE Computer Society Press.
[15]
G. Villard. A study of Coppersmith's block Wiedemann algorithm using matrix polynomials. Technical Report RR 975-I-M, IMAG Grenoble France, 1997.
[16]
R. Zippel. Probabilistic algorithms for sparse polynomials. In Proc. EUROSAM 79 pages 216--226, Marseille, 1979.

Cited By

View all
  • (2024)Computing Krylov iterates in the time of matrix multiplicationProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669715(419-428)Online publication date: 16-Jul-2024
  • (2024)Discrete Markov Processes and Numerical Algorithms for Markov ChainsMarkov Decision Processes and Stochastic Positional Games10.1007/978-3-031-40180-0_1(1-124)Online publication date: 13-Jan-2024
  • (2022)Faster Change of Order Algorithm for Gröbner Bases under Shape and Stability AssumptionsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535484(409-418)Online publication date: 4-Jul-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation
July 2007
406 pages
ISBN:9781595937438
DOI:10.1145/1277548
  • General Chair:
  • Dongming Wang
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. characteristic polynomial
  2. complexity
  3. frobenius normal form

Qualifiers

  • Article

Conference

ISSAC07
Sponsor:
ISSAC07: International Symposium on Symbolic and Algebraic Computation
July 29 - August 1, 2007
Ontario, Waterloo, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)23
  • Downloads (Last 6 weeks)4
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Computing Krylov iterates in the time of matrix multiplicationProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669715(419-428)Online publication date: 16-Jul-2024
  • (2024)Discrete Markov Processes and Numerical Algorithms for Markov ChainsMarkov Decision Processes and Stochastic Positional Games10.1007/978-3-031-40180-0_1(1-124)Online publication date: 13-Jan-2024
  • (2022)Faster Change of Order Algorithm for Gröbner Bases under Shape and Stability AssumptionsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535484(409-418)Online publication date: 4-Jul-2022
  • (2021)Deterministic computation of the characteristic polynomial in the time of matrix multiplicationJournal of Complexity10.1016/j.jco.2021.10157267:COnline publication date: 1-Dec-2021
  • (2020)On the uniqueness of simultaneous rational function reconstructionProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3404051(226-233)Online publication date: 20-Jul-2020
  • (2020)Elimination-based certificates for triangular equivalence and rank profilesJournal of Symbolic Computation10.1016/j.jsc.2019.07.01398:C(246-269)Online publication date: 1-May-2020
  • (2017)Characteristic Polynomials of p-adic MatricesProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087618(389-396)Online publication date: 23-Jul-2017
  • (2017)Certificates for Triangular Equivalence and Rank ProfilesProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087609(133-140)Online publication date: 23-Jul-2017
  • (2017)Efficient computation of the characteristic polynomial of a threshold graphTheoretical Computer Science10.1016/j.tcs.2016.07.013657:PA(3-10)Online publication date: 2-Jan-2017
  • (2015)Exact Linear Algebra AlgorithmicProceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2755996.2756684(17-18)Online publication date: 24-Jun-2015
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media