A Toolkit for Non-linear Algebra

这个项目承担了一个代数几何工具包的实现，用C语言编写，可以解决 复数上的方程组和实数上的不等式。 有 这样的工具包的许多应用程序，因为许多分支的问题， 科学和工程可以用多项式方程系统来表述， 不等式 通过几个著名的定理，特别是塔斯基定理 实际上，这些问题在原则上是可以解决的。 但 最坏情况的界限是指数或双指数的数量， 变量，没有实际的系统已经出现，可以处理超过几个 特殊情况。 另一方面，多项式系统可能具有特殊的 结构，一种稀疏性，这意味着复杂性（由 代数次数）远低于最坏情况。 事实上，大多数重要的 应用程序就是这种类型。 最近，算法已经被开发出来， 可以利用这种结构。 这种认识是一种强烈的动机， 在这个时候开发工具包。 此外，在以下方面也有改进： 算法的符号确定和符号数字计算，它是 我认为这些方法现在已经足够先进，值得实施。

This project undertakes the implementation of an algebraic-geometric toolkit, written in C, which can solve systems of equations over the complex numbers, and inequalities over the reals. There are many applications of such a toolkit, since problems from many branches of science and engineering can be formulated using systems of polynomial equations and inequalities. By several well-known theorems, in particular, Tarski's theorem for the reals, it is possible to solve such problems in principle. But the worst case bounds are exponential or doubly-exponential in the number of variables, and no practical system has appeared that can deal with more than a few special cases. On the other hand, systems of polynomials may have a special structure, a kind of sparseness, that implies a complexity (measured by the algebraic degree) much lower than the worst case. Indeed, most of the important applications are of this type. Very recently, algorithms have been developed that can exploit this structure. This realization is a strong motivation for developing the toolkit at this time. In addition, there have been improvements in algorithms for sign determination and symbolic-numeric computation, and it is felt that these methods are now advanced enough to warrant implementation.