On computing the determinant in small parallel time using a small number of processors
From MaRDI portal
Publication:794429
DOI10.1016/0020-0190(84)90018-8zbMath0541.68019WikidataQ60164650 ScholiaQ60164650MaRDI QIDQ794429
Publication date: 1984
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(84)90018-8
upper bounds; characteristic polynomial; determinant; adjoint; Turing machine; matrix; commutative ring; parallel algebraic circuit complexity
68Q25: Analysis of algorithms and problem complexity
Related Items
Unnamed Item, Unnamed Item, Automatic Symbolic Computation for Discontinuous Galerkin Finite Element Methods, Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic, Minors of Bezout matrices, subresultants and the parameterization of the degree of the polynomial greatest common divisor, Sur la complexité du principe de Tarski-Seidenberg, Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem, Unnamed Item, Relationships among $PL$, $\#L$, and the determinant, Unnamed Item, Unnamed Item, Notes on Hazard-Free Circuits, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, Bipartite Perfect Matching is in Quasi-NC, Determinant: Old algorithms, new insights, On the complexity of computing the greatest common divisor of several univariate polynomials, A Complete Characterization of Unitary Quantum Space, Faster geometric algorithms via dynamic determinant computation, Cancellation is exponentially powerful for computing the determinant, A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set, Relaxed Hensel lifting of triangular sets, Elementary recursive quantifier elimination based on Thom encoding and sign determination, Deformation techniques to solve generalised Pham systems, On a generalization of Stickelberger's theorem, Lower bounds for the determinantal complexity of explicit low degree polynomials, Lower bounds for monotone span programs, Decomposition of algebras over finite fields and number fields, Evaluation properties of invariant polynomials, Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields, Simple algorithms for approximating all roots of a polynomial with real roots, The Faddeev-LeVerrier algorithm and the Pfaffian, Parallelism and fast solution of linear systems, Parallel complexity of the regular code problem, Parallel models of computation: An introductory survey, Problems complete for \(\oplus L\), On sign conditions over real multivariate polynomials, A parametric representation of totally mixed Nash equilibria, On the complexity of counting components of algebraic varieties, Algebraic complexity of computing polynomial zeros, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Rapid parallel computation of degrees in a quotient ring of polynomials over a finite field, Feasible arithmetic computations: Valiant's hypothesis, Parallel evaluation of the determinant and of the inverse of a matrix, Rubber bands, convex embeddings and graph connectivity, Circuits for computing the GCD of two polynomials over an algebraic number field, The complexity of computing the number of strings of given length in context-free languages, Matrix inversion in RNC\(^ 1\), Equations for the projective closure and effective Nullstellensatz, The membership problem for unmixed polynomial ideals is solvable in single exponential time, Parallel algebraic reductions among numerical problems, NC algorithms for real algebraic numbers, Parametrization of Newton's iteration for computations with structured matrices and applications, Improved processor bounds for combinatorial problems in RNC, On the parallel complexity of the polynomial ideal membership problem, An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs, Specified precision polynomial root isolation is in NC, Computing algorithms for the reduction of a Hermite algorithm with polynomial coefficients, Lower bounds for diophantine approximations, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Straight-line programs in geometric elimination theory, The complexity of the characteristic and the minimal polynomial., Computing the characteristic polynomial of multivariate polynomial matrices given by straight-line programs, Complexity bounds in elimination theory -- a survey., The Projective Noether Maple Package: Computing the dimension of a projective variety, On the complexity of the Lickteig-Roy subresultant algorithm, Polynomial bounds for invariant functions separating orbits, Weak theories of linear algebra, Fast and efficient parallel solution of dense linear systems, The proof complexity of linear algebra, Randomization and the parallel solution of linear algebra problems, Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties, Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing, On arithmetic branching programs, Deformation techniques for efficient polynomial equation solving., Homotopy techniques for solving sparse column support determinantal polynomial systems, Linear matroid intersection is in quasi-NC, Factorization of polynomials given by arithmetic branching programs, On the hardness of the determinant: sum of regular set-multilinear circuits, On Hosoya's dormants and sprouts, Directed evaluation, Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits, Computation of étale cohomology on curves in single exponential time, Deterministic computation of the characteristic polynomial in the time of matrix multiplication, Elimination for generic sparse polynomial systems, On the structure of loop-free non-negative edge-bipartite graphs, Operator scaling: theory and applications, Generalized Wong sequences and their applications to Edmonds' problems, Algorithmic aspects of Suslin's proof of Serre's conjecture, On the efficiency of effective Nullstellensätze, Change of order for regular chains in positive dimension, Characterizing Valiant's algebraic complexity classes, On the complexity exponent of polynomial system solving, Factoring multivariate polynomials represented by black boxes: a Maple + C implementation, Homomorphic Evaluation Requires Depth, Arithmetic Circuits: A Chasm at Depth 3, Computing Characteristic Polynomials of Matrices of Structured Polynomials, Bounded Treewidth and Space-Efficient Linear Algebra, Calculation of the characteristic polynomial of a matrix, Lower Bounds for Syntactically Multilinear Algebraic Branching Programs, Structure and importance of logspace-MOD class, Unnamed Item, COMPUTATION OF A DETERMINANT AND A MATRIX PRODUCT IN CELLULAR AUTOMATA, Short Proofs for the Determinant Identities, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits, Computing characteristic polynomials of matrices of structured polynomials, Algebraic independence in positive characteristic: A $p$-adic calculus, ON THE MINIMAL POLYNOMIAL OF A MATRIX, A Gröbner free alternative for polynomial system solving, Computing bases of complete intersection rings in Noether position, Division-free computation of subresultants using Bezout matrices, Connections between graphs and matrix spaces, ABE for circuits with constant-size secret keys and adaptive security
Cites Work
