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, 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 metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-00780556
Contributor : Bernard Mourrain <>
Submitted on : Thursday, January 24, 2013 - 11:54:55 AM
Last modification on : Wednesday, December 12, 2018 - 3:27:08 PM
Long-term archiving on : Thursday, April 25, 2013 - 3:52:17 AM

Files

paper-hal.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

521

Files downloads

399