On the efficiency of algorithms of analysis

DOI10.1090/S0273-0979-1985-15391-1zbMath0592.65032OpenAlexW2052645364MaRDI QIDQ3721699

Publication date: 1985

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0273-0979-1985-15391-1

zbMATH Keywords

computational complexity Newton's method well-posed linear systems efficiency of linear programming efficient zero finding von Neumann-Wilkinson condition number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) General theory of numerical analysis in abstract spaces (65J05) Numerical computation of solutions to systems of equations (65H10) Linear programming (90C05) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Iterative numerical methods for linear systems (65F10) Algorithms in computer science (68W99)

Related Items

Condition number of a square matrix with i.i.d. columns drawn from a convex body, On the existence of generally convergent algorithms, Smooth analysis of the condition number and the least singular value, Uniform convergence of higher order quasi Hermite-Fejér interpolation, Two-square theorems for infinite matrices on certain fields, Smoothed analysis of $\kappa(A)$, Optimal solution of nonlinear equations, Average errors for zero finding: Lower bounds for smooth or monotone functions, On general convergence in extracting radicals via a fundamental family of iteration functions, Point estimation of simultaneous methods for solving polynomial equations: A survey. II., Algebraic complexity of computing polynomial zeros, Sequential and parallel complexity of approximate evaluation of polynomial zeros, Dynamics of a new family of iterative processes for quadratic polynomials, Iteration of meromorphic functions, A stable family with high order of convergence for solving nonlinear equations, Plane Autonomous Systems with Rational Vector Fields, On the worst-case arithmetic complexity of approximating zeros of polynomials, Complexity of fixed points. I, Simplex method and groups generated by reflections, Optimal quadratures with regard to the efficiency, The Durand-Kerner polynomials roots-finding method in case of multiple roots, Braiding of the attractor and the failure of iterative algorithms, A polynomial-time algorithm, based on Newton's method, for linear programming, Global dynamical properties of Euler and backward Euler, The implementation of linear programming algorithms based on homotopies, A probabilistic theory for error estimation in automatic integration, On the separatrix graph of a rational vector field on the Riemann sphere, Discrete versus continuous Newton's method: A case study, Newton's method and complex dynamical systems, Invertibility of random fredholm operators, Statistical complexity of the power method for Markov chains, On zero finding methods of higher order from data at one point, On the convergence of Newton's method, Superattracting extraneous fixed points and $n$-cycles for Chebyshev's method on cubic polynomials, Linear programming, complexity theory and elementary functional analysis, Dynamics and limiting behavior of Julia sets of König's method for multiple roots, A remark on the smallest singular value of powers of Gaussian matrices, On the basins of attraction of a one-dimensional family of root finding algorithms: from Newton to Traub, Sinks with relatively large immediate basins and a refinement of Mañé’sC¹generic dichotomy, Universality in numerical computations with random data, On optimal fourth-order iterative methods free from second derivative and their dynamics, Dynamical aspects of some convex acceleration methods as purely iterative algorithm for Newton's maps, Dynamics of a higher-order family of iterative methods, Attracting cycles for the relaxed Newton's method, Recent developments in information-based complexity, Blowup points and baby Mandelbrot sets for a family of singularly perturbed rational maps, Solving the quintic by iteration, Randomized Newton-Raphson, Local and global behavior for algorithms of solving equations, Globally convergent, iterative path-following for algebraic equations, Dynamics of a family of Chebyshev-Halley type methods, A critique of numerical analysis, Some Connections of Complex Dynamics, Condition numbers of random matrices, Stability analysis of a parametric family of iterative methods for solving nonlinear models, Corrections to Probabilistic analysis of numerical methods for integral equations, Stability study of eighth-order iterative methods for solving nonlinear equations, Unified complexity analysis for Newton LP methods, Statistical complexity of dominant eigenvector calculation, The smallest singular value of a shifted $d$-regular random square matrix, On the probability distribution of data at points in real complete intersection varieties, THE NEWTON–RAPHSON METHOD AND ADAPTIVE ODE SOLVERS, Invertibility of sparse non-Hermitian matrices, New identities in the Catalan triangle, Families of rational maps and convergence basins of Newton's method, Smale's mean value conjecture for finite Blaschke products, Some computational methods for systems of nonlinear equations and systems of polynomial equations, A New Inequality for Complex-Valued Polynomial Functions, Stochastic perturbations and smooth condition numbers, A new proof of inequality for continuous linear functionals, The Littlewood-Offord problem and invertibility of random matrices, Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding, Upper bounds on the distribution of the condition number of singular matrices, Immediate and virtual basins of Newton's method for entire functions., Approximate Zeros of Quadratically Convergent Algorithms, Random matrices: The distribution of the smallest singular values, Computing spectral measures and spectral types, On the classification of plane graphs representing structurally stable rational Newton flows, Topological complexity of a root finding algorithm, Methods with prefixed order for approximating square roots with global and general convergence, An upper bound on the smallest singular value of a square random matrix, On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial, Sharp transition of the invertibility of the adjacency matrices of sparse random graphs, Rayleigh Quotient Iteration for Nonsymmetric Matrices, Numerical Dynamics of Ordinary Differential Equations with Singularity, An adaptive Newton-method based on a dynamical systems approach, A modern retrospective on probabilistic numerics, Newton vector fields on the plane and on the torus, Convergence of the iteration of Halley's family and Smale operator class in Banach space, The asymptotic distribution of the condition number for random circulant matrices, Chaos in King's iterative family, The theory of Newton's method, Newton's method for analytic systems of equations with constant rank derivatives, Convergence analysis of Davidchack and Lai's algorithm for finding periodic orbits, A global analysis of Newton iterations for determining turning points, Probabilistic analysis of numerical methods for integral equations, Chaotic Numerics From an Integrable Hamiltonian System, Average case optimality, Extraneous fixed points of Euler iteration and corresponding Sullivan's basin, Newton's method in practice: finding all roots of polynomials of degree one million efficiently, How to be sure of finding a root of a complex polynomial using Newton's method, The Weierstrass–Durand–Kerner root finder is not generally convergent, Algorithms for computing basins of attraction associated with a rational self-map of the Hopf fibration based on Lyapunov exponents, On the condition number of a Kreiss matrix, The foundations of spectral computations via the solvability complexity index hierarchy, Computing eigenvalues of the Laplacian on rough domains, Universality for Eigenvalue Algorithms on Sample Covariance Matrices, Quantitative invertibility of non-Hermitian random matrices, Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time, The least singular value of a random symmetric matrix, Flow box decomposition for gradients of univariate polynomials, billiards on the Riemann sphere, tree-like configurations of vanishing cycles for $A_{n}$ curve singularities and geometric cluster monodromy, On the smoothed analysis of the smallest singular value with discrete noise, McMullen’s root-finding algorithm for cubic polynomials, Complex random matrices have no real eigenvalues, Geometry of polynomials and root-finding via path-lifting, On sectional Newtonian graphs, Newton flows for elliptic functions I, Julia sets for the super-Newton method, Cauchy’s method, and Halley’s method, Dynamics of a fifth-order iterative method, A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton’s method, Newton's method and the Computational Complexity of the Fundamental Theorem of Algebra, On the singular values of Gaussian random matrices, Kronecker's and Newton's approaches to solving: a first comparison, Point estimation of simultaneous methods for solving polynomial equations: A survey, Newton flows for elliptic functions: a pilot study†, Newton's method for overdetermined systems of equations, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, The probabilistic estimates on the largest and smallest $q$-singular values of random matrices, Combinatorial properties of Newton maps, Asymptotic regularity, fixed points and successive approximations, Fully Adaptive Newton--Galerkin Methods for Semilinear Elliptic Partial Differential Equations

Cites Work