conference paper
Computability of Linear Equations
published
Vasco
Brattka
author
Martin
Ziegler
author
63
department
Do the solutions of linear equations depend computably on their coefficients? Implicitly, this has been one of the central questions in linear algebra since the very beginning of the subject and the famous Gauß algorithm is one of its numerical answers. Today there exists a tremendous number of algorithms which solve this problem for different types of linear equations. However, actual implementations in floating point arithmetic keep exhibiting numerical instabilities for ill-conditioned inputs. This situation raises the question which of these instabilities are intrinsic, thus caused by the very nature of the problem, and which are just side effects of specific algorithms. To approach this principle question we revisit linear equations from the rigorous point of view of computability. Therefore we apply methods of computable analysis, which is the Turing machine based theory of computable real number functions. It turns out that, given the coefficients of a system of linear equations, we can compute the space of solutions, if and only if the dimension of the solution space is known in advance. Especially, this explains why there cannot exist any stable algorithms under weaker assumptions.
2002
eng
Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science10.1007/978-0-387-35608-2_9
95-106
Brattka, V., & Ziegler, M. (2002). Computability of Linear Equations. In <i>Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science</i> (pp. 95–106). Boston, MA. <a href="https://doi.org/10.1007/978-0-387-35608-2_9">https://doi.org/10.1007/978-0-387-35608-2_9</a>
Brattka, Vasco, and Martin Ziegler. “Computability of Linear Equations.” <i>Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science</i>, 2002, pp. 95–106, doi:<a href="https://doi.org/10.1007/978-0-387-35608-2_9">10.1007/978-0-387-35608-2_9</a>.
Brattka V, Ziegler M. Computability of Linear Equations. In: <i>Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science</i>. Boston, MA; 2002:95-106. doi:<a href="https://doi.org/10.1007/978-0-387-35608-2_9">10.1007/978-0-387-35608-2_9</a>
@inproceedings{Brattka_Ziegler_2002, place={Boston, MA}, title={Computability of Linear Equations}, DOI={<a href="https://doi.org/10.1007/978-0-387-35608-2_9">10.1007/978-0-387-35608-2_9</a>}, booktitle={Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science}, author={Brattka, Vasco and Ziegler, Martin}, year={2002}, pages={95–106} }
Brattka, Vasco, and Martin Ziegler. “Computability of Linear Equations.” In <i>Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science</i>, 95–106. Boston, MA, 2002. <a href="https://doi.org/10.1007/978-0-387-35608-2_9">https://doi.org/10.1007/978-0-387-35608-2_9</a>.
V. Brattka and M. Ziegler, “Computability of Linear Equations,” in <i>Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science</i>, 2002, pp. 95–106.
V. Brattka, M. Ziegler, in: Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science, Boston, MA, 2002, pp. 95–106.
181792020-08-24T12:11:07Z2020-08-24T12:21:56Z