On the efficiency of algorithms of analysis (Q3721699)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3951898
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the efficiency of algorithms of analysis |
scientific article; zbMATH DE number 3951898 |
Statements
On the efficiency of algorithms of analysis (English)
0 references
1985
0 references
computational complexity
0 references
von Neumann-Wilkinson condition number
0 references
efficient zero finding
0 references
efficiency of linear programming
0 references
well-posed linear systems
0 references
Newton's method
0 references
0 references
0 references
0 references
0.7740752100944519
0 references
0.7726358771324158
0 references
0.7646017074584961
0 references
This paper is a kind of report on the author's preoccupations concerning the computational complexity. As the author declares, it is partly an exposition of recent results and new open problems, but also some new proofs are given here. There are four principal theorems, named A, B, C and D, twelve problems and many other theorems, lemmas and propositions. We mention the theorem C, which is not proved in the paper: Let \(K_ A\) be the von Neumann-Wilkinson condition number of the matrix A, \(L_ A=\log K_ A\) and L(n) the average (with the Gauss measure) over real \(n\times n\) matrices; then (i) (E. Kostlan) \[ L(n)\leq 1+(5/2)\log n; \] (ii) (A. Ocneanu) Given any \(\epsilon >0\), there is \(n_ 0\) such that for \(n>n_ 0\), \[ (2/3-\epsilon)\log n\leq L(n). \] Some titles are also relevant: On efficient zero finding (theorem A). On the efficiency of linear programming (th. B). On well-posed linear systems (th. C). On efficient approximation of integrals (th. D). Convergence of Newton's method. Purely iterative algorithms. What is an algorithm? Questions of precision.
0 references