On the complexity of computing determinants

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

Gilles Villard, Erich L. Kaltofen

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

Solving p-adic polynomial systems via iterative eigenvector algorithms, 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, Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology, High-order lifting for polynomial Sylvester matrices, 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, Multilinear polynomial systems: root isolation and bit complexity, Probabilistic analysis of block Wiedemann for leading invariant factors, A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix, Efficient sampling in spectrahedra and volume approximation, Deterministic computation of the characteristic polynomial in the time of matrix multiplication, Block-Krylov techniques in the context of sparse-FGLM algorithms, More extensions of a determinant inequality of Hartfiel, 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