Computational tropical geometry and its applications

计算热带几何及其应用

• 批准号: MR/S034463/2
• 负责人: Yue Ren
• 金额: $ 55.54万
• 依托单位: Durham University
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2021
• 资助国家: 英国
• 起止时间: 2021 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=MR%2FS034463%2F2
• 关键词: Computational; tropical; geometry; its; applications

Tropical geometry is a young area of mathematics which studies combinatorial objects arising from polynomial equations. These so-called tropical varieties arise naturally in many areas of mathematics and beyond, such as phylogenetics in biology, celestial mechanics in physics, and auction theory in economics. Wherever they arise, tropical varieties often allow new computational approaches to existing problems. In the UK, the Bank of England has been using tropical geometry since the financial crises to allocate money to the UK financial system. In France, tropical geometry is used for optimisation of load balancing of mobile networks, and performance analysis of emergency call centres.This research projects aims at establishing tropical geometry as a powerful and versatile tool for computational questions in applied sciences and industry beyond optimisation. To this end, we pursue concrete applications as well as improvements of computational methods. The final deliverable is a comprehensive open source software system for tropical algebraic geometry with strong emphasis on its wide spectrum of applications. We focus on three main problems, which were chosen to maximise the impact and the range of techniques that they encompass.The first problem revolves around systems of polynomial equations, which are ubiquitous in applied science. They describe the steady states of chemical reaction networks, the range of movement of a robot arm, or the binding behaviour of ligands in a biochemical system. For over two decades, the state of the art for solving such systems has been homotopy continuation, which works by carefully deforming an easy start system to the target system while tracing all solutions along the way.We seek to improve the existing capabilities, in particular for the type of polynomial systems which arise in the aforementioned applications. While ideas to apply tropical geometry to homotopy continuation have already been studied, all past approaches have failed due to questions of efficiency. However, the last couple of years have seen significant algorithmic breakthroughs in tropical geometry, which we will exploit and build upon.The second problem involves p-adic numbers, which are an indispensable class of fields for number theory. This not only makes them important for the applications of tropical geometry in number theory, but also entails a vast array of number theoretic tools available exclusively over them. Hence a good grasp on tropical geometry over p-adics numbers is an imperative for both theory and practice.That being said, computationally, tropical geometry over p-adic numbers has been neglected due to the unique algorithmic challenges they pose. We seek to remedy this situation and explore computational aspects of tropical geometry specifically over p-adic numbers, facilitated by recent trends in computer algebra.The third problem involves Gröbner bases, which have long history in computational algebraic geometry and adjacent fields such as cryptography. Furthermore, the past decade featured an explosion of algebro-geometric techniques in areas outside of mathematics. As such, Gröbner bases have gained traction both as tool for studying polynomial systems and as object of interest themselves, e.g., as Markov bases in algebraic statistics. However, Gröbner bases are notoriously hard to compute, which severely inhibits their use in practical applications.We will investigate so-called saturating Gröbner bases. In general, polynomial unknowns represent arbitrary elements of the coefficient field, and all operations within a Gröbner basis computation respect this ambiguity. In practice, one is often only interested in specific solutions, e.g. strictly positive real solutions. Saturating Gröbner basis algorithm are symbolic algorithms which are capable of exploiting this numerical information that is abundant in many applications and use it to speed up its performance.

热带几何是一个年轻的数学领域，研究由多项式方程产生的组合对象。这些所谓的热带品种自然而然地出现在许多数学和其他领域，如生物学中的系统发育学、物理学中的天体力学和经济学中的拍卖理论。无论它们出现在哪里，热带品种通常都允许用新的计算方法来解决现有的问题。在英国，自金融危机以来，英国央行一直在利用热带几何学向英国金融体系配置资金。在法国，热带几何学被用于优化移动网络的负载平衡，以及紧急呼叫中心的性能分析。这项研究项目旨在将热带几何学建立为一种强大而通用的工具，用于解决应用科学和工业中超越优化的计算问题。为此，我们寻求具体的应用以及计算方法的改进。最终交付的是热带代数几何的全面开源软件系统，强调其广泛的应用范围。我们集中在三个主要问题上，这三个问题是为了最大化影响和它们所包含的技术范围。第一个问题围绕着在应用科学中普遍存在的多项式方程组。它们描述了化学反应网络的稳定状态，机器人手臂的运动范围，或生化系统中配体的结合行为。二十多年来，求解这类系统的最新技术一直是同伦延拓，它通过小心地将一个容易启动的系统变形到目标系统，同时跟踪沿途的所有解。我们寻求改进现有的能力，特别是对于在上述应用中出现的类型的多项式系统。虽然将热带几何应用于同伦延拓的想法已经被研究过，但由于效率问题，所有过去的方法都失败了。然而，在过去的几年里，热带几何在算法上取得了重大突破，我们将在此基础上加以开发和建立。第二个问题涉及p-进数，这是数论中不可或缺的一类领域。这不仅使它们对于热带几何在数论中的应用非常重要，而且还需要大量专门针对它们的数论工具。因此，很好地掌握p-adics数上的热带几何对于理论和实践都是非常必要的。也就是说，在计算上，p-adics数上的热带几何由于其独特的算法挑战而被忽略。第三个问题涉及Gröbner基，它在计算代数几何和密码学等相邻领域有着悠久的历史。此外，在过去的十年里，代数几何技术在数学以外的领域出现了爆炸性的增长。因此，Gröbner基既作为研究多项式系统的工具，也作为感兴趣的对象本身，例如，作为代数统计中的马尔可夫基。然而，Gröbner基是出了名的难于计算，这严重限制了它们在实际应用中的应用。我们将研究所谓的饱和Gröbner基。一般来说，多项式未知数表示系数域的任意元素，而Gröbner基计算中的所有运算都考虑到这种模糊性。在实践中，人们通常只对特定的解感兴趣，例如严格的正实解。饱和Gröbner基算法是一种符号算法，它能够利用在许多应用中丰富的数值信息，并利用它来提高其性能。

项目成果

Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums

• DOI: 10.1137/21m1413699
• 发表时间: 2021-04
• 期刊: SIAM J. Appl. Algebra Geom.
• 作者: Guido Montúfar;Yue Ren;Leon Zhang

Computing zero-dimensional tropical varieties via projections

通过投影计算零维热带品种

• DOI: 10.1007/s00037-022-00222-9
• 发表时间: 2022
• 期刊: computational complexity
• 影响因子: 1.4
• 作者: Görlach P