Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)

Question

I know the Blum-Shub-Smale model. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis.

A very general question: Most algorithms compromise of finite input - finite computation steps - finite output

However, in mathematics most schemes which one could call algorithmic actually compromise infinitely many iterations. Just to name a few:

• Iteration to construct fix-points of contractive maps
• Iterative solvers in numerical analysis
• Newtons method

I know the last one is treated in the classical book "Complexity and Real Computation" by Blum, Cucker, Shub & Smale, but there does not seem to exist a generalization which puts "iterative" algorithms onto solid foundations.

Edit: Yes, the question:

How can you deal with these iterative algorithms (which as such are not necessarily supposed to finish)?

Addendum: I always wondered whether there might be something like a BSS-like model, which is tailored for numerical analysis - in that it does formalize errors, inexactness, approximate solutions, and does not allow for "unreasonable" computing power. And is easy to access.

The book mentioned above is concerned about this gap, too: "There is not even a formal definition of algorithm in the subject [of numerical analysis]" (p. 23). However, it does not seem their approach suits this need. On the other hand, the monograph Andrej mentions does include a book which heads towards this direction.

Answer 1

Questions regarding real-number computation and infinite iteration, especially in analysis and topology, are studied in constructive and computable analysis. Most people who work in this area will tell you that while the BSS model can be useful for certain kinds of computational complexity, it does not properly reflect computability on real numbers. The trouble is with the decidable $<$ relation on the reals, which is a basic building block in the BSS model.

There are several computational models which capture both computation of (exact) real numbers and infinite computation. Your examples all reduce to computation of the limit of a convergent sequence whose rate of convergence is explicitly known. This is a well-studied situation.

Here is one possible way of understanding computation on real numbers. I will use Haskell just for fun (usually these things get explained in terms of Turing machines). Let us think of a real number as a convergent sequence of rational approximations,

type R = Int -> Rational

where we require that the $k$-th approximation is at most $2^{-k}$ away from the limit (we could have chosen some other rate of convergence, too, or we could have equipped each approximation sequence with information about the rate of convergence--the important thing is that the rate of convergence has to be provided explicitly).

Addition can be defined as follows:

add x y = \k -> x (k+1) + y (k+1)

Exercise: define multiplication and other arithmetic operations.

Now to get infinite iteration going, we need an operation lim which takes a Cauchy sequence and computes its limit. More precisely, lim takes two arguments: a Cauchy sequence $(a_n)_n$ and its modulus of convergence $m$, which is a map $m : \mathbb{N} \to \mathbb{N}$ such that $a_{m(k)}$ is at most $2^{-k}$ away from the limit of $(a_n)_n$. In Haskell:

lim :: (Int -> R) -> (Int -> Int) -> R

lim a m = \k -> a (m (k+1)) (k+1)

Exercise: compute $\sqrt{r}$ as the limit of the sequence obtained by Newton's method for finding the positive root of $x^2 - r$.

This is just a very brief outline on how to do things. To find out more, visit the CCA net web site, especially the Texts and Monographs page.

Answer 2

There are two examples of a complexity-theoretic study of iterative methods. The class PLS and the recent work by Papadimitriou and Daskalakis on CLS: continuous local search. These might be useful (especially the latter as it deals with continuous domains)