Skip to Main content Skip to Navigation
New interface
Journal articles

Solving structured 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 such 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 present consequences for Hermite--Pad\'e approximation and bivariate interpolation.
Document type :
Journal articles
Complete list of metadata
Contributor : Claude-Pierre Jeannerod Connect in order to contact the contributor
Submitted on : Tuesday, November 9, 2021 - 1:34:51 PM
Last modification on : Tuesday, October 25, 2022 - 4:18:34 PM
Long-term archiving on: : Thursday, February 10, 2022 - 6:48:25 PM


Files produced by the author(s)




Alin Bostan, Claude-Pierre Jeannerod, Éric Schost. Solving structured linear systems with large displacement rank. Theoretical Computer Science, 2008, 407 (1-3), pp.155-181. ⟨10.1016/j.tcs.2008.05.014⟩. ⟨hal-03420733⟩



Record views


Files downloads