Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
home [2016-11-01] junheechohome [2023-03-18] (current) – [Mission] Martin Ziegler
Line 1: Line 1:
-====== Introduction ======+====== Computer Science for Continuous Data: Algorithmic Foundations of Numerics ======
  
-A computational decision problem $P$ consists of a family $\bar{x}_n$ of questions ('instances') that are to be answered with ''yes'' or ''no''For function probleminstances are to be answered with values from some set.+===== Motivation ===== 
 +Digital Computers naturally process discrete data, such as bits or integers or strings or graphsFrom bits to advanced data structures, from first semi-conducting transistor to billions in wafer-scale integrationfrom individual Boolean connectives to entire CPU circuits, from kB to TB memories, from 10<sup>2</sup> to 10<sup>9</sup> instructions per second, from assembly code to high-level programming languages: \\ 
 +the success story of digital computing arguably is due to (1) hierarchical layers of abstraction and (2) the ultimate reliability of each layer for the next one to build on ― for processing discrete data.
  
-Complexity is fundamental to theoretical computer science. For a problem $P$, it deals with the question:+Continuous data on the other hand commonly arises in Physics, Engineering and Science//natura non facit saltus//. 
 +Such data mathematically corresponds to real numbers, smooth functions, bounded operators, or compact subsets of some abstract metric space.
  
