# Nearly Optimal Computations with Structured Matrices

2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
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 most popular classes, that is, Toeplitz, Hankel, Cauchy and Van\-der\-monde 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 \cite{kirrinnis-joc-1998}, except for rational interpolation, which we supply now. All known Boolean cost estimates for these 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 representation of our tasks and algorithms in terms of both structured matrices and 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.
Keywords :
Type de document :
Communication dans un congrès
SNC '14 - Symposium on Symbolic-Numeric Computation, Jul 2014, Shanghai, China. Proceedings of the 2014 Symposium on Symbolic-Numeric Computation, pp.21-30, 〈http://symbolic-numeric-computation.org/snc-2014/〉. 〈10.1145/2631948.2631954〉
Domaine :

Littérature citée [25 références]

https://hal.inria.fr/hal-00980591
Contributeur : Elias Tsigaridas <>
Soumis le : vendredi 18 avril 2014 - 12:35:23
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:37:36

### Fichiers

pt-struct-snc.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Victor Y. Pan, Elias Tsigaridas. Nearly Optimal Computations with Structured Matrices. SNC '14 - Symposium on Symbolic-Numeric Computation, Jul 2014, Shanghai, China. Proceedings of the 2014 Symposium on Symbolic-Numeric Computation, pp.21-30, 〈http://symbolic-numeric-computation.org/snc-2014/〉. 〈10.1145/2631948.2631954〉. 〈hal-00980591〉

### Métriques

Consultations de la notice

## 390

Téléchargements de fichiers