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

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00780556
Contributeur : Bernard Mourrain <>
Soumis le : jeudi 24 janvier 2013 - 11:54:55
Dernière modification le : samedi 11 novembre 2017 - 01:13:02
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

351

Téléchargements de fichiers

258