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 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references