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)
- Algorithmic aspects of Suslin's proof of Serre's conjecture
- Short Proofs for the Determinant Identities
- Computing characteristic polynomials of matrices of structured polynomials
- Homomorphic evaluation requires depth
- 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
- Computation of a determinant and a matrix product in cellular automata
- NC algorithms for real algebraic numbers
- Operator scaling: theory and applications
- Automatic symbolic computation for discontinuous Galerkin finite element methods
- Polynomial bounds for invariant functions separating orbits
- ABE for circuits with constant-size secret keys and adaptive security
- On the hardness of the determinant: sum of regular set-multilinear circuits
- Linear matroid intersection is in quasi-NC
- Tensor network complexity of multilinear maps
- Deterministic computation of the characteristic polynomial in the time of matrix multiplication
- Bipartite perfect matching is in quasi-NC
- 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
- ON THE MINIMAL POLYNOMIAL OF A MATRIX
- Factorization of polynomials given by arithmetic branching programs
- A general framework for lattice-based ABE using evasive inner-product functional encryption
- Circuits for computing the GCD of two polynomials over an algebraic number field
- Matrix inversion in RNC\(^ 1\)
- Title not available (Why is that?)
- Calculation of the characteristic polynomial of a matrix
- Notes on hazard-free circuits
- Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
- Title not available (Why is that?)
- Determining the number of Killing tensors by (linear) algebra
- Factoring multivariate polynomials represented by black boxes: a Maple + C implementation
- Probabilistic logarithmic-space algorithms for Laplacian solvers
- Directed evaluation
- Determinant: Old algorithms, new insights
- A complete characterization of unitary quantum space
- Computing bases of complete intersection rings in Noether position
- Computation of étale cohomology on curves in single exponential time
- Title not available (Why is that?)
- Complexity bounds in elimination theory -- a survey.
- Bounded length UCFG equivalence
- Computing characteristic polynomials of matrices of structured polynomials
- Title not available (Why is that?)
- On the complexity of computing the greatest common divisor of several univariate polynomials
- Polyhedral techniques in combinatorial optimization: matchings and tours
- From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
- Homotopy techniques for solving sparse column support determinantal polynomial systems
- 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
- 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
- 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
- Algebraic independence in positive characteristic: a \(p\)-adic calculus
- 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
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)
