论文标题
统一矩阵数据结构：简化和加速迭代算法
Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms
论文作者
论文摘要
许多算法使用的数据结构可以维护经历一些更改的矩阵的属性。这些应用程序是广泛的，包括匹配，最短路径，线性编程，半明确编程，凸赫尔和音量计算。鉴于广泛的应用程序，这些数据结构必须维护的确切属性从一个应用程序到另一个应用程序，迫使算法设计人员从头开始发明它们或修改现有的算法。因此，毫不奇怪，这些数据结构及其证明通常是针对其特定应用量身定制的，并且维护更复杂的属性会导致更复杂的证据。 在本文中，我们提出了一个统一的框架，该框架捕获了许多这些数据结构。该框架的简单性使我们能够为许多现有的数据结构提供简短的证明，而不管要维护的属性多么复杂。我们还展示了如何使用该框架来加快现有的迭代算法，例如单纯形算法。 更正式地，考虑使用输入矩阵$ a_1，...，a_d $的任何有理函数$ f（a_1，...，a_d）$。我们表明，在更新为$ a_1，...，a_d $下，维护$ f（a_1，...，a_d）$的任务可以简化为更简单的问题，即在更新为$ m $的情况下维护某些矩阵倒数$ m^{ - 1} $。后者是一个经过深入研究的问题，称为动态矩阵逆。通过应用我们的还原并使用已知算法进行动态矩阵逆，我们可以获得快速数据结构和迭代算法，以解决更多一般的问题。
Many algorithms use data structures that maintain properties of matrices undergoing some changes. The applications are wide-ranging and include for example matchings, shortest paths, linear programming, semi-definite programming, convex hull and volume computation. Given the wide range of applications, the exact property these data structures must maintain varies from one application to another, forcing algorithm designers to invent them from scratch or modify existing ones. Thus it is not surprising that these data structures and their proofs are usually tailor-made for their specific application and that maintaining more complicated properties results in more complicated proofs. In this paper we present a unifying framework that captures a wide range of these data structures. The simplicity of this framework allows us to give short proofs for many existing data structures regardless of how complicated the to be maintained property is. We also show how the framework can be used to speed up existing iterative algorithms, such as the simplex algorithm. More formally, consider any rational function $f(A_1,...,A_d)$ with input matrices $A_1,...,A_d$. We show that the task of maintaining $f(A_1,...,A_d)$ under updates to $A_1,...,A_d$ can be reduced to the much simpler problem of maintaining some matrix inverse $M^{-1}$ under updates to $M$. The latter is a well studied problem called dynamic matrix inverse. By applying our reduction and using known algorithms for dynamic matrix inverse we can obtain fast data structures and iterative algorithms for much more general problems.
