De Sa Christopher, Gu Albert, Puttagunta Rohan, Ré Christopher, Rudra Atri
Department of Computer Science Cornell University.
Department of Computer Science, Stanford University, albertgu,rohanp,
Proc Annu ACM SIAM Symp Discret Algorithms. 2018 Jan;2018:1060-1079.
Matrix-vector multiplication is one of the most fundamental computing primitives. Given a matrix and a vector , it is known that in the worst case Θ( ) operations over F are needed to compute . Many types of structured matrices do admit faster multiplication. However, even given a matrix that is known to have this property, it is hard in general to recover a representation of exposing the actual fast multiplication algorithm. Additionally, it is not known in general whether the inverses of such structured matrices can be computed or multiplied quickly. A broad question is thus to identify classes of matrices that can be represented with () parameters, and for which matrix-vector multiplication (and ideally other operations such as solvers) can be performed in a sub-quadratic number of operations. One such class of structured matrices that admit near-linear matrix-vector multiplication are the whose rows correspond to a family of orthogonal polynomials. Other well known classes include the Toeplitz, Hankel, Vandermonde, Cauchy matrices and their extensions (e.g. confluent Cauchy-like matrices) that are all special cases of a low property. In this paper, we make progress on two fronts: Our work unifies, generalizes, and simplifies existing state-of-the-art results in structured matrix-vector multiplication. Finally, we show how applications in areas such as multipoint evaluations of multivariate polynomials can be reduced to problems involving low recurrence width matrices.
矩阵与向量相乘是最基本的计算原语之一。给定一个矩阵和一个向量，已知在最坏情况下，需要在有限域F上进行Θ( )次运算来计算。许多类型的结构化矩阵确实允许更快的乘法运算。然而，即使给定一个已知具有此属性的矩阵，通常也很难恢复该矩阵的一种表示形式，以揭示实际的快速乘法算法。此外，一般来说，尚不清楚此类结构化矩阵的逆矩阵是否可以快速计算或相乘。因此，一个广泛的问题是确定可以用( )个参数表示的矩阵类，对于这类矩阵，矩阵与向量相乘（理想情况下还有其他运算，如求解器）可以在低于二次方数量的运算中执行。一类允许近似线性矩阵与向量相乘的结构化矩阵是其行对应于一族正交多项式的矩阵。其他众所周知的矩阵类包括托普利兹矩阵、汉克尔矩阵、范德蒙德矩阵、柯西矩阵及其扩展（例如合流类柯西矩阵），它们都是低 性质的特殊情况。在本文中，我们在两个方面取得了进展：我们的工作统一、推广并简化了结构化矩阵与向量相乘方面现有的最先进结果。最后，我们展示了多元多项式多点求值等领域中的应用如何可以简化为涉及低递归宽度矩阵的问题。
