Superfast solution of Toeplitz systems based on syzygy reduction

作者：Khalil Houssam^*; Mourrain Bernard; Schatzman Michelle

来源：Linear Algebra and Its Applications, 2013, 438(9): 3563-3575.

DOI：10.1016/j.laa.2013.01.015

• Toeplitz matrices
• Polynomial division
• Syzygies of polynomials

We present a new superfast algorithm for solving Toeplitz systems. This algorithm is based on a relation between the solution of such problems and syzygies of polynomials or moving lines. We show an explicit connection between the generators of a Toeplitz matrix and the generators of the corresponding module of syzygies. We show that this module is generated by two elements and the solution of a Toeplitz system T u = g can be reinterpreted as the remainder of a vector depending on g, by these two generators. We obtain these generators and this remainder with computational complexity O(n log(2) n) for a Toeplitz matrix of size n x n.

• 出版日期2013-5-1
• 单位INRIA