On the complexity of computing determinants

DOI10.1007/s00037-004-0185-3zbMath1061.68185WikidataQ56459440 ScholiaQ56459440MaRDI QIDQ1766817

Erich L. Kaltofen, Gilles Villard

Publication date: 1 March 2005

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: http://www.lib.ncsu.edu/resolver/1840.2/87

zbMATH Keywords

characteristic polynomial; randomized algorithm; block Lanczos algorithm; realization; Smith normal form; bit complexity; division-free complexity; matrix determinant; matrix sequence; Integer matrix; block Wiedemann algorithm; multivariable control theory

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

15A15: Determinants, permanents, traces, other special matrix functions

65F40: Numerical computation of determinants

65Y20: Complexity and performance of numerical algorithms

68W20: Randomized algorithms

15B36: Matrices of integers

Related Items

Zariski chambers on surfaces of high Picard number, An 𝐿(1/3) algorithm for ideal class group and regulator computation in certain number fields, Asymptotically fast polynomial matrix algorithms for multivariable systems, A fast algorithm to construct a representation for transversal matroids, Faster geometric algorithms via dynamic determinant computation, Projective interpolation of polynomial vectors and improved key recovery attack on SFLASH, Interpolation in Valiant's theory, Relaxed Hensel lifting of triangular sets, Efficient computation of the characteristic polynomial of a threshold graph, Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation, Critical groups of graphs with dihedral actions. II., On the complexity of inverting integer and polynomial matrices, An effective algorithm of computing symbolic determinants with multivariate polynomial entries, On the extension of Sarrus' rule to \(n \times n\) (\(n > 3\)) matrices: development of new method for the computation of the determinant of \(4 \times 4\) matrix, Sparse resultants and straight-line programs, Essentially optimal computation of the inverse of generic polynomial matrices, Probabilistic analysis of block Wiedemann for leading invariant factors, Graph characterization by counting sink star subgraphs, The shifted number system for fast linear algebra on integer matrices, Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix, A fraction free matrix Berlekamp/Massey algorithm, AN ORACLE-BASED, OUTPUT-SENSITIVE ALGORITHM FOR PROJECTIONS OF RESULTANT POLYTOPES, Efficient Disjointness Tests for Private Datasets, Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time, FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME