期刊
LINEAR ALGEBRA AND ITS APPLICATIONS
卷 438, 期 9, 页码 3563-3575出版社
ELSEVIER SCIENCE INC
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. (C) 2013 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据