Skip to Main content Skip to Navigation
New interface
Journal articles

Superfast solution of Toeplitz systems based on syzygy reduction

Houssam Khalil 1, 2 Bernard Mourrain 1 Michelle Schatzman 2 
1 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis (1965 - 2019), CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : 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 nxn.
Document type :
Journal articles
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Bernard Mourrain Connect in order to contact the contributor
Submitted on : Thursday, January 24, 2013 - 11:54:55 AM
Last modification on : Saturday, September 24, 2022 - 3:36:05 PM
Long-term archiving on: : Thursday, April 25, 2013 - 3:52:17 AM


Files produced by the author(s)



Houssam Khalil, Bernard Mourrain, Michelle Schatzman. Superfast solution of Toeplitz systems based on syzygy reduction. Linear Algebra and its Applications, 2013, 438 (9), pp.3563-3575. ⟨10.1016/j.laa.2013.01.015⟩. ⟨hal-00780556⟩



Record views


Files downloads