Skip to Main content Skip to Navigation
New interface
Conference papers

Solving Toeplitz- and Vandermonde-like linear systems with large displacement rank

Alin Bostan 1 Claude-Pierre Jeannerod 2 Éric Schost 3 
2 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Linear systems with structures such as Toeplitz-, Vandermonde-or Cauchy-likeness can be solved in $O\,\tilde{~}(\alpha^2 n)$ operations, where $n$ is the matrix size, $\alpha$ is its displacement rank, and $O\,\tilde{~}$ denotes the omission of logarithmic factors. We show that for Toeplitz-like and Vandermonde-like matrices, this cost can be reduced to $O\,\tilde{~}(\alpha^{\omega-1} n)$, where $\omega$ is a feasible exponent for matrix multiplication over the base field. The best known estimate for $\omega$ is $\omega < 2.38$, resulting in costs of order $O\,\tilde{~}(\alpha^{1.38} n)$. We also present consequences for Hermite--Pad\'e approximation and bivariate interpolation.
Document type :
Conference papers
Complete list of metadata
Contributor : Claude-Pierre Jeannerod Connect in order to contact the contributor
Submitted on : Tuesday, November 9, 2021 - 1:43:51 PM
Last modification on : Tuesday, October 25, 2022 - 4:20:32 PM
Long-term archiving on: : Thursday, February 10, 2022 - 6:49:26 PM


Files produced by the author(s)




Alin Bostan, Claude-Pierre Jeannerod, Éric Schost. Solving Toeplitz- and Vandermonde-like linear systems with large displacement rank. International Symposium on Symbolic and Algebraic Computation (ISSAC), Jul 2007, Waterloo, Canada. pp.33, ⟨10.1145/1277548.1277554⟩. ⟨hal-03420744⟩



Record views


Files downloads