bt365手机平台-下载首页

  • 研究人员礼貌形象

    全屏

总之算法,远距离的后果

为解决“图形拉普拉斯算子”的新技术显着比它的前辈更简单,有一个巨大的实际问题范围的影响。


在过去十年中,计算机科学理论已经看到了解决图形拉普拉斯算子的问题,显着的进步 - 与在调度熟悉的应用程序,图像处理,网络产品推荐,网络分析和科学计算成群的计算深奥的名字,来命名一些。仅在2004年也研究人员首次提出了一种算法,解决了图形拉普拉斯算子在“近似线性的时间”,这意味着,该算法的运行时间并没有随着问题的规模成倍增加。
 

该动画显示了两种不同的简单图“生成树”,像在许多科学计算中使用的网格。由bt365手机app的新算法承诺的加速需要“低弹性”生成树(绿色),其中,相邻节点之间的路径不会变得过长(红色)。 研究人员的图像礼貌

在今年的计算理论研讨会ACM,MIT的研究人员将出席 新算法 求解图拉普拉斯算子,不仅比它的前辈快,但也大大简化。 “需要在数学和计算机科学的多个分支根本创新的2004年文件,但它最终被分成三篇文章,我认为是在总130页,说:”乔纳森kelner,应用数学bt365手机app的副教授谁领导新的研究。 “我们能够使用的东西,将适合在黑板来取代它。”

bt365手机app的研究人员 - kelner;洛伦佐orecchia,在应用数学指导员;和kelner的学生阿龙sidf要么d和泽源珠 - 相信他们的算法的简单性应该让速度更快,更容易在软件比它的前辈落实。但同样重要的是,他们的概念分析,他们认为,应该让他们的结果更容易推广到其他情境的简单性。

克服阻力

图的拉普拉斯是一个矩阵 - 数字的大网格 - 一个描述 图形在计算机科学中常见的数学抽象。的曲线图是节点,通常被描绘为圆形,和边缘,描绘为连接节点线的任​​何集合。在物流问题,要执行的节点可能代表的任务,而在网上推荐引擎,它们可能代表电影的标题。

在许多图表,边缘被“加权”,这意味着他们有与之相关联的不同的数字。这些数字可能代表成本 - 在时间,金钱和精力 - 从一步移动到另一个在一个复杂的后勤行动的,或者他们可能代表一个在线视频服务的客户的喜好电影之间的相关性的强度。

的曲线图的拉普拉斯描述了所有的边缘之间的权重,但它也可以被解释为一系列线性方程。解决这些方程是用于分析图表的许多技术是至关重要的。

考虑图拉普拉斯算子一个直观的方式是想象图作为一个大的电路和边缘作为电阻器。边缘的权重描述电阻器的电阻;解决拉普拉斯告诉你多少电流将图中的任何两个点之间流动。

早些时候的方式来解决审议了一系列的利益图表的日益逼近简单的图形拉普拉斯算子。解决最简单的提供下一个最简单的,它提供了一种最简单的一个很好的近似,等等的良好近似。但构造图的顺序可以得到非常复杂的,而且证明是最简单的解决方案是最复杂的一个很好的近似规则需要大量的数学匠心。

环回

bt365手机app的研究人员的做法是要简单得多。他们做的第一件事就是寻找图中的“生成树”。树是一种特殊的图形不具有闭环。家谱是一个熟悉的例子;在那里,一个循环可能意味着有人在两家母公司和兄弟姐妹同一个人。图的生成树是触及所有图形的节点,但与创建环路边缘分配的树。构建生成树高效的算法已经非常成熟。

在手生成树,bt365手机app的算法,然后重新添加刚刚丢失的边缘之一,创建一个循环。一个循环是指两个节点通过两个不同的路径连接;在电路类推,电压将必须跨越两个路径是相同的。所以在当前的流动是平衡的循环值的算法棒。然后将其添加回另一个缺棱和重新平衡。

即使一个简单的图形,珍视平衡一个循环可以失衡另一个。但bt365手机app的研究表明,显着地,增加边和再平衡的这种简单重复的过程会收敛于图形拉普拉斯算子的解决方案。也没有上述会聚演示需要复杂的数学:“一旦你找到思考这个问题的正确方法,一切都只是属于地方,” kelner解释。

模式转变

丹尼尔·斯皮尔曼,应用数学教授和计算机科学在耶鲁大学,是kelner的论文指导老师和2004年论文的两位联合作者之一。根据斯皮尔曼,他的算法上,你永远不会遇到,除非它是一个更大的宇宙比我们知道的天文大小的问题解决了拉普拉斯算子在接近线性的时间”。乔恩和同事的算法实际上是很实际的问题。”

斯皮尔曼指出,在2010年,研究人员在卡内基梅隆大学还提出了一个实际的算法求解拉普拉斯算子。理论分析表明,美国bt365手机app的算法应该是有所加快,但“所有这些事情的奇怪的现实是,你做了很多的分析,以确保一切正常,但你有时会异常幸运,或者是格外倒霉,当你实现他们。所以我们必须等待,看看这果然是这样。”

bt365手机app的论文的真正价值,斯皮尔曼说,是其创新的理论方法。 “我的工作和乡亲在卡内基梅隆大学的工作,我们在数字线性代数使用的技术从数值线性代数的领域解决问题,”他说。 “乔恩的纸张完全无视所有这些技术和真正解决利用数据结构和算法设计思路这个问题。它取代了一整套的想法,另一组的想法,我认为这将是一个有点改变游戏规则的领域。因为人们会看到有这样的一套想法,在那里,可能有应用程序没有任何人的想象。”


主题: 算法, 图论, 拉普拉斯算子, 线性代数, 图的拉普拉斯, 数学, 理论计算机科学

评论

这是最好的科学的最外行文章中,我在相当长的一段读过。

这确实是一个很好的科学贡献。但令人吃惊的是“时间”出现的字纸的50倍以上,而没有数值实验报告显示解决一个实际问题所需的实际时间。

该agmg软件也许是基于复杂的或老式的“机器”,但用户并不需要关心,和软是相当容易使用。和接近线性的时间不只是一个理论上的承诺,但有些事,每个人都可以检查。

“这不是我这么聪明,我只是留在较长的问题,”爱因斯坦

数字移动比单词的速度。然而,我们需要他们两个:文字和数字。有没有足够的微观锋利的寻找到我们的灵魂。

回到顶部