scientific article; zbMATH DE number 1069617

Publication date: 23 March 1998

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

algorithms computational complexity condition number polynomial time polynomial time complexity NP problem complexity theory of numerical analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity and performance of numerical algorithms (65Y20)

Related Items

Uniform convergence of higher order quasi Hermite-Fejér interpolation ⋮ The Legacy of Turing in Numerical Analysis ⋮ Two-square theorems for infinite matrices on certain fields ⋮ Extended Newton methods for conic inequalities: approximate solutions and the extended Smale \(\alpha\)-theory ⋮ On semilocal convergence analysis for two-step Newton method under generalized Lipschitz conditions in Banach spaces ⋮ A method for computing the number of iterations in data dependent loops ⋮ Convergence of the reach for a sequence of Gaussian-embedded manifolds ⋮ Estimating the local radius of convergence for Picard iteration ⋮ On the condition of the zeros of characteristic polynomials ⋮ On the complexity of the Plantinga-Vegter algorithm ⋮ Newton's method and its use in optimization ⋮ Local convergence of the Newton’s method in two step nilpotent Lie groups ⋮ Condition numbers for the cube. I: Univariate polynomials and hypersurfaces ⋮ Complete decomposition of symmetric tensors in linear time and polylogarithmic precision ⋮ The foundations of spectral computations via the solvability complexity index hierarchy ⋮ Local convergence radius for the Mann-type iteration ⋮ Local convergence of generalized Mann iteration ⋮ Rigid continuation paths II. structured polynomial systems ⋮ Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time ⋮ Unrealistic models for realistic computations: how idealisations help represent mathematical structures and found scientific computing ⋮ Geometry of polynomials and root-finding via path-lifting ⋮ Primal and dual model representations in kernel-based learning ⋮ Extending the applicability of the Gauss-Newton method under average Lipschitz-type conditions ⋮ Local and global behavior for algorithms of solving equations ⋮ Globally convergent, iterative path-following for algebraic equations ⋮ Newton's method for sections on Riemannian manifolds: Generalized covariant \(\alpha \)-theory ⋮ On a problem posed by Steve Smale ⋮ Robust smoothed analysis of a condition number for linear programming ⋮ Kantorovich's type theorems for systems of equations with constant rank derivatives ⋮ The probability that a slightly perturbed numerical analysis problem is difficult ⋮ Relations between roots and coefficients, interpolation and application to system solving ⋮ On the solution of systems of equations with constant rank derivatives ⋮ A note on the finite variance of the averaging function for polynomial system solving ⋮ Smale's \(\alpha \)-theory for inexact Newton methods under the \(\gamma \)-condition ⋮ Adversarial smoothed analysis ⋮ Convergence behavior of Gauss-Newton's method and extensions of the Smale point estimate theory ⋮ On numerical stability in large scale linear algebraic computations ⋮ Computing spectral measures and spectral types ⋮ Uniqueness of the singular points of vector fields on Riemannian manifolds under the \(\gamma\)-condition ⋮ Local convergence of Newton's method on the Heisenberg group ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ On the Solvability Complexity Index, the 𝑛-pseudospectrum and approximations of spectra of operators ⋮ Computational cost of the Fekete problem. I: The forces method on the 2-sphere ⋮ Kantorovich-type convergence criterion for inexact Newton methods ⋮ Extended Newton Methods for Multiobjective Optimization: Majorizing Function Technique and Convergence Analysis ⋮ Convergence behavior for Newton-Steffensen's method under \(\gamma\)-condition of second derivative ⋮ On the cost of iterative computations ⋮ Newton-Kantorovich method and its global convergence ⋮ Convergence of Gauss-Newton's method and uniqueness of the solution ⋮ Probabilistic analysis of the Grassmann condition number ⋮ Condition number bounds for problems with integer coefficients ⋮ Real computations with fake numbers