Nearly optimal computations with structured matrices

Victor Y. Pan 1 Elias Tsigaridas 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : We estimate the Boolean complexity of multiplication of structured matrices by a vector and the solution of nonsingular linear systems of equations with these matrices. We study four basic and most popular classes, that is, Toeplitz, Hankel, Cauchy and Vandermonde matrices, for which the cited computational problems are equivalent to the task of polynomial multiplication and division and polynomial and rational multipoint evaluation and interpolation. The Boolean cost estimates for the latter problems have been obtained by Kirrinnis in [10], except for rational interpolation. We supply them now as well as the Boolean complexity estimates for the important problems of multiplication of transposed Vandermonde matrix and its inverse by a vector. All known Boolean cost estimates from [10] for such problems rely on using Kronecker product. This implies the d-fold precision increase for the d-th degree output, but we avoid such an increase by relying on distinct techniques based on employing FFT. Furthermore we simplify the analysis and make it more transparent by combining the representations of our tasks and algorithms both via structured matrices and via polynomials and rational functions. This also enables further extensions of our estimates to cover Trummer’s important problem and computations with the popular classes of structured matrices that generalize the four cited basic matrix classes, as well as the transposed Vandermonde matrices. It is known that the solution of Toeplitz, Hankel, Cauchy, Vandermonde, and transposed Vandermonde linear systems of equations is generally prone to numerical stability problems, and numerical problems arise even for multiplication of Cauchy, Vandermonde, and transposed Vandermonde matrices by a vector. Thus our FFT-based results on the Boolean complexity of these important computations could be quite interesting because our estimates are reasonable even for more general classes of structured matrices, showing rather moderate growth of the complexity as the input size increases.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2017
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger
Contributeur : Elias Tsigaridas <>
Soumis le : samedi 12 décembre 2015 - 15:41:22
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03
Document(s) archivé(s) le : samedi 29 avril 2017 - 11:55:43


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01105263, version 2



Victor Y. Pan, Elias Tsigaridas. Nearly optimal computations with structured matrices. Theoretical Computer Science, Elsevier, 2017. 〈hal-01105263v2〉



Consultations de la notice


Téléchargements de fichiers