6
$\begingroup$

Hello,

in contrast to the more discrete part of computational mathematics (cryptography, combinatorial computation), numerical mathematics seems to ignore typical questions of theoretical computer science -- what does 'algorithm' or 'computation' mean, what is the model of computation.

This is far from fallacious. For example, a finite element theorist mostly investigates only approximation schemes and convergence rates, which in principle do not demand any computation at all. Algorithms are typically neat and short, and any exceptions to these are not rarely just combinatorial insertions for mesh management. The other end of the spectrum compromises very technical numerical mathematics. - In either case, the 'deep-down' part is largely abandoned as soon as possible, because it is largely irrelevant. Just like no cryptographer enjoys talking about Turing machines.

Has there been a rigourous treatment of a numerical model, a justification why (or for whom) a certain model might be appropiate?

I am aware of computable analysis and numerical mathematicians who participate in this field. But I am not aware of a numerical model like, say, a numerical random access machine. I even suppose there different models appropiate for researchers in fundamental numerical algoriths or a FEM reasearcher, depending on which level of detail is needed.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

The principal motivation for the Blum Shub Smale model of computability was precisely the kind of concern you raise in your question. In particular, the BSS machines provide a numerical model of computation using a random access machine concept, where the registers hold full-precision real numbers. The dynamicists had wanted a theoretical model of computability that would untangle the discrete computational effects, such as round-off error, from the computational analysis of numerical algorithms involving continuous quantities. They wanted to provide a formal setting in which to analyze issues such as stability and convergence of algorithms in a more continuous setting, where quantities would be represented with perfect precision, and the typical discrete computational issues would loom less large. The BSS model is provably different from the model of computable analysis.

Improve this answer
$\endgroup$
12
  • $\begingroup$ The BSS model, as described in the Wikipedia article, provides a test 'exactly equal zero'. Maybe I am wrong, but in general you would not use such an operation in a numerical algorithm. It seems appropiate to equip the machine instead with something like 'test bigger than zero' or maybe even 'test bigger than $\epsilon$' with $\epsilon$ > 0. $\endgroup$
    – shuhalo
    Commented Mar 10, 2011 at 8:51
  • $\begingroup$ Having "test bigger than zero" allows one to compute "test equal zero", since you can just test the number and its negation and get the same information. Similarly, having a test for $\epsilon\lt y$ when $\epsilon$ is a fixed computable number will provide a test for equality with $0$; and if $\epsilon$ is not computable, then this test will be something like an oracle, a source of noncomputability in the device. But you are right to point to this crisp testing as a difference between BSS models and, say, computable analysis. $\endgroup$
    – Joel David Hamkins
    Commented Mar 10, 2011 at 13:55
  • $\begingroup$ I think that what Martin had in mind was a test distinguishing the case $x>\epsilon$ from the case $x\le0$. This can be done effectively. $\endgroup$
    – Emil Jeřábek
    Commented Mar 10, 2011 at 14:40
  • $\begingroup$ My point was that $x=0$ is equivalent to ( not $x+\epsilon\gt\epsilon$ and not $-x+\epsilon\gt\epsilon$), which would be computable, if $\epsilon$ is computable. And if $\epsilon$ is not computable, then you can get non-computable information out of the test. $\endgroup$
    – Joel David Hamkins
    Commented Mar 10, 2011 at 14:55
  • $\begingroup$ I know. My point is that this reduction ceases to work if the test is not required to give any sensible outcome for $x\in(0,\epsilon)$. $\endgroup$
    – Emil Jeřábek
    Commented Mar 10, 2011 at 15:00
4
$\begingroup$

There are mainly three approaches to deal with computational complexity of continuous problems.
1. Information Based Complexity (analytical complexity). It is a very general framework that describes the complexity of a problem in terms of the number of 'operations' (specified by the problem itself) needed to solve it on condition that we are given only rough information about the initial problem. This theory is mostly about the 'real' complexity --- which is independent of any particular model of computation --- it gives lower bounds on all possible models. See 'Information-Based Complexity' by Traub, Wasilowski and Woźniakowski for more details.
2. Blum–Shub–Smale machine and that like (algebraic complexity). The idea comes from the good old days when people believed that it was possible to build analog computers that are more powerful than turing machines. I was to say that the idea of stroing infinite information in a single cell, and comparing two such cells in a finite time is a bit crazy from both practical and theoretical point of view, but I guess it is prudent to refrain from making such comments. These models are inconsistent with physical laws, so it should not be strange that they allow some 'dirty hacks' (for example there are uncomputable problems easily solvable on Blum–Shub–Smale machine; under some definitions, one may show that both $P/Poly$ and $NP$ are solvable in polynomial time).
3. Turing machines (discrete complexity). If you really want to solve a problem on a computer, then you really have to transform it into a discrete one (either symbolic or numeric). But then, there is nothing left but the classic complexity :-)

David, I do agree with your reasoning, and (so) with your conclusion. However, notice that it is always easy to falsify statements such as my remarks. Simply, the reality is so complex, that in every such proclamation there must be much more things that we have to ignore, than we are able to take into consideration. The crucial point here is that BSS allows us to perform dirty tricks and reach something paradoxical, which otherwise we would have not accepted; and that the extra power does not give us anything besides these paradoxes. Every algorithm for BSS either: has its counterpart in the standard model, or is ‘unrealizable’ (we may have an infinite precision, and infinite memory, but when we cut these infinities at any stage, we get a Turing machine). Put it differently, according to our current knowledge every ‘sensible’ ‘realization’ of a BSS has to factor through a Turing machine.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Concerning your remarks in item (2), since all the models of computability are meant to provide idealized theoretical models, it seems misplaced to judge them on the grounds of physical realizability. After all, would you make the analogous criticism of Turing machines, arguing that for very long computations, the paper tape would become so massive so as to have gravitational effects? It would certainly tear or collapse into a black hole. Such criticisms do not seem to touch the fundamental theoretical value of the models. $\endgroup$
    – Joel David Hamkins
    Commented Mar 10, 2011 at 13:14
1
$\begingroup$

Caveat emptor: answer written by a non-expert.

I think Algebraic Complexity Theory in general provides a useful model for dealing with computations involving real numbers (or other fields). The BSS model seems to be one successful model in algebraic complexity.

A question of my own is: isn't interval arithmetic suitable for the kind of analysis that one might wish to perform for numerical algorithms?

Another question is: What about Non-standard analysis?

Improve this answer
$\endgroup$
1
  • $\begingroup$ I didn't know interval arithmetic. But it (or maybe fuzzy arithmetic) seems quite close to what you have in mind when you design a numerical algorithm. $\endgroup$
    – shuhalo
    Commented Mar 10, 2011 at 17:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .