2 Search Results for "Jeannerod, Claude-Pierre"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.39
Faster Approximate Linear Matroid Intersection

Authors: Tatsuya Terao

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two r × n matrices M₁ and M₂, and the objective is to find a largest set of columns that are linearly independent in both M₁ and M₂. We design a (1 - ε)-approximation algorithm with time complexity Õ_{ε}(nnz(M₁) + nnz(M₂) + r_{*}^{ω}), where nnz(M_i) denotes the number of nonzero entries in M_i for i = 1, 2, r_{*} denotes the maximum size of a common independent set, and ω < 2.372 denotes the matrix multiplication exponent. Our approximation algorithm is faster than the exact algorithm by Harvey [FOCS'06 & SICOMP'09] and Cheung-Kwok-Lau [STOC'12 & JACM'13], which runs in Õ(nnz(M₁) + nnz(M₂) + n r_{*}^{ω - 1}) time. We also develop a fast (1 - ε)-approximation algorithm for the weighted version of the linear matroid intersection problem. In fact, we design a (1 - ε)-approximation algorithm for weighted linear matroid intersection with time complexity Õ_{ε}(nnz(M₁) + nnz(M₂) + r_{*}^{ω}). Our algorithm improves upon the (1 - ε)-approximation algorithm by Huang-Kakimura-Kamiyama [SODA'16 & Math. Program.'19], which runs in Õ_{ε}(nnz(M₁) + nnz(M₂) + nr_{*}^{ω - 1}) time. To obtain these results, we combine Quanrud’s adaptive sparsification framework [ICALP'24] with a simple yet effective method for efficiently checking whether a given vector lies in the linear span of a subset of vectors, which is of independent interest.
Cite as

Tatsuya Terao. Faster Approximate Linear Matroid Intersection. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{terao:LIPIcs.SWAT.2026.39,
  author =	{Terao, Tatsuya},
  title =	{{Faster Approximate Linear Matroid Intersection}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.39},
  URN =		{urn:nbn:de:0030-drops-260756},
  doi =		{10.4230/LIPIcs.SWAT.2026.39},
  annote =	{Keywords: Linear matroid intersection, fast approximation algorithm}
}
Document
DOI: 10.4230/DagSemProc.06271.16
Using fast matrix multiplication to solve structured linear systems

Authors: Eric Schost, Alin Bostan, and Claude-Pierre Jeannerod

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
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.
Cite as

Eric Schost, Alin Bostan, and Claude-Pierre Jeannerod. Using fast matrix multiplication to solve structured linear systems. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schost_et_al:DagSemProc.06271.16,
  author =	{Schost, Eric and Bostan, Alin and Jeannerod, Claude-Pierre},
  title =	{{Using fast matrix multiplication to solve structured linear systems}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.16},
  URN =		{urn:nbn:de:0030-drops-7787},
  doi =		{10.4230/DagSemProc.06271.16},
  annote =	{Keywords: Structured matrices, matrix multiplication, Hermite-Pade, bivariate interpolation}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2006

  • Refine by Author
  • 1 Bostan, Alin
  • 1 Jeannerod, Claude-Pierre
  • 1 Schost, Eric
  • 1 Terao, Tatsuya

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Mathematics of computing → Matroids and greedoids
  • 1 Theory of computation → Algorithm design techniques

  • Refine by Keyword
  • 1 Hermite-Pade
  • 1 Linear matroid intersection
  • 1 Structured matrices
  • 1 bivariate interpolation
  • 1 fast approximation algorithm
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact