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.
Type de document :
Article dans une revue
Linear Algebra and its Applications, Elsevier, 2013, 438 (9), pp.3563-3575. <10.1016/j.laa.2013.01.015>
Liste complète des métadonnées


https://hal.inria.fr/hal-00780556
Contributeur : Bernard Mourrain <>
Soumis le : jeudi 24 janvier 2013 - 11:54:55
Dernière modification le : mardi 3 mai 2016 - 15:11:53
Document(s) archivé(s) le : jeudi 25 avril 2013 - 03:52:17

Fichiers

paper-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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>

Partager

Métriques

Consultations de
la notice

328

Téléchargements du document

251