-> How expensive (in terms of resources like memory or, primarily, time) is a computational solution to $P$?+The rise of digital (over analog) computers led a stagnation in the realm of continuous (=//non//-discretizeddata processing: 
 +35 years after introduction and hardware standardization of IEEE 754 floating point numbers, mainstream Numerics is arguably still dominated by this forcible discretization of continuous data ― in spite of violating associative and distributive laws, breaking symmetries, introducing and propagating rounding errors, in addition to an involved (and incomplete) axiomatization including NaNs and denormalized numbers.
  
-However the question of computability logically precedes that of complexity:+{{https://cs4contidat.eu/floatingpoints.png}} 
 +Figure 1: Floating Point Number Line, from https://courses.engr.illinois.edu/cs357/fa2019/assets/images/figs/floatingpoints.png. See also https://www.jasss.org/9/4/4.html#2.1
  
-> Does $P$ admit of a computational solution at all?+\\
  
-Many problems are clearly computable (e.gby means of exhaustive search); but for others, computability is not obvious or even fails.+Deviations between mathematical structures and their hardware counterparts are common also in the discrete realm, 
 +such as the “integer” wraparound 255+1=0 occurring in bytes that led to the //[[https://en.wikipedia.org/wiki/Nuclear_Gandhi|Nuclear Gandhi]]// programming bug.
  
-Complexity generally measures the amount of some ressource necessary/sufficient in order to solve $P$asymptotically in terms of the input sizeTypical ressources are running time (#steps) or space (#memory cells); others, for instance in parallel computing, include the number of processors or the volume of communication.+Similarly, deviations between exact and approximate continuous data underlie infamous failures such as the  [[https://en.wikipedia.org/wiki/Ariane_flight_V88|Ariane 501 flight V88]] or the [[https://en.wikipedia.org/wiki/Sleipner_A|Sleipner-A oil platform]].
  
-Turing machines are generally agreed to be the appropriate mathematical idealization describing the capabilities of actual digital computers, that is, for problems involving finite binary strings, integers, or anything encodable as such (e.grational numbers with numerator/denominator or finite graphs). With regard to computations on real numbers on the other handtwo major extensions have become well established:+Nowadays high-level programming languages (such as Java or Python) provide a user data type (called for example ''BigInt'' or ''mpz_t'') that fully agrees with mathematical integers, simulated in software using a variable number of hardware bytes. 
 +This additional layer of abstraction provides the reliability for advanced discrete data types (such as weighted or labelled graphs) to build on, as mentioned above.
  
-  * //Recursive Analysis// considers computation on reals in terms of infinite approximations by rational numbers. +===== Mission ===== 
-  * //Blum-Shub-Smale machines// ('algebraic model'perform finitely many arithmetic operations on //real// numbers exactly.+We develop Computer Science for continuous data, to catch up with the discrete case: from foundations via practical implementation to commercial applications. 
 + 
 +In fact some object-oriented software libraries, such as [[http://irram.uni-trier.de/|iRRAM]] or [[https://cs.nyu.edu/exact/core_pages/intro.html|Core III]] or [[https://store.fmi.uni-sofia.bg/fmi/logic/theses/lambov/|realLib]] or [[http://ariadne-cps.org/|Ariadne]] or [[https://michalkonecny.github.io/aern/|Aern]], have long been providing general (=including all transcendental) real numbers as exact encapsulated user data type. 
 +Technically they employ finite but variable precision approximations: much like ''BigInt'', but with the added challenge of choosing said precision automatically and adaptively sufficient for the user program to appear as indistinguishable from exact reals. This requires a new (namely partial) semantics for real comparison: formalizing the folklore to “avoid” testing for equality, in terms of [[https://en.wikipedia.org/wiki/Three-valued_logic|Kleene's ternary logic]]. 
 + 
 +    [[http://sewonpark.com/sewon_park|Sewon Park]] in [[http://realcomputation.asia/THESES/21Sewon.pdf|his PhD Thesis]] has extended that semantics to composite expressions, and further to command sequences aka programs, whose correctness can then be symbolically verified using an extension of [[https://en.wikipedia.org/wiki/Hoare_logic|Floyd-Hoare Logic]]; 
 +see also the preprint [[http://arXiv.org/abs/1608.05787|arXiv:1608.05787]]. 
 + 
 +     * Thus reliably building on single real numbers leads to higher (but finite) dimensional data types, such as vectors or matrices. 
 +[[http://sewonpark.com/sewon_park|Sewon Park]] has designed and analyzed and implemented a [[https://github.com/realcomputation/irramplus/tree/master/GAUSSELIM|reliable variant of Gaussian Elimination]], in particular regarding pivot search. 
 +[[https://slee3379.math.gatech.edu/|Seokbin Lee]] has designed and analyzed and implemented a [[https://github.com/realcomputation/irramplus/tree/master/GRASSMANN|reliable variant of the Grassmannian]], i.e., the orthomodular lattice of subspaces of some fixed finite-dimensional Euclidean or unitary vector space. 
 + 
 +  * Infinite sequences of real numbers arise as elements of ℓ<sup>p</sup> spaces; and as coefficients to analytic function germs. 
 +[[http://www.holgerthies.com/|Holger Thies]] has implemented [[https://github.com/holgerthies|analytic functions for reliably solving ODEs and PDEs]]. 
 + 
 +See the references below for this and more [[https://github.com/realcomputation/irramplus|continuous data types on GitHub]]. 
 + 
 +Like discrete data, processing continuous data on a digital computer eventually boils down to processing bits: finite sequences of bits in the discrete case, in the continuous case infinite sequences, approximated via finite initial segments. 
 +Coding theory of discrete data is well-established since Claude Shannon’s famous work. 
 +Encoding real numbers as infinite sequences of bits is non-trivial: the binary expansion for example renders addition uncomputable. 
 +  *  [[https://www.donghyunlim.com/|Donghyun Lim]] in [[http://realcomputation.asia/THESES/19Donghyun.pdf|his MSc Thesis]] has investigated encoding more advanced (such as functionspaces; 
 + 
 +see also the [[https://arxiv.org/abs/2002.04005|preprint arXiv:2002.04005]]. 
 +  *  [[https://www.comp.nus.edu.sg/programmes/pg/phdcs/directory/|Ivan Koswara]] and [[http://www.lix.polytechnique.fr/Labo/Gleb.POGUDIN/|Gleb Pogudin]] and [[https://www.researchgate.net/profile/Svetlana-Selivanova|Svetlana Selivanova]] have [[http://cs4contidat.eu/yjcom101727.pdf|related the bit-complexity intrinsic to approximate solutions of linear partial differential equations]] to discrete complexity classes #P and PSPACE. 
 + 
 +  * [[http://informatik.uni-trier.de/~brausse/personal/index.xhtml|Franz Brauße]] and [[https://www.maastrichtuniversity.nl/pieter.collins|Pieter Collins]] envision a Computer <del>Algebra</del>//Analysis// System 
 + 
 +===== References ===== 
 +  * [[http://youtube.com/playlist?list=PLvcvykdwsGNE9HyG46aT6aqCvvJBZgKZh|30h online lecture series]] in [[https://youtube.com/channel/UCSehZy20EPRqgV0uiTzJkEA|YouTube channel]] 
 + 
 +  *  C++ classes for continuous data types: [[https://github.com/realcomputation|RealComputation]], [[https://github.com/holgerthies|Holger Thies]] 
 + 
 +  * [[https://doi.org/10.1007/978-3-031-14788-3_5|Vision paper]] 
 + 
 +  * [[https://doi.org/10.1016/j.jco.2022.101727|Recent publication characterizing the bit-complexity of Partial Differential Equations in terms of discrete complexity classes P/NP/#P/PSPACE/EXP]] 
 + 
 +  * [[https://arxiv.org/abs/2002.04005|Preprint on quantitative coding theory of continuous data]] 
 + 
 +  * [[https://arxiv.org/abs/1608.05787|Preprint on semantics and formal verification of programs processing real numbers exactly with partial semantics of comparison]] 
 + 
 +  * [[http://stoimenov.net/stoimeno/homepage/ckt/index.html|Workshop on Computational Knot Theory]] organized by [[http://stoimenov.net/stoimeno/homepage/|Alexander Stoimenow]] 
 + 
 +  * [[https://www.fiff.de/publikationen/fiff-kommunikation/fk-2022/fk-2022-2/fk-2022-2-content/fk-2-22-p25.pdf|Vision paper (in German) about Artificial Intelligence]], written jointly with [[https://www.fernuni-hagen.de/philosophie/lg1/team/andrea.reichenberger.shtml|Andrea Reichenberger]]
  
-The classical theory of computation (models and algorithms, computability and complexity, semantics and specification etc.) is concerned with discrete problems, that is, over bits or integers. We apply, adapt, and newly develop such methods and concepts to the many continuous problems pertaining to and arising in analysis/numerics, algebra, and physics. This includes devising and analyzing rigorous algorithms for calculations involving real (and complex) numbers, functions, and operators; and proving them optimal by relating to famous open conjectures like "$P \ne NP$", both in the bit-cost and in the algebraic model aka Blum-Shub-Smale machine. Promising (e.g. parameterized polynomial-time) algorithms are implemented in an imperative object-oriented programming language, and their practical performance evaluated empirically.