“线性代数中的可计算性”(2004)

线性代数中的许多问题都可以用高斯消元法来解决。这个著名的算法适用于实数计算的代数模型，其中运算+、-、*/以及例如<；和==之类的测试假定是精确的。代数算法在实际数字计算机上的实现往往会导致数值不稳定，从而暴露出模型与现实之间的严重差异。

追溯到艾伦·图灵(Alan Turing)的另一种实数计算模型认为实数是有理近似的极限。在被广泛认为是更现实的可计算性概念中，我们研究了线性代数中的问题。我们的中心结果产生了在这个意义上的算法。

假设A的秩和B的不同特征值的个数是已知的。如果没有这样的限制，前两个问题通常是无法计算的。

由帕德伯恩科学计算研究所(PASCO)DFG研究训练组GK-693支持。