2026-07-21T12:58:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:778 2024-03-06T11:06:57Z ddc:004 open_access

Using fast matrix multiplication to solve structured linear systems Schost, Eric Bostan, Alin Jeannerod, Claude-Pierre Structured matrices matrix multiplication Hermite-Pade bivariate interpolation Structured linear algebra techniques are a versatile set of tools; they enable one to deal at once with various types of matrices, with features such as Toeplitz-, Hankel-, Vandermonde- or Cauchy-likeness. Following Kailath, Kung and Morf (1979), the usual way of measuring to what extent a matrix possesses one such structure is through its displacement rank, that is, the rank of its image through a suitable displacement operator. Then, for the families of matrices given above, the results of Bitmead-Anderson, Morf, Kaltofen, Gohberg-Olshevsky, Pan (among others) provide algorithm of complexity $O(alpha^2 n)$, up to logarithmic factors, where $n$ is the matrix size and $alpha$ its displacement rank. We show that for Toeplitz- Vandermonde-like matrices, this cost can be reduced to $O(alpha^(omega-1) n)$, where $omega$ is an exponent for linear algebra. We present consequences for Hermite-Pad'e approximation and bivariate interpolation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Schost and Alin Bostan and Claude-Pierre Jeannerod 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06271.16 urn:nbn:de:0030-drops-7787 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.16 eng https://creativecommons.org/licenses/by/4.0/legalcode