2013/01/24 by Khalil, Houssam, Mourrain, Bernard, Schatzman, Michelle
#FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.1301.5798
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 log2 n) for a Toeplitz matrix of size nxn.