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
Recommendations
Cites work
Cited in
(only showing first 100 items - show all)- Simple algorithms for approximating all roots of a polynomial with real roots
- A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
- On the structure of loop-free non-negative edge-bipartite graphs
- The complexity of computing the number of strings of given length in context-free languages
- Equations for the projective closure and effective Nullstellensatz
- Deformation techniques to solve generalised Pham systems
- Elimination for generic sparse polynomial systems
- Parallel models of computation: An introductory survey
- Fast and efficient parallel solution of dense linear systems
- On the complexity of the Lickteig-Roy subresultant algorithm
- Decomposition of algebras over finite fields and number fields
- Parallelism and fast solution of linear systems
- Sur la complexité du principe de Tarski-Seidenberg
- Generalized Wong sequences and their applications to Edmonds' problems
- Change of order for regular chains in positive dimension
- Arithmetic circuits: a chasm at depth 3
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Problems complete for \(\oplus L\)
- Cancellation is exponentially powerful for computing the determinant
- Minors of Bezout matrices, subresultants and the parameterization of the degree of the polynomial greatest common divisor
- Randomization and the parallel solution of linear algebra problems
- Faster geometric algorithms via dynamic determinant computation
- A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic
- Fast parallel algorithms for vandermonde determinants
- Parallel evaluation of the determinant and of the inverse of a matrix
- Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
- The proof complexity of linear algebra
- The Faddeev-LeVerrier algorithm and the Pfaffian
- Parallel complexity of the regular code problem
- The complexity of the characteristic and the minimal polynomial.
- Division-free computation of subresultants using Bezout matrices
- The membership problem for unmixed polynomial ideals is solvable in single exponential time
- Deterministic polynomial identity testing in non-commutative models
- Bounded treewidth and space-efficient linear algebra
- Algebraic independence in positive characteristic: a \(p\)-adic calculus
- Improved processor bounds for combinatorial problems in RNC
- Rapid parallel computation of degrees in a quotient ring of polynomials over a finite field
- scientific article; zbMATH DE number 3999284 (Why is no real title available?)
- Computing algorithms for the reduction of a Hermite algorithm with polynomial coefficients
- On the complexity of counting components of algebraic varieties
- Parallel computation of polynomial GCD and some related parallel computations over abstract fields
- Weak theories of linear algebra
- On arithmetic branching programs
- Straight-line programs in geometric elimination theory
- On a generalization of Stickelberger's theorem
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- Lower bounds for monotone span programs
- Relationships among $PL$, $\#L$, and the determinant
- An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs
- Algebraic complexity of computing polynomial zeros
- Structure and importance of logspace-MOD class
- Computing the characteristic polynomial of multivariate polynomial matrices given by straight-line programs
- Feasible arithmetic computations: Valiant's hypothesis
- Evaluation properties of invariant polynomials
- On sign conditions over real multivariate polynomials
- Rubber bands, convex embeddings and graph connectivity
- Complexity of parallel matrix computations
- On the complexity of computing determinants
- Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties
- Deformation techniques for efficient polynomial equation solving.
- Parametrization of Newton's iteration for computations with structured matrices and applications
- A Gröbner free alternative for polynomial system solving
- Elementary recursive quantifier elimination based on Thom encoding and sign determination
- On the efficiency of effective Nullstellensätze
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Lower bounds for diophantine approximations
- On the complexity exponent of polynomial system solving
- Lower bounds for the determinantal complexity of explicit low degree polynomials
- Characterizing Valiant's algebraic complexity classes
- The Projective Noether Maple Package: Computing the dimension of a projective variety
- A parametric representation of totally mixed Nash equilibria
- Specified precision polynomial root isolation is in NC
- Relaxed Hensel lifting of triangular sets
- Parallel algebraic reductions among numerical problems
- Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
- Notes on hazard-free circuits
- scientific article; zbMATH DE number 7250159 (Why is no real title available?)
- Determinants vs. algebraic branching programs
- NC algorithms for real algebraic numbers
- Automatic symbolic computation for discontinuous Galerkin finite element methods
- On the hardness of the determinant: sum of regular set-multilinear circuits
- Short Proofs for the Determinant Identities
- Bipartite perfect matching is in quasi-NC
- scientific article; zbMATH DE number 7561373 (Why is no real title available?)
- A complete characterization of unitary quantum space
- On the parallel complexity of the polynomial ideal membership problem
- Computing characteristic polynomials of matrices of structured polynomials
- 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
- Computing bases of complete intersection rings in Noether position
- Linear matroid intersection is in quasi-NC
- Bounded length UCFG equivalence
- Homotopy techniques for solving sparse column support determinantal polynomial systems
- Computation of étale cohomology on curves in single exponential time
- Operator scaling: theory and applications
- Complexity bounds in elimination theory -- a survey.
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Probabilistic logarithmic-space algorithms for Laplacian solvers
- Tensor network complexity of multilinear maps
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)
