scientific article; zbMATH DE number 1069617
The aim of the paper is a thorough discussion on the complexity theory of numerical analysis. According to computer science, an algorithm defined by a Turing machine is in polynomial time if the computing time \(T(y)\) on the input \(y\) satisfies: \[ T(y)\leq K(\text{size}(y))^c,\tag{1} \] where \(\text{size}(y)\) is the number of bits for representing \(y\). A problem is said to be P (or tractable) if there is a polynomial time algorithm (i.e. Turing machine) to solve it. Since in numerical analysis most algorithms are solving problems only approximately, with accuracy \(\varepsilon>0\), or precision \(\log\varepsilon^{-1}\), the paper redefines the ``polynomial complexity as: \[ T(y,\varepsilon)\leq K(\mu(y)+ \text{size}(y)- \log\varepsilon)^c,\tag{2} \] where \(y=(y_1,\dots, y_n)\), \(\text{size}(y)= n\), \(y_i\in\mathbb{R}\) representing the input of the numerical problem, and \(\mu(y)\) being the condition number of the particular problem. An estimate of the probability distribution of \(\mu\) takes the form: \[ \text{prob}\{y: \mu(y)\geq K\}\leq\Biggl({1\over K}\Biggr)^c,\tag{3} \] where a probability measure has been put on the space of inputs. Now the complexity theory of numerical analysis is represented by a two-parts scheme: Part 1 is the estimate (2), and Part 2 is the estimate (3) of the condition number. The existence of the corresponding fundamental problem \(\text{P}=\text{NP}\) over the set of real numbers \(\mathbb{R}\) is also investigated. For the entire collection see [Zbl 0868.00024].
- Computational cost of the Fekete problem. I: The forces method on the 2-sphere
- Kantorovich-type convergence criterion for inexact Newton methods
- Complexity analysis and its application
- Uniform convergence of higher order quasi Hermite-Fejér interpolation
- Local and global behavior for algorithms of solving equations
- Condition number bounds for problems with integer coefficients
- Real computations with fake numbers
- Convergence of the reach for a sequence of Gaussian-embedded manifolds
- Estimating the local radius of convergence for Picard iteration
- Local convergence of generalized Mann iteration
- Primal and dual model representations in kernel-based learning
- Computing spectral measures and spectral types
- On semilocal convergence analysis for two-step Newton method under generalized Lipschitz conditions in Banach spaces
- On the complexity of the Plantinga-Vegter algorithm
- A note on the finite variance of the averaging function for polynomial system solving
- Computing the homology of semialgebraic sets. I: Lax formulas
- Convergence behavior for Newton-Steffensen's method under \(\gamma\)-condition of second derivative
- Probabilistic analysis of the Grassmann condition number
- Two-square theorems for infinite matrices on certain fields
- On the condition of the zeros of characteristic polynomials
- Uniqueness of the singular points of vector fields on Riemannian manifolds under the -condition
- Newton-Kantorovich method and its global convergence
- Convergence of Gauss-Newton's method and uniqueness of the solution
- Condition numbers for the cube. I: Univariate polynomials and hypersurfaces
- Local convergence radius for the Mann-type iteration
- The Legacy of Turing in Numerical Analysis
- Extended Newton methods for conic inequalities: approximate solutions and the extended Smale -theory
- On the solvability complexity index, the n-pseudospectrum and approximations of spectra of operators
- The probability that a slightly perturbed numerical analysis problem is difficult
- On the Complexity of Numerical Analysis
- On the efficiency of algorithms of analysis
- scientific article; zbMATH DE number 4077311 (Why is no real title available?)
- Geometry of polynomials and root-finding via path-lifting
- On numerical stability in large scale linear algebraic computations
- On the cost of iterative computations
- Ultimate complexity for numerical algorithms
- Local convergence of the Newton’s method in two step nilpotent Lie groups
- A theory of complexity, condition, and roundoff
- Extended Newton methods for multiobjective optimization: majorizing function technique and convergence analysis
- On the solution of systems of equations with constant rank derivatives
- Topics in real and complex number complexity theory
- scientific article; zbMATH DE number 2212170 (Why is no real title available?)
- Local convergence of Newton's method on the Heisenberg group
- Complete decomposition of symmetric tensors in linear time and polylogarithmic precision
- The foundations of spectral computations via the solvability complexity index hierarchy
- 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
- Extending the applicability of the Gauss-Newton method under average Lipschitz-type conditions
- Globally convergent, iterative path-following for algebraic equations
- On the computation of geometric features of spectra of linear operators on Hilbert spaces
- On a problem posed by Steve Smale
- Robust smoothed analysis of a condition number for linear programming
- On the computation of the homology of semialgebraic sets
- Instability in deep learning -- when algorithms cannot compute uncertainty quantifications for neural networks
- Global convergence of Hessenberg shifted QR. I: Exact arithmetic
- Relations between roots and coefficients, interpolation and application to system solving
- Complete decomposition of symmetric tensors in linear time and polylogarithmic precision
- -theory of Hald's method
- A practical extension of computational complexity theory for applications in mathematics and sciences
- Universal methods for nonlinear spectral problems
- A method for computing the number of iterations in data dependent loops
- Newton's method and its use in optimization
- Newton's method for sections on Riemannian manifolds: Generalized covariant \(\alpha \)-theory
- Kantorovich's type theorems for systems of equations with constant rank derivatives
- 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
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4356579)
