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-8zbMATH Open0541.68019DBLPjournals/ipl/Berkowitz84OpenAlexW2082002555WikidataQ60164650 ScholiaQ60164650MaRDI QIDQ794429FDOQ794429
Authors: Stuart J. Berkowitz 
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
Recommendations
matrixdeterminantcharacteristic polynomialTuring machineadjointupper boundscommutative ringparallel algebraic circuit complexity
Cites Work
Cited In (only showing first 100 items - show all)
- The Faddeev-LeVerrier algorithm and the Pfaffian
- Parallel computation of polynomial GCD and some related parallel computations over abstract fields
- A parametric representation of totally mixed Nash equilibria
- Parametrization of Newton's iteration for computations with structured matrices and applications
- Change of order for regular chains in positive dimension
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Bounded Treewidth and Space-Efficient Linear Algebra
- Feasible arithmetic computations: Valiant's hypothesis
- Fast parallel algorithms for vandermonde determinants
- Rapid parallel computation of degrees in a quotient ring of polynomials over a finite field
- Structure and importance of logspace-MOD class
- Specified precision polynomial root isolation is in NC
- Division-free computation of subresultants using Bezout matrices
- Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties
- Faster geometric algorithms via dynamic determinant computation
- A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic
- Title not available (Why is that?)
- A Gröbner free alternative for polynomial system solving
- Lower bounds for diophantine approximations
- Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
- On the complexity of the Lickteig-Roy subresultant algorithm
- Sur la complexité du principe de Tarski-Seidenberg
- Cancellation is exponentially powerful for computing the determinant
- Computing the characteristic polynomial of multivariate polynomial matrices given by straight-line programs
- Algebraic independence in positive characteristic: A $p$-adic calculus
- On the complexity exponent of polynomial system solving
- Minors of Bezout matrices, subresultants and the parameterization of the degree of the polynomial greatest common divisor
- Straight-line programs in geometric elimination theory
- Lower bounds for monotone span programs
- Evaluation properties of invariant polynomials
- On the complexity of computing determinants
- The membership problem for unmixed polynomial ideals is solvable in single exponential time
- Fast and efficient parallel solution of dense linear systems
- Randomization and the parallel solution of linear algebra problems
- Computing algorithms for the reduction of a Hermite algorithm with polynomial coefficients
- On a generalization of Stickelberger's theorem
- Deformation techniques for efficient polynomial equation solving.
- Decomposition of algebras over finite fields and number fields
- A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
- On the efficiency of effective Nullstellensätze
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Improved processor bounds for combinatorial problems in RNC
- On the complexity of counting components of algebraic varieties
- Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
- On the structure of loop-free non-negative edge-bipartite graphs
- Relationships among $PL$, $\#L$, and the determinant
- On sign conditions over real multivariate polynomials
- Relaxed Hensel lifting of triangular sets
- An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs
- Lower bounds for the determinantal complexity of explicit low degree polynomials
- Elimination for generic sparse polynomial systems
- Generalized Wong sequences and their applications to Edmonds' problems
- Parallel complexity of the regular code problem
- Deterministic polynomial identity testing in non-commutative models
- Weak theories of linear algebra
- On arithmetic branching programs
- Characterizing Valiant's algebraic complexity classes
- The proof complexity of linear algebra
- Algebraic complexity of computing polynomial zeros
- Parallel models of computation: An introductory survey
- Problems complete for \(\oplus L\)
- The complexity of the characteristic and the minimal polynomial.
- Parallel algebraic reductions among numerical problems
- Deformation techniques to solve generalised Pham systems
- The Projective Noether Maple Package: Computing the dimension of a projective variety
- Parallel evaluation of the determinant and of the inverse of a matrix
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- The complexity of computing the number of strings of given length in context-free languages
- Arithmetic circuits: a chasm at depth 3
- Complexity of parallel matrix computations
- Equations for the projective closure and effective Nullstellensatz
- Parallelism and fast solution of linear systems
- Rubber bands, convex embeddings and graph connectivity
- Elementary recursive quantifier elimination based on Thom encoding and sign determination
- Simple algorithms for approximating all roots of a polynomial with real roots
- Title not available (Why is that?)
- Algorithmic aspects of Suslin's proof of Serre's conjecture
- Short Proofs for the Determinant Identities
- Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
- On the parallel complexity of the polynomial ideal membership problem
- Connections between graphs and matrix spaces
- Notes on Hazard-Free Circuits
- NC algorithms for real algebraic numbers
- Operator scaling: theory and applications
- Title not available (Why is that?)
- Polynomial bounds for invariant functions separating orbits
- Bipartite Perfect Matching is in Quasi-NC
- A Complete Characterization of Unitary Quantum Space
- Title not available (Why is that?)
- ABE for circuits with constant-size secret keys and adaptive security
- On the hardness of the determinant: sum of regular set-multilinear circuits
- Homomorphic Evaluation Requires Depth
- Linear matroid intersection is in quasi-NC
- Deterministic computation of the characteristic polynomial in the time of matrix multiplication
- On Hosoya's dormants and sprouts
- Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic
- Determinants vs. algebraic branching programs
- From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces
- ON THE MINIMAL POLYNOMIAL OF A MATRIX
- Factorization of polynomials given by arithmetic branching programs
This page was built for publication: On computing the determinant in small parallel time using a small number of processors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794429)
