11
$\begingroup$

There are algorithmic graph theory/number theory/combinatorics/information theory/game theory.

Is there algorithmic mathematical analysis?

According to wiki, mathematical analysis includes the theories of differentiation, integration, measure, limits, infinite series, and analytic functions. It is OK to focus on real analysis (wiki) that deals with the real numbers and real-valued functions of a real variable.

"Algorithmic" means studying something from the perspectives of computability theory and complexity theory.


Googling of "algorithmic mathematical analysis" leads me to "mathematical analysis of algorithms" or "applications of analysis to algorithms", which is not what I mean.

$\endgroup$
  • 10
    $\begingroup$ I think you are looking for "computable analysis", which is by now a quite well-established area. You can check, for example, an introductory book by Weihrauch. The theory deals mainly with computability questions, I am not sure how much is known as far as computational complexity. My impression is that even nailing a good definition of complexity is tricky. $\endgroup$ – Sasho Nikolov May 30 '15 at 4:38
  • $\begingroup$ @SashoNikolov Yes. "Computable analysis" seems very relevant. Thanks. Convert your comment to an answer? $\endgroup$ – hengxin May 30 '15 at 4:52
  • 3
    $\begingroup$ See also Chaudhuri, Sankaranarayanan and Vardi's paper on Regular Real analysis which studies a fragment of real analysis you can carry out with finite automata on infinite words. $\endgroup$ – Vijay D May 30 '15 at 6:43
  • $\begingroup$ As another resource, see Yap's paper "Theory of Real Computation according to EGC": cs.nyu.edu/exact/doc/realtheory.pdf $\endgroup$ – Huck Bennett Jun 3 '15 at 4:42
18
$\begingroup$

Check out the Computability and Complexity in Analysis network. Quote:

The topics of interest include foundational work on various models and approaches for describing computability and complexity over the real numbers. They also include complexity-theoretic investigations, both foundational and with respect to concrete problems, and new implementations of exact real arithmetic, as well as further developments of already existing software packages.

$\endgroup$
12
$\begingroup$

(Disclaimer: I am not an expert, feel free to suggest corrections, or write a more comprehensive answer if you are.)

Extending computability and complexity to the real numbers (which is a first step in doing analysis) is tricky and has been done in several inequivalent ways. One is the Blum-Shub-Smale (BSS) model, which augments Turing machines with the ability to store and perform algebraic operations with real numbers. The resulting theory is algebraic in flavor, e.g. all computable functions are piecewise semi-algebraic. The model is interesting but has some strange features that make it seem unrealistic, at least as a model of how computers actually deal with real number computation. For example it allows computation with uncomputable constants: the constant function with value Chaitin's constant is computable in the BSS model. On the other hand, $e^x$ is not computable in the BSS model.

Another approach can be found in the field of computable analysis, and I think that's what you are looking for. Check the book by Weihrauch for an introduction (the introduction and the chapter on computable real numbers are available on the linked page, and will give you a good idea of what is going on). There still are several not quite equivalent models here, but the rough idea is that rational numbers have finite representation, and then you construct the computable reals the same way you construct the reals as a completion of the rationals. So, analogously to defining a real as a (equivalence class of) a Cauchy sequence of rationals, a computable real is given by a Turing machine that computes arbitrarily good approximations to it. Then a function $f: \mathbb{R} \to \mathbb{R}$ is computable if a Turing machine can compute arbitrarily good approximations of $f(x)$ given (as an oracle) a machine that computes arbitrarily good approximations of $x$.

There are fascinating connections between computable analysis and classical/modern analysis and many other fields, for example algorithmic randomness. One simple example of a theorem is that all computable functions are continuous. To give a more sophisticated example (without actually going into the details), there are interesting counterparts to classical theorems in analysis, e.g. an analogue of Rademacher's theorem is that all computable Lipschitz functions $f:[0,1] \to [0,1]$ are differentiable at all algorithmically random points (for the right notion of algorithmic randomness).

Formulating a complexity theory for real functions is, AFAIK, even trickier. This is related to the fact that computing a real function is a higher-order computation (since it takes a Turing machine as input) so the bit size of the input is not usually the right thing to measure the runtime against. Check this paper by Mark Braverman for one approach to defining efficient real computation. At this point I am way out of my depth to say more, so I will stop.

$\endgroup$
8
$\begingroup$

The classic reference for complexity of computation of real functions is:

  • Ker-I Ko, Computational Complexity of Real Functions, 1991

Also have a look at chapter 7 in Weirauch's book.

$\endgroup$
-7
$\begingroup$

Looking at this question more than two years after it was posted and, no offense, I'm disappointed with the answers and comments.

This is what happens when CS departments all over the world mislabel their topics and mislead multiple generations of scientists and engineers.

  • Either the Algorithms classes in all CS departments need to be relabelled to Discrete Algorithms.

  • Or the current content of that class needs to be cut down to 50% or less (that 50% or less includes Data Structures) and the remaining half needs to include some assortment of topics from Numerical Analysis and Scientific Computing.

Because what is the core of Mathematical Analysis? Real Analysis and the real line. And how are real numbers represented in computers? floating point, or arbitrary precision, etc. So the next time you're working on any algorithm that deals with floating point and/or arbitrary precision as a core component (not as a content, as in sorting a bunch of floating point numbers), know that you're doing Algorithmic Mathematical Analysis (AMA)!

And don't even get me started with the massive universe of NA/Computational Science topics. It arguably dwarfs whole of TCS. When you're solving systems of multiple non-linear PDEs on a computer, you're not only utilizing the fundamentals of mathematical analysis, but cutting edge functional analysis in all its glory, complete with open research problems, etc. It can't get any more AMA than that.

$\endgroup$
  • 2
    $\begingroup$ I don't understand how your rant about the CS curriculum answers the question. $\endgroup$ – Sasho Nikolov Sep 30 '17 at 3:06
  • $\begingroup$ Well I don't understand how the rest of the answers and comments to this date answer even 1% of the question. And yet they're there. (some are even upvoted, and one is even accepted). And maybe 40% of my comment is not directly relevant to the question (though it indirectly is), yet the remaining 60% pretty much settles the issue. $\endgroup$ – Fi Zixer Sep 30 '17 at 3:13
  • 6
    $\begingroup$ The accepted answer gives a website with a wealth of information about computability and complexity over the reals. That's what the question asked for. It did not ask for opinions on the appropriateness of the CS curriculum. $\endgroup$ – Sasho Nikolov Sep 30 '17 at 3:19
  • 1
    $\begingroup$ We generally tend to downvote rants. If you had simply said that numerical analysis was, in some sense, algorithmic mathematical analysis, you might actually have gotten some upvotes. And, really, multiple generations of scientists and engineers have not been misled. You seem to be assuming that they're stupid. They're not; they know the difference between the stuff taught in algorithms classes and the stuff taught in numerical analysis classes. $\endgroup$ – Peter Shor Oct 2 '17 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.