Special Topics in Computer Science I (CS493) in Summer 2018: Algorithmic Foundation of Numerics

This course offers a hands-on introduction to the rigorous foundations of computing with continuous data (real numbers, sequences, functions): from in/computability via complexity to programming practice.

Purpose and Goals

We emphasize the difference between a recipe/heuristic and an algorithm. You will be reminded of aspects from the classical (i.e. discrete) Theory of Computation, from computability to complexity. We then apply it to numerical problems, yielding a rigorous perspective on the (i) computability, (ii) complexity, and (iii) semantics of: real tests, root finding, differentiation, maximization, integration, ODE and PDE solving. The course culminates in a programming assignment in iRRAM: a C++ library providing via object-oriented overloading an abstract data type REAL. In addition, each week will conclude with a theoretical homework assignment.

Administrative

Lecturer: Martin Ziegler

Language: English only

Prerequisites: Introduction to Computer Science, Discrete Mathematics, Calculus I, C++, root on some Linux computer

Grading: 10% attendance, 50% homework/programming assignments, 40% final exam

Schedule

  • Tue, July 3, 12:10-13:00
  • Wed, July 4, 12:10-13:00
  • Thu, July 5, 12:10-13:00
  • Fri, July 6, 9:00-12:00
  • Tue, July 10, 12:10-13:00
  • Wed, July 11, 12:10-13:00
  • Thu, July 12, 12:10-13:00
  • Tue, July 17, 12:10-13:00
  • Wed, July 18, 12:10-13:00
  • Thu, July 19, 12:10-13:00
  • Fri, July 20, 9:00-12:00
  • Tue, July 24, 12:10-13:00
  • Wed, July 25, 12:10-13:00
  • Thu, July 26, 12:10-13:00

Synopsis

  1. Recap on Discrete Computability:
    • Halting Problem
    • Un/Semi/Decidability/Enumerability
    • Reductions
    • WHILE Programs
    • Oracles
  2. Computing over the Reals
    • Computable Real numbers: non/equivalent notions
    • Equality, real sequences and limits
    • Computing real functions, Effective Weierstrass Theorem
    • Computational cost, compactness, and continuity
    • Root finding and uncomputable argmax
    • Uncomputable derivative/wave equation
    • Non-extensionality, discrete enrichment
  3. Recap on Discrete Complexity:
    • Runtime and memory, asymptotically
    • Complexity classes P, NP, #P, PSPACE, EXP
    • Polynomial-time reductions
    • Cook-Levin Theorem (w/o proof)
  4. Real Complexity Theory
    • Real arithmetic, join, maximum, integral
    • Polynomial-time un/computable reals
    • Polynomial-time un/computable functions
    • Maximizing smooth functions and P/NP
    • Riemann Integration and #P, ODEs and PSPACE
    • Complexity Phase Transition and Gevrey's Hierarchy
  5. Practice of Exact Real Computation
    • iRRAM library
    • Semantics of tests and choose()
    • Example Algorithms

Reading List

Suggested Literature

  • Ker-I Ko: Complexity Theory of Real Functions, Birkhäuser (1991).
  • Klaus Weihrauch: Computable Analysis: An Introduction, Springer (2000).
  • Akitoshi Kawamura, Stephen Cook: Complexity Theory for Operators in Analysis, ACM Transactions on Computation Theory 4 (2012).
  • Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick, Martin Ziegler: Computational Complexity of Smooth Differential Equations, Logical Methods in Computer Science (2014).
  • Akitoshi Kawamura, Norbert Müller, Carsten Rösnick, Martin Ziegler: Computational Benefit of Smoothness: Parameterized Bit-Complexity of Numerical Operators on Analytic Functions and Gevrey's Hierarchy, pp.689-714 in the Journal of Complexity vol.31:5 (2015).
  • Akitoshi Kawamura, Florian Steinberg, Martin Ziegler: On the Computational Complexity of the Dirichlet Problem for Poisson's Equation, Mathematical Structures in Computer Science (2017).