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