利用随机性的新算法打破了求解线性方程组的速度限制 - quantamagazine

21-03-10 banq

通过利用随机性的新算法从根本上实现了一种新颖且更快的方式,可以执行数学和计算机科学中最基本的计算之一。

这一新方法由乔治亚州理工学院的Richard PengSantosh Vempala于7月份在线发布,并于1月在年度ACM-SIAM离散算法研讨会上进行了介绍,并获得了最佳论文奖。

线性系统是计算机科学中许多基本优化问题的特征,这些问题涉及为约束系统中的一组变量寻找最佳值。如果我们可以更快地解决线性系统,那么我们也可以更快地解决那些问题。

Peng和Vempala证明了他们的算法可以n阶2.332的步长求解任何稀疏线性系统。这比矩阵乘法的最佳算法(n 2.37286)快了约四十分之一。虽然这只是作为概念证明,实现了轻微的改进,但是它表明存在一种解决线性系统的更好的方法。

详细点击标题见原文

猜你喜欢