Robust Output Sensitive Algorithms for Subanalytic Geometry

亚解析几何的鲁棒输出敏感算法

• 批准号: 0211458
• 负责人: J Maurice Rojas
• 金额: $ 9.88万
• 依托单位: Texas A&M Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2005-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0211458&HistoricalAwards=false
• 关键词: Robust; Output; Sensitive; Algorithms; Subanalytic

The investigator aims to complete the nascent theory ofoutput-sensitive algorithms in real algebraic geometry.Output-sensitive in this context means that the complexity of theunderlying algorithm depends mainly on intrinsic geometricparameters, e.g., the number of connected components of theunderlying solution set, as opposed to extrinsic parameters likethe degrees of the input polynomials. Such algorithms are fasterthan the traditional methods of computational algebra by a factorexponential in the dimension, but have so far been discoveredonly in various isolated contexts. So a unified algorithmicapproach has a broad impact. Furthermore, the underlyingapproach takes numerical conditioning into account from theoutset, thus providing algorithms that are certifiably preciseeven when applied to approximate data. Another novelty is thatthe underlying theory applies in the even broader arena of realand p-adic analytic functions. The algorithmic aspects of p-adicanalytic functions are almost completely unexplored, so asecondary focus of this project is to elaborate and apply thisnew theory to equation-solving over finite fields and motivicintegration. The investigator combines advanced techniques from numericalanalysis and algebraic geometry to provide a new approach to afundamental problem occuring in many applications: solvinganalytic inequalities. For example, finding the optimalallocation of resources in a large organization (e.g., an army,an airline, or a large business) has long been known to reduce tosolving linear inequalities. From a different direction, it isknown that the complexity of certain neural net architectures(which are useful in training automated bomb-sniffers and patternrecognition systems) depends critically on understanding thesolutions of nonlinear polynomial inequalities. Both theseexamples are special cases of analytic inequalities, and thisproject provides new algorithms for their solution that aremagnitudes faster than current algorithms. Furthermore, thesenew algorithms provide certifiably precise solutions --- afeature which is especially important when facing uncertainphysical data. Another novel aspect is the principalinvestigator's recent discovery that the underlying techniquesapply to an even broader context, which can provide new solutionsto many problems in the design of cryptosystems.

研究者的目标是完成真实的代数几何中的输出敏感算法的新生理论。在这种情况下，输出敏感意味着底层算法的复杂性主要取决于内在的几何参数，例如，底层解决方案集的连接组件的数量，而不是外部参数，如输入多项式的次数。 这样的算法比传统的计算代数方法在维度上快一个因子指数，但到目前为止只在各种孤立的情况下被发现。 因此，统一的算法方法具有广泛的影响。 此外，基本的方法从一开始就考虑到数值条件，从而提供了即使应用于近似数据也可以证明精确的算法。 另一个新奇是，基本理论适用于更广泛的实和p-adic解析函数的竞技场。 p-adicanalytic函数的算法方面几乎完全未被探索，因此本项目的一个经济重点是阐述和应用这一新理论来求解有限域上的方程和动机积分。 调查员结合了numericalanalysis和代数几何的先进技术，提供了一种新的方法来解决许多应用中出现的基本问题：solvinganalytic不等式。 例如，在大型组织中找到资源的最佳分配（例如，军队、航空公司或大型企业）长期以来被认为可以简化为求解线性不等式。 从另一个角度来看，我们知道某些神经网络架构（在训练自动炸弹嗅探器和模式识别系统中很有用）的复杂性关键取决于对非线性多项式不等式的解的理解。 这两个例子都是解析不等式的特殊情况，本项目为它们的解提供了新的算法，比现有的算法快得多。 此外，这些新算法提供了可证明的精确解-这一特性在面对不确定的物理数据时尤为重要。 另一个新颖的方面是主要研究者最近发现，底层技术适用于更广泛的背景，这可以为密码系统设计中的许多问题提供新的解决方案。