The complexity of partial derivatives
From MaRDI portal
Publication:1171380
DOI10.1016/0304-3975(83)90110-XzbMath0498.68028MaRDI QIDQ1171380
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
root functionsdeterminantmatrix inversioncomplexity of single power sumssingle elementary symmetric functions
Analysis of algorithms and problem complexity (68Q25) Numerical computation of determinants (65F40) Direct numerical methods for linear systems and matrix inversion (65F05)
Related Items
Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients, Fast Algorithms for Discrete Differential Equations, Algorithmic differentiation for adjoint sensitivity calculation in plasma edge codes, Monotone arithmetic complexity of graph homomorphism polynomials, Rigid continuation paths II. structured polynomial systems, Arithmetic circuits, structured matrices and (not so) deep learning, A probabilistic algorithm to test local algebraic observability in polynomial time, Algebraic independence in positive characteristic: A $p$-adic calculus, A Gröbner free alternative for polynomial system solving, A new family of high-order directions for unconstrained optimization inspired by Chebyshev and Shamanskii methods, Lower bounds for special cases of syntactic multilinear ABPs, Non-commutative circuits and the sum-of-squares problem, Affine projections of symmetric polynomials., The complexity of evaluating interpolation polynomials, Fast computation of discrete invariants associated to a differential rational mapping, Complexity results for triangular sets, Non-intrusive model reduction of large-scale, nonlinear dynamical systems using deep learning, Matrix inversion algorithms by means of automatic differentiation, Computing Frobenius maps and factoring polynomials, Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits, Some complete and intermediate polynomials in algebraic complexity theory, A fast numerical algorithm for the composition of power series with complex coefficients, A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle, Adjoining Strategies for Multi-layered Programs, Probing a set of hyperplanes by lines and related problems, Faster combinatorial algorithms for determinant and Pfaffian, Complexity of parallel matrix computations, The trace invariant and matrix inversion, Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant, Polar varieties, real equation solving, and data structures: the hypersurface case, Semi-algebraic complexity -- Additive complexity of matrix computational tasks, Sparse polynomial interpolation based on derivatives, Quadratic lower bounds for algebraic branching programs and formulas, Algebraic and numerical techniques for the computation of matrix determinants, Feasible arithmetic computations: Valiant's hypothesis, Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness, Semi-algebraic decision complexity, the real spectrum, and degree, Easy lower bound for a strange computational model, The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms, Lower bounds for the circuit size of partially homogeneous polynomials, Automatic computation of partial derivatives and rounding error estimates with applications to large-scale systems of nonlinear equations, Straight-line programs in geometric elimination theory, The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, On per-iteration complexity of high order Chebyshev methods for sparse functions with banded Hessians, Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization, Fast linear homotopy to find approximate zeros of polynomial systems, Deterministic polynomial identity tests for multilinear bounded-read formulae, Determinant-Preserving Sparsification of SDDM Matrices, On the Power of Homogeneous Depth 4 Arithmetic Circuits, Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits, Lower bounds for the determinantal complexity of explicit low degree polynomials, Robust certified numerical homotopy tracking, The Chebyshev-Shamanskii method for solving systems of nonlinear equations, Computing the sign or the value of the determinant of an integer matrix, a complexity survey., Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set, Faster Combinatorial Algorithms for Determinant and Pfaffian, On a problem posed by Steve Smale, Lower bounds for tropical circuits and dynamic programs, Fast computation of zeros of polynomial systems with bounded degree under finite-precision, Optimal Jacobian accumulation is NP-complete, Deterministic computation of the characteristic polynomial in the time of matrix multiplication, Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth, Some computational problems in linear algebra as hard as matrix multiplication, Change of order for regular chains in positive dimension, Test complexity of generic polynomials, Efficient VLSI fault simulation, Computation of exact gradients in distributed dynamic systems, Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation, Subquadratic-time factoring of polynomials over finite fields, On sign conditions over real multivariate polynomials, Newton's method and FFT trading, Unnamed Item, Unnamed Item, A backward automatic differentiation framework for reservoir simulation, Rigorous Sensitivity Analysis for Systems of Linear and Nonlinear Equations, On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant, Lower bounds for matrix factorization, Black-box learning of multigrid parameters, Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree, An algorithm for implicit interpolation, Smale 17th Problem: Advances and Open Directions, Lower bounds for arithmetic circuits via the Hankel matrix, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, Unnamed Item, Unnamed Item, Unnamed Item, A Selection of Lower Bounds for Arithmetic Circuits, Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials, A quadratic lower bound for algebraic branching programs, A geometric approach to homomorphic secret sharing, A super-quadratic lower bound for depth four arithmetic circuits, Lower bound for the approximative complexity, Deformation techniques for sparse systems, Notes on Hazard-Free Circuits, On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models, Unnamed Item, A minimal code list, A quadratic lower bound for homogeneous algebraic branching programs, Lower bounds for matrix factorization, Leibniz complexity of Nash functions on differentiations, There is no efficient reverse derivation mode for discrete derivatives, Fast algorithms for the characteristic polynomial, Definability and fast quantifier elimination in algebraically closed fields, Bit complexity for computing one point in each connected component of a smooth real algebraic set, The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations, Term Graphs for Computing Derivatives in Imperative Languages, Unifying known lower bounds via geometric complexity theory, Exact linear reduction for rational dynamical systems, Limitations of sums of bounded read formulas and ABPs, Randomized interior point methods for sampling and optimization
Cites Work
