Faster Approximate Linear Matroid Intersection

Terao, Tatsuya

doi:10.4230/LIPIcs.SWAT.2026.39

Faster Approximate Linear Matroid Intersection

Tatsuya Terao

Research Institute for Mathematical Sciences, Kyoto University, Japan

Abstract

We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two $r\times n$ matrices $M_{1}$ and $M_{2}$ , and the objective is to find a largest set of columns that are linearly independent in both $M_{1}$ and $M_{2}$ . We design a $(1-\varepsilon)$ -approximation algorithm with time complexity $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ , where $\mathrm{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 $\omega<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 $\tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+nr_{*}^{\omega-1})$ time.

We also develop a fast $(1-\varepsilon)$ -approximation algorithm for the weighted version of the linear matroid intersection problem. In fact, we design a $(1-\varepsilon)$ -approximation algorithm for weighted linear matroid intersection with time complexity $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ . Our algorithm improves upon the $(1-\varepsilon)$ -approximation algorithm by Huang–Kakimura–Kamiyama [SODA’16 & Math. Program.’19], which runs in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+nr_{*}^{\omega% -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.

Keywords and phrases:

Linear matroid intersection, fast approximation algorithm

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algorithm design techniques ; Mathematics of computing

\rightarrow

Matroids and greedoids

Related Version:

Full Version: https://arxiv.org/abs/2604.11725 [54]

Acknowledgements:

We thank Yusuke Kobayashi for his insightful comments, generous support, and valuable feedback on the manuscript. In particular, his input greatly helped us establish Lemma 11. We also thank Kou Hamada for helpful conversations that contributed to the initial motivation for this work. We are grateful to Takashi Noguchi for his helpful comments, which simplified the proof of Lemma 11. Finally, we thank the anonymous reviewers for their careful reading and valuable suggestions.

Funding:

This work was partially supported by the joint project of Kyoto University and Toyota Motor Corporation, titled “Advanced Mathematical Science for Mobility Society” and by JSPS KAKENHI Grant Number JP24KJ1494.

DOI:

10.4230/LIPIcs.SWAT.2026.39

Event:

20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Editor:

Pierre Fraigniaud

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Fast Algorithms for Linear Matroid Problems.

Matroids are combinatorial structures that abstract linear independence and provide a unifying framework capturing fundamental properties of matrices and graphs. We focus on fast algorithms for problems on linear matroids that are given explicitly as the columns of an $r\times n$ matrix $M$ over a field $\mathbb{F}$ .

Motivated by the view that running time should reflect not only the matrix dimensions $r\times n$ but also its sparsity, we design faster algorithms whose complexity depends on $\mathrm{nnz}(M)$ (the number of nonzero entries of $M$ ) in addition to $r$ and $n$ . In fact, many commonly studied matroids admit sparse linear representations. For example, it is well known that a graphic matroid can be represented by a vertex-edge incidence matrix with exactly two nonzero entries per edge, resulting in a total of $2m$ nonzero entries, where $m$ is the number of edges (see e.g., [47, Section 5.1]).

From this perspective, an important contribution is due to Cheung–Kwok–Lau [14], who developed a remarkable sketching technique and, as a result, presented a surprising algorithm for computing the rank of a matrix $M$ in $\tilde{O}(\mathrm{nnz}(M)+(\mathrm{rank}(M))^{\omega})$ time.¹¹1The $\tilde{O}$ notation omits polylog factors. Note that even checking whether a given subset of vectors is independent already requires $O((\mathrm{rank}(M))^{\omega})$ time, and reading the input takes $O(\mathrm{nnz}(M))$ time.

Nguy $\tilde{\hat{\text{e}}}$ n [44] presented an elegant algorithm for computing a maximum-weight base of a linear matroid represented by a matrix $M$ . While a direct application of the sketching technique of Cheung–Kwok–Lau would only yield a running time of $\tilde{O}\!\big(\mathrm{nnz}(M)+n\cdot(\mathrm{rank}(M))^{\omega-1}\big)$ , his refined use of this technique leads to $\big(\mathrm{nnz}(M)+(\mathrm{rank}(M))^{\omega}\big)^{1+o(1)}$ . This problem has also been studied, under the name column rank profile problem [19, 36, 52, 20], which asks for the lexicographically smallest sequence of $\mathrm{rank}(M)$ column indices such that the corresponding columns of the matrix are linearly independent. Dumas–Pernet–Sultan [20] achieved the same time complexity for the column rank profile problem.

Linear Matroid Intersection.

In this work, we consider fast approximation algorithms for linear matroid intersection. This linear matroid intersection problem can be described without relying on matroid terminology as follows: Given two $r\times n$ matrices $M_{1}$ and $M_{2}$ over a field $\mathbb{F}$ , where the columns in $M_{1}$ and $M_{2}$ are indexed by $\{1,\ldots,n\}$ , the objective is to find a set $I\subseteq\{1,\ldots,n\}$ of maximum size such that the columns indexed by $I$ are linearly independent in both $M_{1}$ and $M_{2}$ . Many important problems in combinatorial optimization, such as bipartite matching, rainbow spanning tree, arborescence, and spanning tree packing, can be viewed as special cases of linear matroid intersection.

For the linear matroid intersection problem, Cunningham [16] gave a combinatorial algorithm with time complexity $\tilde{O}(nr^{2})$ . Gabow–Xu [28, 29] proposed a faster combinatorial algorithm with time complexity $\tilde{O}(nrr_{*}^{1/(4-\omega)})=O(nrr_{*}^{0.62})$ , where $\omega$ is the exponent of matrix multiplication, known to satisfy $\omega<2.371339$ [3]. Here, $r_{*}$ denotes the maximum size of a common independent set. Harvey [33] developed an algebraic algorithm with time complexity $O(nr^{\omega-1})$ . Cheung–Kwok–Lau [14] combined their elegant sketching technique with Harvey’s algorithm [33], obtaining an algorithm with running time $\tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+nr_{*}^{\omega-1})$ . In fact, simply applying their sketching technique reduces an $r\times n$ input matrix to an $O(r_{*})\times n$ matrix while preserving linear dependence among the columns.

Given the progress on the case of a single matroid [14, 20, 44], it is natural to ask whether linear matroid intersection can be solved in $\tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ time. Note that even checking whether a given subset is independent in a single matroid already requires $O(r_{*}^{\omega})$ time, and reading the input takes $O(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2}))$ time. Avoiding the dependence on $n$ is most meaningful when $r_{*}\ll n$ , a regime that arises naturally, for example, for graphic matroids. However, achieving a running time of $\tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ seems quite challenging. To achieve such a running time, one must avoid explicitly computing the product of an $O(r_{*})\times n$ matrix and an $n\times O(r_{*})$ matrix, which would already take $O(nr_{*}^{\omega-1})$ time. Here, it is well known that $M_{1}$ and $M_{2}$ have a common base if and only if $\det(M_{1}DM_{2}^{\top})\neq 0$ , where $D$ is a diagonal matrix with variables on the diagonal $D_{i,i}=x_{i}$ (see for e.g., [31, Lemma 2.5]). Using this matrix formulation, a standard approach to the decision version of linear matroid intersection, i.e., deciding whether a common base exists, requires computing the product of an $O(r_{*})\times n$ matrix and an $n\times O(r_{*})$ matrix. Hence, to our knowledge, no prior result has shown that the time complexity for merely estimating the size of a maximum common independent set can be faster than that of Cheung–Kwok–Lau.

Our Result for Maximum Cardinality Linear Matroid Intersection.

Our main result is to develop a $(1-\varepsilon)$ -approximation algorithm for linear matroid intersection running in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ time.²²2The $\tilde{O}_{\varepsilon}$ notation omits polylog factors and polynomial factors in $\varepsilon^{-1}$ . We note that our algorithm is applicable over any field.

Theorem 1.

For any $\varepsilon>0$ , a $(1-\varepsilon)$ -approximate solution to the maximum cardinality linear matroid intersection problem can be computed with high probability³³3We say “with high probability” if the failure probability is at most $n^{-\Theta(1)}$ . in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ time.

Our approximation algorithm in Theorem 1 is faster than the exact algorithm obtained by combining Harvey’s algorithm [33] with the sketching technique of Cheung–Kwok–Lau [14], which runs in $\tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+nr_{*}^{\omega-1})$ time. Even when $M_{1}$ and $M_{2}$ are dense and $r_{*}=\Theta(r)$ , our approximation algorithm achieves a running time of $\tilde{O}_{\varepsilon}(nr+r^{\omega})$ , which is faster than the $O(nr^{\omega-1})$ time required by Harvey’s exact algorithm [33]. Surprisingly, our complexity is almost the same as that of computing the rank of a matrix [14], and also that of finding a maximum-weight base of a single linear matroid [20, 44].

Weighted Linear Matroid Intersection.

We also consider the weighted version of the linear matroid intersection problem. In this problem, we are given two $r\times n$ matrices $M_{1}$ and $M_{2}$ over a field $\mathbb{F}$ , whose columns are indexed by $\{1,\ldots,n\}$ , and a weight function $c:\{1,\ldots,n\}\to\mathbb{R}_{\geq 0}$ . The objective is to find a set $I\subseteq\{1,\ldots,n\}$ such that the columns indexed by $I$ are linearly independent in both $M_{1}$ and $M_{2}$ , and the total weight $\sum_{e\in I}c(e)$ is maximized. Gabow–Xu [28, 29] gave a combinatorial algorithm with time complexity $\tilde{O}(nr^{\frac{7-\omega}{5-\omega}}\log(nC))=\tilde{O}(nr^{1.77}\log(nC))$ , where $C$ is the largest given weight. Harvey [32] proposed an algebraic algorithm with time complexity $\tilde{O}(C^{1+o(1)}nr^{\omega-1})$ . Huang–Kakimura–Kamiyama [35] presented a $(1-\varepsilon)$ -approximation algorithm with time complexity $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+nr_{*}^{\omega% -1})$ , where $r_{*}$ is the maximum size of a common independent set.

Our Result for Maximum Weight Linear Matroid Intersection.

Using a similar idea to that used to obtain Theorem 1, we also develop a $(1-\varepsilon)$ -approximation algorithm for weighted linear matroid intersection running in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ time. We note that our algorithm is applicable over any field.

Theorem 2.

For any $\varepsilon>0$ , a $(1-\varepsilon)$ -approximate solution to the weighted linear matroid intersection problem can be computed with high probability in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ time.

Our algorithm in Theorem 2 improves upon the $(1-\varepsilon)$ -approximation weighted linear matroid intersection algorithm by Huang–Kakimura–Kamiyama [35], which runs in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+nr_{*}^{\omega% -1})$ time.

1.1 Technical Overview

Adaptive Sparsification Framework of Quanrud [48].

Our linear matroid intersection algorithm builds upon the adaptive sparsification framework of Quanrud [48], which was developed to obtain a fast $(1-\varepsilon)$ -approximation algorithm for matroid intersection in the oracle model. However, we emphasize that a direct application of Quanrud’s framework does not yield the running time achieved by our algorithm.

In Quanrud’s framework, the original problem over $n$ elements is reduced to $O(\log(n)/\varepsilon)$ primal-dual instances of matroid intersection, each over $\tilde{O}_{\varepsilon}(r_{*})$ elements, where $r_{*}$ is the maximum size of a common independent set. For linear matroid intersection, computing primal and dual solutions to sparsified instances can be done straightforwardly using Harvey’s exact algorithm for linear matroid intersection [33]. Applied to the sparsified instance of size $\tilde{O}_{\varepsilon}(r_{*})$ , Harvey’s algorithm runs in $\tilde{O}_{\varepsilon}(r_{*}^{\omega})$ time, which is sufficiently fast. To adaptively construct sparsified instances, it is necessary to compute $\mathrm{span}_{\mathcal{M}_{1}}(\tilde{S})$ and $\mathrm{span}_{\mathcal{M}_{2}}(\tilde{T})$ , where $(\tilde{S},\tilde{T})$ denotes a dual solution to the sparsified instance. For linear matroids, a straightforward method can compute the spans in $O(nr_{*}^{\omega-1})$ time, but this is still too slow for our purpose.

Challenge in Computing a Span.

Without using matroid terminology, our task is as follows: Given an $r\times n$ matrix $M$ and a subset $S\subseteq[n]$ , determine whether each column vector $\boldsymbol{m}_{i}$ lies in the linear span of the set $\{\boldsymbol{m}_{j}\mid j\in S\}$ , where $\boldsymbol{m}_{1},\ldots,\boldsymbol{m}_{n}$ denote the vectors corresponding to the columns of $M$ . We present a simple randomized algorithm that solves this task in $\tilde{O}(\mathrm{nnz}(M)+r^{\omega})$ time, which is of independent interest.

In the oracle model, where an algorithm accesses a matroid $\mathcal{M}$ through an independence oracle, the span

\mathrm{span}_{\mathcal{M}}(S)=\{v\in V\mid{\rm rank}_{\mathcal{M}}(S\cup\{v\}% )={\rm rank}_{\mathcal{M}}(S)\}

of a set $S$ can be computed naively using a linear number of queries. However, when the matroid is given via a matrix representation, the standard approaches are too inefficient for our purpose. Naively, each independence query takes $O(r^{\omega})$ time, and thus the most straightforward implementation requires $O(nr^{\omega})$ time. The standard Gaussian elimination approach takes $O(nr^{2})$ time to compute the span. Using the fact that the linear representation of $\mathcal{M}/S$ , the matroid obtained by contracting $\mathcal{M}$ by $S$ , can be computed in $O(nr^{\omega-1})$ time (see [33, Fact 4.1]), we can reduce the time complexity to $O(nr^{\omega-1})$ . However, this complexity is still inefficient for obtaining a linear matroid intersection algorithm that outperforms the best known exact algorithm. To compute the span faster than $O(nr^{\omega-1})$ time, one must avoid computing the product of an $r\times n$ matrix and an $n\times r$ matrix, which is a challenging task.

To overcome this difficulty, our fast span computation algorithm shares a similar spirit with the famous Freivalds’ algorithm [24] (see e.g., [42, Section 7.1]) for verifying matrix multiplication without actually performing the multiplication. In our approach, we sample a vector $\boldsymbol{v}$ from the orthogonal complement of $\mathrm{span}\{\boldsymbol{m}_{j}\mid j\in S\}$ , which can be computed in $\tilde{O}(\mathrm{nnz}(M)+r^{\omega})$ time. Then, for each column vector $\boldsymbol{m}_{i}$ , we check whether $\boldsymbol{v}^{\top}\boldsymbol{m}_{i}=0$ . It is obvious that if $\boldsymbol{m}_{i}\in\mathrm{span}\{\boldsymbol{m}_{j}\mid j\in S\}$ , then $\boldsymbol{v}^{\top}\boldsymbol{m}_{i}=0$ always holds. Furthermore, we can show that if $\boldsymbol{m}_{i}\notin\mathrm{span}\{\boldsymbol{m}_{j}\mid j\in S\}$ , then $\boldsymbol{v}^{\top}\boldsymbol{m}_{i}\neq 0$ with high probability. The total time required to compute all inner products $\boldsymbol{v}^{\top}\boldsymbol{m}_{i}$ for all $i\in[n]$ is $O(\mathrm{nnz}(M))$ . Therefore, the total running time of our span computation algorithm is $\tilde{O}(\mathrm{nnz}(M)+r^{\omega})$ , which is efficient enough to enable the design of a linear matroid intersection algorithm that outperforms the best known exact algorithm.

Challenge for Weighted Linear Matroid Intersection.

For weighted linear matroid intersection, a naive combination of the adaptive sparsification framework of Quanrud [48] and our fast span computation algorithm yields a $(1-\varepsilon)$ -approximation algorithm with time complexity $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega+% 1})$ . This additional factor arises because, in the weighted setting, we need to test membership in $\operatorname{span}_{\mathcal{M}}(S)$ not for a single candidate set $S$ , but for $O(r_{*})$ different candidates. To improve the running time to $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ , we carefully employ the fast Gram–Schmidt orthonormalization algorithm of van den Brand [57]. Concretely, we use van den Brand’s algorithm to compute, for each set in the support of the dual solution in the weighted setting, a basis for the corresponding subspace as well as a basis for its orthogonal complement.

When considering matrices over the real field $\mathbb{R}$ , the idea of employing the fast Gram– Schmidt orthonormalization algorithm of van den Brand works correctly in conjunction with the techniques described above. However, over an arbitrary field $\mathbb{F}$ , the argument may fail. This is because, when considering matrices over a field other than $\mathbb{R}$ , it may happen that a linear subspace $W$ satisfies $W\cap W^{\perp}\neq\{\boldsymbol{0}\}$ and $W+W^{\perp}\neq\mathbb{F}^{r}$ ,⁴⁴4For example, consider $W=\mathrm{span}\{(1,1,0,0)^{\top},(0,0,1,1)^{\top}\}$ over the binary field $\mathrm{GF}(2)$ . Then, $W^{\perp}=\mathrm{span}\{(1,1,0,0)^{\top},(0,0,1,1)^{\top}\}$ . In this case, neither $W\cap W^{\perp}=\{\boldsymbol{0}\}$ nor $W+W^{\perp}=(\mathrm{GF}(2))^{4}$ holds. where $W^{\perp}$ is the orthogonal complement of $W$ (i.e., $W^{\perp}=\{\boldsymbol{v}\in\mathbb{F}^{r}\mid\forall\boldsymbol{w}\in W,% \boldsymbol{v}^{\top}\boldsymbol{w}=0\}$ ). This issue matters in our setting because we need to maintain bases for subspaces corresponding to many different sets, and for this purpose, our algorithm relies on the property that $W\cap W^{\perp}=\{\boldsymbol{0}\}$ and $W\oplus W^{\perp}=\mathbb{F}^{r}$ .

To design an algorithm applicable to any field, we replace the Euclidean inner product $\boldsymbol{v}^{\top}\boldsymbol{w}$ with the bilinear form $\langle\boldsymbol{v},\boldsymbol{w}\rangle=\boldsymbol{v}^{\top}B\boldsymbol{w}$ , where we choose $w_{1},\ldots,w_{r}$ independently and uniformly at random from $\mathbb{F}$ , and define a diagonal $r\times r$ matrix $B$ such that $B_{i,i}=w_{i}$ . Here, we define the orthogonal complement with respect to the bilinear form $\langle\boldsymbol{v},\boldsymbol{w}\rangle=\boldsymbol{v}^{\top}B\boldsymbol{w}$ as $W^{\perp}_{B}=\{\boldsymbol{v}\in\mathbb{F}^{r}\mid\forall\boldsymbol{w}\in W,% \langle\boldsymbol{v},\boldsymbol{w}\rangle=\boldsymbol{v}^{\top}B\boldsymbol{% w}=0\}$ . For a fixed linear subspace $W$ , we can show that both $W\cap W^{\perp}_{B}=\{\boldsymbol{0}\}$ and $W\oplus W^{\perp}_{B}=\mathbb{F}^{r}$ hold with high probability.

To determine whether $\boldsymbol{m}_{i}\in\mathrm{span}\{\boldsymbol{m}_{j}\mid j\in S\}$ , it suffices to check whether $\langle\boldsymbol{v},\boldsymbol{m}_{i}\rangle=\boldsymbol{v}^{\top}B% \boldsymbol{m}_{i}=0$ . Here, $\boldsymbol{v}$ is a vector sampled from the orthogonal complement of $\mathrm{span}\{\boldsymbol{m}_{j}\mid j\in S\}$ with respect to the bilinear form $\langle\boldsymbol{v},\boldsymbol{w}\rangle=\boldsymbol{v}^{\top}B\boldsymbol{w}$ . We make use of a fast orthogonalization algorithm with respect to the bilinear form $\langle\boldsymbol{v},\boldsymbol{w}\rangle=\boldsymbol{v}^{\top}B\boldsymbol{w}$ , which is a modified version of the fast Gram–Schmidt orthonormalization algorithm of van den Brand [57].

1.2 Related Work

Faster Matroid Intersection under Oracle Models.

In addition to the linear matroid model, another standard model for handling matroids is the oracle model. In this model, an algorithm accesses a matroid through an oracle that answers queries about its structure. In recent years, the development of faster algorithms for matroid intersection under oracle models has attracted significant attention. Starting the work of Edmonds [21, 22], many fast algorithms in the oracle model have been studied [2, 55, 38, 16, 25, 51, 39, 13, 35, 45, 12, 9, 6, 56, 7, 48, 53, 8, 18]. There have also been many studies on fast matroid intersection algorithms for several important specific classes of matroids [27, 26, 16, 28, 29, 59, 32, 33, 35]. Recently, Blikstad–Mukhopadhyay–Nanongkai–Tu [7] proposed a remarkable new oracle model, called dynamic oracle, which unifies various results on fast matroid intersection algorithms for specific classes of matroids; see [7, Table 2].

Note that the recent dynamic oracle framework of Blikstad–Mukhopadhyay–Nanongkai–Tu [7] yields a linear matroid intersection algorithm with time complexity $O(n^{2.5925}\sqrt{r_{*}})$ , using the dynamic matrix rank maintenance algorithm of [58]. However, this complexity is slower than that of Harvey [33].

Additional Related Work.

There are several studies on fast algebraic algorithms for problems that generalize linear matroid intersection, such as linear matroid parity [15], fractional linear matroid parity [46], and linear delta-matroid parity [37]. Matoya–Oki [41] derandomized Harvey’s [33] linear matroid intersection algorithm for a special case known as a Pfaffian pair. Linear matroid intersection has also been well studied in parallel and other computational models [43, 31, 30, 1]. The intersection of multiple linear matroids has also attracted interest in the parameterized algorithm community; see, for example, [17, Section 12.3] and [5, 40, 10, 23].

Concurrent Work.

Independent of our work, Dudeja–Grilnberger [18] presented a remarkable reduction in the independence oracle model that converts any $(1-\varepsilon)$ -approximation algorithm for unweighted matroid intersection into a $(1-\varepsilon)$ -approximation algorithm for weighted matroid intersection, while increasing the running time by only a factor of $\log C$ , where $C$ denotes the aspect ratio. Thus, one might hope that, when combined with our unweighted result in Theorem 1, their reduction could yield a weighted result comparable to Theorem 2. However, their reduction relies on several subroutines, including a procedure for greedily computing a common independent set, and it is unclear whether all of these subroutines can be implemented efficiently for linear matroids. Accordingly, it is unclear whether their reduction, combined with Theorem 1, can yield a result comparable to Theorem 2.

2 Preliminaries

2.1 Basic Notation

The set $\{1,\ldots,n\}$ is denoted by $[n]$ . If $U$ is a set, then $\binom{U}{k}$ denotes the set of all its subsets of size $k$ .

Consider a matrix $M$ over a field $\mathbb{F}$ . Let $\mathrm{nnz}(M)$ denote the number of nonzero entries in $M$ . Let $M[S]$ denote the submatrix consisting of columns indexed by $S$ . Let $M[R,C]$ denote the submatrix consisting of the rows indexed by $R$ and the columns indexed by $C$ . Let $[A\mid B]$ denote the matrix whose columns consist of those of $A$ , followed by those of $B$ . We write $I$ to denote the identity matrix. Let $\mathrm{span}\{\boldsymbol{v}_{1},\ldots,\boldsymbol{v}_{k}\}$ denote the linear span of the set of vectors $\{\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{k}\}$ .

2.2 Assumptions and Conventions

When $\mathbb{F}$ is a finite field, we can assume that $|\mathbb{F}|=\Omega(\mathrm{poly}(n))$ by the following well-known lemma. As a result of this assumption, the running time of our algorithm increases by a multiplicative factor of $\mathrm{polylog}(n)$ .

Lemma 3 (from [14, Lemma 2.1]).

Let $A$ be an $r\times n$ matrix over a field $\mathbb{F}$ with $p^{c}$ elements. We can construct a finite field $\mathbb{F}^{\prime}$ with $p^{ck}=\Omega(\mathrm{poly}(n))$ elements and an injective mapping $f\colon\mathbb{F}\to\mathbb{F}^{\prime}$ so that the image of $\mathbb{F}$ is a subfield of $\mathbb{F}^{\prime}$ . Then, the $r\times n$ matrix $A^{\prime}$ where $A^{\prime}_{ij}=f(A_{ij})$ satisfies the following property: a set of columns of $A$ is independent if and only if the corresponding set of columns of $A^{\prime}$ is independent. This preprocessing step takes $O(\mathrm{nnz}(A))$ time. Each field operation in $\mathbb{F}^{\prime}$ can be performed using $\mathrm{polylog}(n)$ field operations in $\mathbb{F}$ .

When $\mathbb{F}$ is an infinite field, we assume the exact arithmetic model where each field operation is performed in one unit of time. In the algorithm, we also require the ability to sample a random element from an arbitrary subset of size $\Omega(\mathrm{poly}(n))$ in $\mathbb{F}$ . This assumption is needed for the application of the Schwartz–Zippel Lemma.⁵⁵5The Schwartz–Zippel Lemma is used in Harvey’s exact algorithm for linear matroid intersection [33] and in the sketching technique of Cheung–Kwok–Lau [14], both of which are components of our algorithm.

Lemma 4 (Schwartz–Zippel Lemma [50]).

Let $P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ be a nonzero polynomial of total degree $d$ over a field $\mathbb{F}$ . Let $S$ be a finite subset of $\mathbb{F}$ and let $r_{1},\ldots,r_{n}$ be chosen independently and uniformly at random from $S$ . Then, the probability that $P(r_{1},\ldots,r_{n})=0$ is at most $d/|S|$ .

We assume that two $n\times n$ matrices can be multiplied in $O(n^{\omega})$ time. The current best upper bound on $\omega$ is $\omega<2.371339$ [3]. For an $n\times n$ matrix, it is known that computing the determinant, rank, and inverse can all be done in the same time complexity as one matrix multiplication [11, 34].

The assumptions in this subsection were also made in [14, 44].

2.3 Matroid Preliminaries

For the basics of matroid theory, see, for example, the excellent textbooks of Oxley [47] or Schrijiver [49].

A pair $\mathcal{M}=(V,\mathcal{I})$ of a finite set $V$ and a non-empty set family $\mathcal{I}\subseteq 2^{V}$ is called a matroid if the following properties are satisfied.

(Downward closure property): If $I\in\mathcal{I}$ and $J\subseteq I$ , then $J\in\mathcal{I}$ .
(Augmentation property): If $I,J\in\mathcal{I}$ and $|J|<|I|$ , then there exists $v\in I\setminus J$ such that $J\cup\{v\}\in\mathcal{I}$ .

A set $I\subseteq V$ is called independent if $I\in\mathcal{I}$ and dependent otherwise.

Matroid Rank and Span.

Motivated by linear algebra, matroids have associated notions of a rank function and a span function, defined as follows. For a matroid $\mathcal{M}=(V,\mathcal{I})$ , the rank of $\mathcal{M}$ is ${\rm rank}(\mathcal{M})=\max\{|I|\mid I\in\mathcal{I}\}$ . In addition, for any $S\subseteq V$ , the rank of $S$ is ${\rm rank}_{\mathcal{M}}(S)=\max\{|I|\mid I\subseteq S,I\in\mathcal{I}\}$ . Moreover, for any $S\subseteq V$ , the span of $S$ is ${\rm span}_{\mathcal{M}}(S)=\{v\in V\mid{\rm rank}_{\mathcal{M}}(S\cup\{v\})={% \rm rank}_{\mathcal{M}}(S)\}$ .

Matroid Intersection.

In the matroid intersection problem, we are given two matroids $\mathcal{M}_{1}=(V,\mathcal{I}_{1})$ and $\mathcal{M}_{2}=(V,\mathcal{I}_{2})$ , and the objective is to find a common independent set $I\in\mathcal{I}_{1}\cap\mathcal{I}_{2}$ of maximum size.

Edmonds [21] proved the following min-max theorem, which is now well known.

Theorem 5 (Matroid intersection theorem [21]; see also [49, Theorem 41.1]).

Let $\mathcal{M}_{1}=(V,\mathcal{I}_{1})$ , $\mathcal{M}_{2}=(V,\mathcal{I}_{2})$ be matroids, with rank function $\mathrm{rank}_{\mathcal{M}_{1}}$ and $\mathrm{rank}_{\mathcal{M}_{2}}$ , respectively. Then,

\max_{I\in\mathcal{I}_{1}\cap\mathcal{I}_{2}}|I|=\min_{S,T\subseteq V,S\cup T=% V}(\mathrm{rank}_{\mathcal{M}_{1}}(S)+\mathrm{rank}_{\mathcal{M}_{2}}(T)).

Here, $(S,T)$ is called a dual solution to matroid intersection, where $S$ and $T$ minimize the right-hand side of the equation in Theorem 5.

In our linear matroid intersection algorithm, we use Harvey’s exact algorithm for linear matroid intersection [33] to compute primal and dual solutions to sparsified instances.

Theorem 6 (Harvey’s exact linear matroid intersection algorithm; see [33, Section 4.6]).

An exact solution to the maximum cardinality linear matroid intersection problem can be computed with high probability in $\tilde{O}(nr^{\omega-1})$ time. Furthermore, an exact dual solution can also be computed with high probability in $\tilde{O}(nr^{\omega-1})$ time.

2.4 Sketching Technique of Cheung–Kwok–Lau

In our algorithm, we use the sketching technique of Cheung–Kwok–Lau [14]. Using this technique, we can reduce the dimension of the input matrix from $r\times n$ to $O(r_{*})\times n$ .

Lemma 7 (Sketching technique of Cheung–Kwok–Lau [14]; from [14, Lemma 2.9]).

There is an algorithm that, given an $r\times n$ matrix $A$ over a field $\mathbb{F}$ , returns an $O(k)\times n$ matrix $A^{\prime}$ over a field $\mathbb{F}$ in $O(\mathrm{nnz}(A))$ time, with $\mathrm{nnz}(A^{\prime})=O(\mathrm{nnz}(A))$ , such that for any set $S\subseteq[n]$ of size at most $k$ , if the columns indexed by $S$ are linearly independent in $A$ , then the columns of $A^{\prime}$ indexed by $S$ are also linearly independent with probability at least $1-O(1/n^{1/3})$ .

In our fast span computation algorithm, we use the following lemma.

Lemma 8 (Fast computation of a basis of the orthogonal complement of the column space).

There is a randomized algorithm that, given an $r\times n$ matrix $M$ over a field $\mathbb{F}$ , finds a basis of the orthogonal complement of the column space of $M$ with high probability in $O((\mathrm{nnz}(M)+r^{\omega})\log n)$ time.

Lemma 8 can be easily derived from the following lemma, which was obtained using the sketching technique of Cheung–Kwok–Lau. Here, the null space of a matrix $A$ is the subspace of vectors $\boldsymbol{x}$ such that $A\boldsymbol{x}=\boldsymbol{0}$ .

Lemma 9 (from [14, Theorem 1.3(2)]; see also [14, Section 4.1.2]).

There is a randomized algorithm that, given an $m\times n$ matrix $A$ over a field $\mathbb{F}$ , finds a basis of the null space of $A$ with high probability in $O((\mathrm{nnz}(A)+n(\mathrm{rank}(A))^{\omega-1})\log n)$ time.

Let $W$ denote the column space of an $r\times n$ matrix $M$ , i.e., $W=\mathrm{span}\{\boldsymbol{m}_{1},\ldots,\boldsymbol{m}_{n}\}$ , where $\boldsymbol{m}_{1},\ldots,\boldsymbol{m}_{n}$ are the column vectors of $M$ . The orthogonal complement of $W$ , denoted by $W^{\perp}$ , is defined as $W^{\perp}=\{\boldsymbol{x}\in\mathbb{F}^{r}\mid\forall\boldsymbol{w}\in W,% \boldsymbol{w}^{\top}\boldsymbol{x}=0\}$ . Now, $\boldsymbol{x}\in W^{\perp}$ if and only if $\boldsymbol{m}_{i}^{\top}\boldsymbol{x}=0$ for any $i\in[n]$ . We have $W^{\perp}=\{\boldsymbol{x}\in\mathbb{F}^{r}\mid M^{\top}\boldsymbol{x}=% \boldsymbol{0}\}$ . Therefore, to find a basis of the orthogonal complement of the column space of $M$ , we simply compute a basis of the null space of $M^{\top}$ using Lemma 9. Note that $M^{\top}$ is an $n\times r$ matrix. Hence, Lemma 8 follows from Lemma 9.

2.5 Fast Gram–Schmidt Orthonormalization

For our maximum weight linear matroid intersection algorithm for matrices over $\mathbb{R}$ , we use the fast Gram–Schmidt orthonormalization algorithm of van den Brand [57].

Lemma 10 (Fast Gram–Schmidt orthonormalization; from van den Brand [57, Section 4.5]).

Given an $r\times n$ matrix $M$ with $r\leq n$ over $\mathbb{R}$ , where $\boldsymbol{m}_{1},\ldots,\boldsymbol{m}_{n}$ are column vectors of $M$ , there is an algorithm that repeatedly computes $\boldsymbol{m}^{\prime}_{i}=\boldsymbol{m}_{i}-P_{i-1}\boldsymbol{m}_{i}$ , where $P_{i-1}\boldsymbol{m}_{i}$ denotes the orthogonal projection of $\boldsymbol{m}_{i}$ onto $\mathrm{span}\{\boldsymbol{m}_{1},\ldots,\boldsymbol{m}_{i-1}\}$ , and then normalizes $\boldsymbol{m}^{\prime}_{i}$ if $\boldsymbol{m}^{\prime}_{i}\neq\boldsymbol{0}$ . The total running time of this process is $O(n^{\omega})$ .

To extend our algorithm to arbitrary fields, we modify a fast Gram–Schmidt orthonormalization algorithm of van den Brand into a fast orthogonalization algorithm with respect to the bilinear form $\langle\boldsymbol{v},\boldsymbol{w}\rangle=\boldsymbol{v}^{\top}B\boldsymbol{w}$ ; see the full version [54] for details.

3 Fast Span Computation Algorithm

As part of our technical contribution, we develop a fast span computation algorithm, which is used as a subroutine in our maximum cardinality linear matroid intersection algorithm. The following lemma states its running time guarantee.

Lemma 11.

There is a randomized algorithm that, given an $r\times n$ matrix $M$ over a field $\mathbb{F}$ whose columns are the representation of elements of a matroid $\mathcal{M}$ , and a set $S\subseteq[n]$ ,⁶⁶6Although in our application the size of $S$ is always $\tilde{O}_{\varepsilon}(r)$ , we state the lemma in a general form for potential broader applicability., computes $\mathrm{span}_{\mathcal{M}}(S)$ with high probability in $\tilde{O}(\mathrm{nnz}(M)+r^{\omega})$ time.

We note that our algorithm is applicable over any field.

The core idea of our algorithm is very simple. In our algorithm, we first sample a vector $\boldsymbol{v}$ from the orthogonal complement of $\mathrm{span}\{\boldsymbol{m}_{j}\mid j\in S\}$ , where $\boldsymbol{m}_{1},\ldots,\boldsymbol{m}_{n}$ denote the vectors corresponding to the columns of the input matrix $M$ . Then, we output the set $\{i\in[n]\mid\boldsymbol{v}^{\top}\boldsymbol{m}_{i}=0\}$ as $\mathrm{span}_{\mathcal{M}}(S)$ . See Algorithm 1 for the pseudocode of our algorithm.

Let $W=\mathrm{span}\{\boldsymbol{m}_{j}\mid j\in S\}$ . The orthogonal complement of $W$ , denoted by $W^{\perp}$ , is defined as $W^{\perp}=\{\boldsymbol{v}\in\mathbb{F}^{r}\mid\forall\boldsymbol{w}\in W,% \boldsymbol{v}^{\top}\boldsymbol{w}=0\}$ . When considering matrices over a field other than $\mathbb{R}$ , it may occur that $W$ does not satisfy $W\cap W^{\perp}=\{\boldsymbol{0}\}$ or $W+W^{\perp}=\mathbb{F}^{r}$ . Nevertheless, for our purpose it suffices that $(W^{\perp})^{\perp}=W$ , which in fact holds over any field.⁷⁷7This can be verified by a simple argument in linear algebra. Now, fix any $\boldsymbol{x}\in W$ . For any $\boldsymbol{y}\in W^{\perp}$ , we have $\boldsymbol{y}^{\top}\boldsymbol{x}=0$ . Thus, $\boldsymbol{x}\in(W^{\perp})^{\perp}$ , and hence $W\subseteq(W^{\perp})^{\perp}$ . Moreover, the Rank–nullity theorem implies that $\dim(W^{\perp})=r-\dim(W)$ and $\dim((W^{\perp})^{\perp})=r-\dim(W^{\perp})$ . Therefore, $\dim((W^{\perp})^{\perp})=\dim(W)$ , which, together with $W\subseteq(W^{\perp})^{\perp}$ , yields $(W^{\perp})^{\perp}=W$ .

Note that we assume $|\mathbb{F}|=\Omega(\mathrm{poly}(n))$ . Recall that, by Lemma 3, this assumption can be made without loss of generality.

Algorithm 1 Span computation algorithm.

Proof.

In our algorithm, we first compute a basis $\{\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{k}\}$ of the orthogonal complement of $\mathrm{span}\{\boldsymbol{m}_{j}\mid j\in S\}$ by applying Lemma 8 to $M[S]$ . This step takes $O((\mathrm{nnz}(M)+r^{\omega})\log n)$ time.

Next, we choose $r_{1},\ldots,r_{k}$ independently and uniformly at random from a finite subset $F\subseteq\mathbb{F}$ with $|F|=\Theta(n^{2})$ , and compute

\boldsymbol{v}=\sum_{j=1}^{k}r_{j}\boldsymbol{b}_{j},

which takes $O(r^{2})$ time, since $k\leq r$ and each $\boldsymbol{b}_{j}$ is an $r$ -dimensional vector.

We claim that the value of $\boldsymbol{v}^{\top}\boldsymbol{m}_{i}$ satisfies the following two properties. Here, $\boldsymbol{m_{1}},\ldots,\boldsymbol{m_{n}}$ denote the vectors corresponding to the columns of the matrix $M$ .

$\blacksquare$

If $i\in\mathrm{span}_{\mathcal{M}}(S)$ , then we have $\boldsymbol{v}^{\top}\boldsymbol{m}_{i}=0$ for every possible choice of $r_{1},\ldots,r_{k}$ , since $\boldsymbol{v}$ lies in the orthogonal complement of $\mathrm{span}\{\boldsymbol{m}_{j}\mid j\in S\}$ .
$\blacksquare$

If $i\notin\mathrm{span}_{\mathcal{M}}(S)$ , then we have $\boldsymbol{v}^{\top}\boldsymbol{m}_{i}\neq 0$ with probability at least $1-1/|F|$ . This can be shown as follows. Consider the multivariate polynomial

$P(x_{1},\ldots,x_{k})=\sum_{j=1}^{k}x_{j}\boldsymbol{b}_{j}^{\top}\boldsymbol{% m}_{i}.$

Here, to show that $P(x_{1},\ldots,x_{k})$ is a nonzero polynomial, we prove the following claim.⁸⁸8Over the real number field $\mathbb{R}$ , the claim is immediate. However, over an arbitrary field $\mathbb{F}$ , one cannot in general rely on $W\cap W^{\perp}=\{\boldsymbol{0}\}$ or $W+W^{\perp}=\mathbb{F}^{r}$ , so some care is required. For completeness, we give a careful proof, which uses only the identity $(W^{\perp})^{\perp}=W$ . Recall that we are assuming $i\notin\mathrm{span}_{\mathcal{M}}(S)$ .

Claim 12.

There exists some $j\in[k]$ such that $\boldsymbol{b}_{j}^{\top}\boldsymbol{m}_{i}\neq 0$ .

Proof of Claim 12.

Let $W=\operatorname{span}\{\boldsymbol{m}_{j}\mid j\in S\}$ . Here, we have $\boldsymbol{m}_{i}\notin W$ . Suppose, for the sake of contradiction, that $\boldsymbol{b}_{j}^{\top}\boldsymbol{m}_{i}=0$ for all $j\in[k]$ , where $\{\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{k}\}$ form a basis of $W^{\perp}$ . Then, $\boldsymbol{m}_{i}$ is orthogonal to every vector in $W^{\perp}$ , which implies that $\boldsymbol{m}_{i}\in(W^{\perp})^{\perp}=W$ , contradicting the assumption $\boldsymbol{m}_{i}\notin W$ . Therefore, there exists some $j\in[k]$ such that $\boldsymbol{b}_{j}^{\top}\boldsymbol{m}_{i}\neq 0$ , which completes the proof. $\hfill\vartriangleleft$ By Claim 12, $P(x_{1},\ldots,x_{k})$ is a nonzero polynomial of total degree $1$ . Since $r_{1},\ldots,r_{k}$ are chosen independently and uniformly at random from a finite subset $F\subseteq\mathbb{F}$ , by the Schwartz–Zippel Lemma (Lemma 4), the probability that

$P(r_{1},\ldots,r_{k})=\sum_{j=1}^{k}r_{j}\boldsymbol{b}_{j}^{\top}\boldsymbol{% m}_{i}=\boldsymbol{v}^{\top}\boldsymbol{m}_{i}=0$

is at most $1/|F|$ .

Then, we only need to check, for each $i\in[n]$ , whether $\boldsymbol{v}^{\top}\boldsymbol{m}_{i}=0$ . The total time required to compute all inner products $\boldsymbol{v}^{\top}\boldsymbol{m}_{i}$ for all $i\in[n]$ is $O(\mathrm{nnz}(M))$ . Finally, we output the set $\{i\in[n]\mid\boldsymbol{v}^{\top}\boldsymbol{m}_{i}=0\}$ as $\mathrm{span}_{\mathcal{M}}(S)$ .

There are at most $n$ operations that check whether $i\in\mathrm{span}_{\mathcal{M}}(S)$ , and each fails with probability at most $1/|F|$ . Therefore, the probability that at least one of them fails is at most $n/|F|=O(1/n)$ , where we recall that $|F|=\Theta(n^{2})$ .

In summary, we can compute $\mathrm{span}_{\mathcal{M}}(S)$ with high probability in $O((\mathrm{nnz}(M)+r^{\omega})\log n)$ time. $\hfill\blacktriangleleft$

4 Adaptive Sparsification Framework of Quanrud

In this section, we describe the adaptive sparsification framework of Quanrud [48], which was developed to obtain a fast $(1-\varepsilon)$ -approximation algorithm for matroid intersection in the independence oracle model. Our linear matroid intersection algorithm builds upon this framework.

Quanrud’s framework employs a multiplicative weight update method, inspired by Assadi’s semi-streaming maximum matching algorithm [4]. In this framework, we maintain a weight for each element and repeat the following $O(\log(n)/\varepsilon)$ iterations: In each iteration, we sample $\Theta(\min\{k\log(n)/\varepsilon,n\})$ elements, in proportion to their weight, compute primal and dual solutions over the sampled elements, and then update the weights of elements. In Quanrud’s paper, $k$ is set to $r_{*}$ , where $r_{*}$ denote the maximum size of a common independent set.⁹⁹9When we apply Quanrud’s framework to linear matroid intersection, we set $k=r$ instead of $k=r_{*}$ .

4.1 Maximum Cardinality Matroid Intersection

In this subsection, we describe Quanrud’s framework for maximum cardinality matroid intersection. The pseudocode is shown in Algorithm 2.

Algorithm 2 Quanrud’s maximum cardinality matroid intersection algorithm in the independence oracle model (from [48, Figure 1]).

We maintain a weight function $w:V\to\mathbb{R}_{\geq 0}$ over the elements, where all elements initially have equal weights. We then repeat the following process for $L=O(\log(n)/\varepsilon)$ iterations: In each iteration, we first sample $\tilde{O}(k/\varepsilon)$ elements $V^{\prime}\subseteq V$ in proportion to $w$ . Then, we compute a maximum common independent set $I$ and a dual solution $(\tilde{S},\tilde{T})$ for the subproblem over $V^{\prime}$ .¹⁰¹⁰10In Quanrud’s paper, a $(1-\varepsilon)$ -approximate solution is computed in Line 4 of Algorithm 2. However, when applying Quanrud’s framework to linear matroid intersection, we compute an exact solution. It is clear that this does not affect the correctness. Note that $\tilde{S},\tilde{T}\subseteq V^{\prime}$ . We extend these sets to their spans, setting $S=\mathrm{span}_{\mathcal{M}_{1}}(\tilde{S})$ and $T=\mathrm{span}_{\mathcal{M}_{2}}(\tilde{T})$ . Finally, we update the weights $w$ by setting $w(e)\leftarrow w(e)/2$ for all elements $e\in S\cup T$ . After $L$ iterations, we output $I$ with the largest cardinality among all iterations.

When applying Quanrud’s framework to linear matroid intersection, we use Harvey’s linear matroid intersection algorithm (Theorem 6) to implement Line 4 of Algorithm 2, and our fast span computation algorithm presented in Section 3 to implement Line 5. See Section 5.1 for details.

4.2 Maximum Weight Matroid Intersection

In this subsection, we describe Quanrud’s framework for maximum weight matroid intersection. The high-level approach in the weighted case is similar to that in the unweighted case, but requires additional technical sophistication. The pseudocode is shown in Algorithm 3.

Algorithm 3 Quanrud’s maximum weight matroid intersection algorithm in the independence oracle model (from [48, Figure 2]).

Here, we refer to a solution $(y,z)$ , where $y,z:2^{V}\to\mathbb{R}_{\geq 0}$ , of the following LP as a dual solution. This LP is the dual of the LP relaxation of the weighted matroid intersection problem.

	$\displaystyle\mathrm{minimize}$	$\displaystyle\,\,\sum_{S\subseteq V}\left(\mathrm{rank}_{\mathcal{M}_{1}}(S)y(% S)+\mathrm{rank}_{\mathcal{M}_{2}}(S)z(S)\right)\quad\mathrm{over}\,\,\,y,z:2^% {V}\to\mathbb{R}_{\geq 0}$		(1)
	$\displaystyle\mathrm{s.t.}$	$\displaystyle\,\,\sum_{S\ni e}(y(S)+z(S))\geq c(e)\quad\mathrm{for}\,\,\mathrm% {all}\,\,e\in V$		(1)

Quanrud defines $(y,z)$ to be compact if the supports of $y$ and $z$ satisfy the following conditions:

	$\displaystyle\mathrm{support}(y)\subseteq$	$\displaystyle\{\mathrm{span}_{\mathcal{M}_{1}}(\{e_{1}\}),\mathrm{span}_{% \mathcal{M}_{1}}(\{e_{1},e_{2}\}),\ldots,\mathrm{span}_{\mathcal{M}_{1}}(\{e_{% 1},\ldots,e_{k}\})\},$
	$\displaystyle\mathrm{support}(z)\subseteq$	$\displaystyle\{\mathrm{span}_{\mathcal{M}_{2}}(\{f_{1}\}),\mathrm{span}_{% \mathcal{M}_{2}}(\{f_{1},f_{2}\}),\ldots,\mathrm{span}_{\mathcal{M}_{2}}(\{f_{% 1},\ldots,f_{k}\})\}.$

Here, $e_{1},\ldots,e_{k}\in V$ and $f_{1},\ldots,f_{k}\in V$ are two sequences of $k$ elements.

As in the unweighted case, we maintain a weight function $w:V\to\mathbb{R}_{\geq 0}$ with initially equal weights, and repeat the following process for $L=O(\log(n)/\varepsilon)$ iterations: In each iteration, we first sample $\tilde{O}(k/\varepsilon)$ elements $V^{\prime}\subseteq V$ in proportion to $w$ . Then, we compute a $(1-\varepsilon)$ -approximate maximum-weight common independent set $I$ and a compact $(1-\varepsilon)$ -approximate dual solution $\tilde{y},\tilde{z}:2^{V^{\prime}}\to\mathbb{R}_{\geq 0}$ for the subproblem over $V^{\prime}$ . We then construct $y,z:2^{V}\to\mathbb{R}_{\geq 0}$ from $\tilde{y},\tilde{z}$ by setting

	$\displaystyle y(\mathrm{span}_{\mathcal{M}_{1}}(S^{\prime}))$	$\displaystyle=\lceil\tilde{y}(S^{\prime})\rceil_{1+\varepsilon}\quad\quad\text% {for all }S^{\prime}\in\mathrm{support}(\tilde{y}),$
	$\displaystyle z(\mathrm{span}_{\mathcal{M}_{2}}(T^{\prime}))$	$\displaystyle=\lceil\tilde{z}(T^{\prime})\rceil_{1+\varepsilon}\quad\quad\text% {for all }T^{\prime}\in\mathrm{support}(\tilde{z}).$

We set $y(F)=0$ (resp. $z(F)=0$ ) for any $F\in 2^{V}$ not of the form $\mathrm{span}_{\mathcal{M}_{1}}(S^{\prime})$ with $S^{\prime}\in\mathrm{support}(\tilde{y})$ (resp. $\mathrm{span}_{\mathcal{M}_{2}}(T^{\prime})$ with $T^{\prime}\in\mathrm{support}(\tilde{z})$ ). Here, $\lceil x\rceil_{1+\varepsilon}$ = $(1+\varepsilon)^{\lceil\log_{1+\varepsilon}x\rceil}$ denote rounding $x$ up to the nearest power of $1+\varepsilon$ . Since $(y^{\prime},z^{\prime})$ is compact, there exists a sequence $e_{1},\ldots,e_{k}$ such that every set in the support of $y^{\prime}$ has the form $S^{\prime}_{i}=(\mathrm{span}_{\mathcal{M}_{1}}(\{e_{1},\ldots,e_{i}\}))\cap V% ^{\prime}$ . Then, every set in the support of $y$ has the form $S_{i}=\mathrm{span}_{\mathcal{M}_{1}}(S^{\prime}_{i})=\mathrm{span}_{\mathcal{% M}_{1}}(\{e_{1},\ldots,e_{i}\})$ . Symmetrically, the same property holds for $z$ , with a different sequence of $k$ elements determined by $z^{\prime}$ . Thus, $(y,z)$ is also compact. Finally, we update the weights $w$ by setting $w(e)\leftarrow w(e)/2$ for all elements $e\in V$ such that $\sum_{S\ni e}(y(S)+z(S))\geq c(e)$ holds. After $L$ iterations, we output $I$ that maximizes $c(I)$ over all iterations.

When applying Quanrud’s framework to maximum weight linear matroid intersection, we use the $(1-\varepsilon)$ -approximate weighted linear matroid intersection algorithm by Huang–Kakimura–Kamiyama [35] to implement Line 4 of Algorithm 3. To implement Line 6, we combine our fast span computation algorithm presented in Section 3 with the fast Gram–Schmidt orthonormalization algorithm of van den Brand [57] (Lemma 10). See Section 5.2 for details.

5 Linear Matroid Intersection Algorithms

In this section, we prove Theorems 1 and 2 by combining the sparsification framework of Quanrud [48] (see Section 4 for details) with our fast span computation algorithm presented in Section 3.

When we apply Quanrud’s framework to linear matroid intersection, we set $k=r$ instead of $k=r_{*}$ . In the proofs of Theorems 1 and 2, we apply Quanrud’s framework to matrices that have been suitably preprocessed using the sketching technique of Cheung–Kwok–Lau [14] (Lemma 7). For the preprocessed matrices, the maximum size of a common independent set is within a constant factor of the number of rows, which justifies setting $k=r$ .¹¹¹¹11Actually, sampling $\Theta(\min\{r\log(n)/\varepsilon,n\})$ elements, instead of $\Theta(\min\{r_{*}\log(n)/\varepsilon,n\})$ , in each iteration does not affect the correctness of Quanrud’s framework. This is because the approximation guarantee relies on Lemma 9 (and Lemma 13 in the weighted case) in Quanrud’s paper [48], which states that sampling $\Omega(\min\{r_{*}\log(n)/\varepsilon,n\})$ elements is sufficient.

5.1 Maximum Cardinality Linear Matroid Intersection

We first show the following theorem, and then prove Theorem 1 using this theorem.

Theorem 13.

For any $\varepsilon>0$ , a $(1-\varepsilon)$ -approximate solution to the maximum cardinality linear matroid intersection problem can be computed with high probability in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r^{\omega})$ time.

Proof.

We show that, when the matroids are given by matrix representations, Quanrud’s maximum cardinality matroid intersection algorithm (Algorithm 2) can be implemented in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r^{\omega})$ time. By using Harvey’s exact algorithm for linear matroid intersection (Theorem 6), Line 4 can be implemented in $\tilde{O}_{\varepsilon}(r^{\omega})$ time, since the number of elements in the sparsified set is $\tilde{O}_{\varepsilon}(r)$ . By applying Lemma 11, Line 5 can be implemented in $\tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r^{\omega})$ time. Furthermore, Lines 3 and 6 can be implemented in $\tilde{O}_{\varepsilon}(n)$ time. Since the number of iterations of the for loop is $O(\log(n)/\varepsilon)$ , the total running time is the desired bound of $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r^{\omega})$ , which completes the proof. $\hfill\blacktriangleleft$

Following the approach of [14, Section 4.3.2], we can improve the running time to $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ , which proves Theorem 1.

Proof of Theorem 1.

We assume without loss of generality that $\varepsilon<1/2$ .

Given an integer $\ell$ , we consider the task of finding a set $I^{\prime}\subseteq[n]$ of size at least $\min\{(1-\varepsilon)\ell,(1-\varepsilon)\cdot r_{*}\}$ such that the columns indexed by $I^{\prime}$ are linearly independent in both $M_{1}$ and $M_{2}$ . Using Lemma 7 with $k=\ell$ , we compress the input matrices $M_{1}$ and $M_{2}$ into $O(\ell)\times n$ matrices $M_{1}^{\prime}$ and $M_{2}^{\prime}$ , in $O(\mathrm{nnz}(M_{1}))$ and $O(\mathrm{nnz}(M_{2}))$ time, respectively. We have $\mathrm{nnz}(M_{1}^{\prime})=O(\mathrm{nnz}(M_{1}))$ and $\mathrm{nnz}(M_{2}^{\prime})=O(\mathrm{nnz}(M_{2}))$ . Furthermore, for any set $S\subseteq[n]$ of size at most $\ell$ , if the columns indexed by $S$ are linearly independent in both $M_{1}$ and $M_{2}$ , then the columns indexed by $S$ are also linearly independent in both $M_{1}^{\prime}$ and $M_{2}^{\prime}$ with probability at least $1-O(1/n^{1/3})$ . Consequently, the maximum size of a common independent set for $M^{\prime}_{1}$ and $M^{\prime}_{2}$ is $\min\{\ell,r_{*}\}$ with high probability. Then, we apply the algorithm in Theorem 13 to find a $(1-\varepsilon)$ -approximate solution to the linear matroid intersection problem on $M_{1}^{\prime}$ and $M_{2}^{\prime}$ , which runs in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1}^{\prime})+\mathrm{nnz}(M_{2}^{% \prime})+\ell^{\omega})=\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{% nnz}(M_{2})+\ell^{\omega})$ time.

To find a solution of size at least $(1-\varepsilon)\cdot r_{*}$ , we set $\ell=2,4,8,\ldots$ and apply the above algorithm until there is no solution of size $\ell/2$ . The total running time of this algorithm is $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ , which completes the proof. $\hfill\blacktriangleleft$

5.2 Maximum Weight Linear Matroid Intersection

We first show the following theorem, and then prove Theorem 2 using this theorem.

Theorem 14.

For any $\varepsilon>0$ , a $(1-\varepsilon)$ -approximate solution to the maximum weight linear matroid intersection problem can be computed with high probability in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r^{\omega})$ time.

In Quanrud’s framework, we need to compute a $(1-\varepsilon)$ -approximate maximum-weight common independent set and a compact $(1+\varepsilon)$ -approximate dual solution for the sparsified instances. When implementing Quanrud’s framework for linear matroids, we use the following lemma to compute compact primal-dual solutions. This lemma is obtained by combining the $(1-\varepsilon)$ -approximation algorithm for the weighted matroid intersection by Huang–Kakimura–Kamiyama [35] with the argument of Quanrud’s paper [48]. See the full version [54] for the proof of Lemma 15.

Lemma 15.

Given two $r\times n$ matrix $M_{1}$ and $M_{2}$ over a field $\mathbb{F}$ , and a weight function $c:[n]\to\mathbb{R}_{\geq 0}$ , there is an algorithm that computes a $(1-\varepsilon)$ -approximate maximum-weight common independent set $I$ , along with a compact $(1+\varepsilon)$ -approximate dual solution $y,z:2^{[n]}\to\mathbb{R}_{\geq 0}$ , with high probability in $\tilde{O}_{\varepsilon}(nr^{\omega-1})$ time.

To efficiently implement Line 6 of Algorithm 3, we present the following lemma. This lemma is obtained by combining our fast span computation algorithm described in Section 3 with the fast Gram–Schmidt orthonormalization algorithm of van den Brand (Lemma 10).

Lemma 16.

Let $M$ be an $r\times n$ matrix over a field $\mathbb{F}$ , and let $\{i_{1},\ldots,i_{r}\}\subseteq[n]$ be a set of indices. Here, $\boldsymbol{m}_{1},\ldots,\boldsymbol{m}_{n}$ denote the vectors corresponding to the columns of $M$ . Then, there is an algorithm that answers the following query: given $j\in[n]$ and $\alpha\in[r]$ , determine whether $\boldsymbol{m}_{j}\in\mathrm{span}\{\boldsymbol{m}_{i_{\beta}}\mid\beta\leq\alpha\}$ with high probability in $O(\mathrm{nnz}(\boldsymbol{m}_{j}))$ time. This algorithm requires $O(r^{\omega})$ time for preprocessing.

Here, we provide a proof only for matrices over $\mathbb{R}$ . The extension to matrices over an arbitrary field is deferred to the full version [54]. To make the algorithm applicable over arbitrary fields, the key modification is to replace the Euclidean inner product $\boldsymbol{v}^{\top}\boldsymbol{w}$ with the bilinear form $\langle\boldsymbol{v},\boldsymbol{w}\rangle=\boldsymbol{v}^{\top}B\boldsymbol{w}$ (see the full version [54] for details).

Proof of Lemma 16 for matrices over $\mathbb{R}$ .

We first describe the preprocessing algorithm. First, we apply the fast Gram–Schmidt orthonormalization algorithm of van den Brand [57] (Lemma 10) to the sequence of $2r$ vectors $\boldsymbol{m}_{i_{1}},\ldots,\boldsymbol{m}_{i_{r}},\boldsymbol{e}_{1},\ldots% ,\boldsymbol{e}_{r}$ , which takes $O(r^{\omega})$ time. Here, $\boldsymbol{e}_{i}\in\mathbb{R}^{r}$ is the standard basis vector (i.e., the vector with $1$ in the $i$ -th coordinate and $0$ elsewhere). Then, we obtain a vector sequence $\boldsymbol{m}^{\prime}_{i_{1}},\ldots,\boldsymbol{m}^{\prime}_{i_{r}},% \boldsymbol{e}^{\prime}_{1},\ldots,\boldsymbol{e}^{\prime}_{r}$ . We note that this vector sequence includes the zero vector $\boldsymbol{0}$ . We then choose $q_{1},\ldots,q_{2r}$ independently and uniformly at random from a finite subset $R\subset\mathbb{R}$ of size $\mathrm{poly}(n)$ (e.g., $R=\{1,2,\ldots,\text{poly}(n)\}$ ). Next, for each $\alpha\in[r]$ , we compute a vector $\displaystyle\boldsymbol{v}_{\alpha}=\sum_{j=\alpha+1}^{r}q_{j}\boldsymbol{m}^% {\prime}_{i_{j}}+\sum_{j=1}^{r}q_{r+j}\boldsymbol{e}^{\prime}_{j}$ . This can be implemented in $O(r^{2})$ time by computing the sums in reverse order. We note that $\boldsymbol{v}_{\alpha}$ lies in the orthogonal complement of $\mathrm{span}\{\boldsymbol{m}_{i_{1}},\ldots,\boldsymbol{m}_{i_{\alpha}}\}$ .

Next, we describe how to answer the query. It suffices to check whether $\boldsymbol{v}_{\alpha}^{\top}\boldsymbol{m}_{j}=0$ , which can be done in $O(\mathrm{nnz}(\boldsymbol{m}_{j}))$ time. As in the proof of Lemma 11, if $\boldsymbol{m}_{j}\in\mathrm{span}\{\boldsymbol{m}_{i_{\beta}}\mid\beta\leq\alpha\}$ holds, then $\boldsymbol{v}_{\alpha}^{\top}\boldsymbol{m}_{j}=0$ always holds, otherwise $\boldsymbol{v}_{\alpha}^{\top}\boldsymbol{m}_{j}\neq 0$ holds with probability at least $1-1/|R|=1-1/\text{poly}(n)$ . Therefore, checking whether $\boldsymbol{v}_{\alpha}^{\top}\boldsymbol{m}_{j}=0$ suffices to decide whether $\boldsymbol{m}_{j}\in\mathrm{span}\{\boldsymbol{m}_{i_{\beta}}\mid\beta\leq\alpha\}$ , which completes the proof. $\hfill\blacktriangleleft$

We now present the proof of Theorem 14.

Proof of Theorem 14.

We show that, when the matroids are given by matrix representations, Quanrud’s maximum weight matroid intersection algorithm (Algorithm 3) can be implemented in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r^{\omega})$ time. By Lemma 15, Line 4 can be implemented in $\tilde{O}_{\varepsilon}(r^{\omega})$ time, since the number of elements in the sparsified set is $\tilde{O}_{\varepsilon}(r)$ .

In our algorithm, we do not explicitly compute $(y,z)$ computed in Line 5. Here, $(y,z)$ computed in Line 5 is compact, and thus we can write

	$\displaystyle\mathrm{support}(y)\subseteq$	$\displaystyle\{\mathrm{span}_{\mathcal{M}_{1}}(\{i_{1}\}),\mathrm{span}_{% \mathcal{M}_{1}}(\{i_{1},i_{2}\}),\ldots,\mathrm{span}_{\mathcal{M}_{1}}(\{i_{% 1},\ldots,i_{r}\})\},$		(2)
	$\displaystyle\mathrm{support}(z)\subseteq$	$\displaystyle\{\mathrm{span}_{\mathcal{M}_{2}}(\{j_{1}\}),\mathrm{span}_{% \mathcal{M}_{2}}(\{j_{1},j_{2}\}),\ldots,\mathrm{span}_{\mathcal{M}_{2}}(\{j_{% 1},\ldots,j_{r}\})\},$		(2)

for two sequences of $r$ elements $i_{1},\ldots,i_{r}\in[n]$ and $j_{1},\ldots,j_{r}\in[n]$ . Here, let $\mathcal{M}_{1}$ (resp. $\mathcal{M}_{2}$ ) denote the matroid represented by the matrix $M_{1}$ (resp. $M_{2}$ ). The elements $i_{1},\ldots,i_{r}$ and $j_{1},\ldots,j_{r}$ belong to the sparsified set, and are computed in Line 4. To implement Line 5, we simply compute the value of $y(\mathrm{span}_{\mathcal{M}_{1}}(\{i_{1},\ldots,i_{\alpha}\}))$ and $z(\mathrm{span}_{\mathcal{M}_{2}}(\{j_{1},\ldots,j_{\alpha}\}))$ for each $\alpha\in[r]$ , which takes $O(r)$ time. Note that we do not explicitly compute $\mathrm{span}_{\mathcal{M}_{1}}(\{i_{1},\ldots,i_{\alpha}\})$ or $\mathrm{span}_{\mathcal{M}_{2}}(\{j_{1},\ldots,j_{\alpha}\})$ .

It remains to bound the running time of Line 6. In this line, for each $i\in[n]$ , we need to check whether $\displaystyle\sum_{S\ni i}(y(S)+z(S))\geq c(i)$ . Here, $\boldsymbol{m}^{(1)}_{1},\ldots,\boldsymbol{m}^{(1)}_{n}$ (resp. $\boldsymbol{m}^{(2)}_{1},\ldots,\boldsymbol{m}^{(2)}_{n}$ ) denote the vectors corresponding to the columns of $M_{1}$ (resp. $M_{2}$ ). As preprocessing, for all $\alpha\in[r]$ , we compute
$\displaystyle y_{\alpha}=\sum_{\gamma\in\{\alpha,\alpha+1,\ldots,r\}}y(\mathrm% {span}_{\mathcal{M}_{1}}(\{i_{1},\ldots,i_{\gamma}\})),\quad z_{\alpha}=\sum_{% \gamma\in\{\alpha,\alpha+1,\ldots,r\}}z(\mathrm{span}_{\mathcal{M}_{2}}(\{j_{1% },\ldots,j_{\gamma}\})),$

which takes $O(r)$ time. Furthermore, we apply the preprocessing algorithm of Lemma 16 to $M_{1}$ and $\{i_{1},\ldots,i_{r}\}$ , which takes $O(r^{\omega})$ time; we do the same for $M_{2}$ and $\{j_{1},\ldots,j_{r}\}$ .

We now describe how to check whether $\displaystyle\sum_{S\ni i}(y(S)+z(S))\geq c(i)$ holds for each $i\in[n]$ in $\tilde{O}(\mathrm{nnz}(\boldsymbol{m}^{(1)}_{i})+\mathrm{nnz}(\boldsymbol{m}^{% (2)}_{i}))$ time. We can binary search for the first index $\alpha^{(1)}\in[r]$ (resp. $\alpha^{(2)}\in[r]$ ) such that $\boldsymbol{m}^{(1)}_{i}\in\mathrm{span}\{\boldsymbol{m}^{(1)}_{i_{\beta}}\mid% \beta\leq\alpha^{(1)}\}$ (resp. $\boldsymbol{m}^{(2)}_{i}\in\mathrm{span}\{\boldsymbol{m}^{(2)}_{j_{\beta}}\mid% \beta\leq\alpha^{(2)}\}$ ). Note that, for all $\gamma\geq\alpha^{(1)}$ , we have $\boldsymbol{m}^{(1)}_{i}\in\mathrm{span}\{\boldsymbol{m}^{(1)}_{i_{\beta}}\mid% \beta\leq\gamma\}$ . By Lemma 16, this binary search process takes $\tilde{O}(\mathrm{nnz}(\boldsymbol{m}^{(1)}_{i})+\mathrm{nnz}(\boldsymbol{m}^{% (2)}_{i}))$ time. Here, we have $\displaystyle\sum_{S\ni i}(y(S)+z(S))=y_{\alpha^{(1)}}+z_{\alpha^{(2)}}$ , so this value can be computed in $O(1)$ time. Thus, for each $i\in[n]$ , we can check whether $\displaystyle\sum_{S\ni i}\left(y(S)+z(S)\right)\geq c(i)$ in $\tilde{O}(\mathrm{nnz}(\boldsymbol{m}^{(1)}_{i})+\mathrm{nnz}(\boldsymbol{m}^{% (2)}_{i}))$ time. Therefore, Line 6 can be implemented in $\tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r^{\omega})$ time, which completes the proof. $\hfill\blacktriangleleft$

Using the sketching technique of Cheung–Kwok–Lau [14] (Lemma 7), we can improve the running time to $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ , which proves Theorem 2.

Proof of Theorem 2.

As a first step, we compute a $2/3$ -approximate solution $\bar{S_{*}}$ to the maximum cardinality linear matroid intersection for the input matrices $M_{1}$ and $M_{2}$ , using Theorem 1, in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega})$ time. We then apply Lemma 7 with $k=\frac{3}{2}|\bar{S_{*}}|$ . Note that $k\geq r_{*}$ and $k=\Theta(r_{*})$ . The lemma compresses the input matrices $M_{1}$ and $M_{2}$ into $O(r_{*})\times n$ matrices $M_{1}^{\prime}$ and $M_{2}^{\prime}$ , in $O(\mathrm{nnz}(M_{1}))$ and $O(\mathrm{nnz}(M_{2}))$ time, respectively. We have $\mathrm{nnz}(M_{1}^{\prime})=O(\mathrm{nnz}(M_{1}))$ and $\mathrm{nnz}(M_{2}^{\prime})=O(\mathrm{nnz}(M_{2}))$ . Furthermore, for any set $S\subseteq[n]$ of size at most $r_{*}$ , if the columns indexed by $S$ are linearly independent in both $M_{1}$ and $M_{2}$ , then the columns indexed by $S$ are also linearly independent in both $M_{1}^{\prime}$ and $M_{2}^{\prime}$ with probability at least $1-O(1/n^{1/3})$ . We then apply the algorithm in Theorem 14 to the compressed matrices $M_{1}^{\prime}$ and $M_{2}^{\prime}$ to find a $(1-\varepsilon)$ -approximate solution to the maximum weight linear matroid intersection problem. This algorithm runs in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1}^{\prime})+\mathrm{nnz}(M_{2}^{% \prime})+r_{*}^{\omega})=\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{% nnz}(M_{2})+r_{*}^{\omega})$ time. $\hfill\blacktriangleleft$

References

[1] Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra. Linear matroid intersection is in catalytic logspace. In Proceedings of the 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362, pages 3:1–3:23, 2026. doi:10.4230/LIPIcs.ITCS.2026.3.
[2] Martin Aigner and Thomas A Dowling. Matching theory for combinatorial geometries. Transactions of the American Mathematical Society, 158(1):231–245, 1971. doi:10.1090/S0002-9947-1971-0286689-5.
[3] Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 2005–2039. SIAM, 2025. doi:10.1137/1.9781611978322.63.
[4] Sepehr Assadi. A simple $(1-\varepsilon)$ -approximation semi-streaming algorithm for maximum (weighted) matching. TheoretiCS, 4, 2025. Preliminary version in SOSA 2024. doi:10.46298/theoretics.25.16.
[5] Alexander I Barvinok. New algorithms for linear $k$ -matroid intersection and matroid $k$ -parity problems. Mathematical Programming, 69(1):449–470, 1995. doi:10.1007/BF01585571.
[6] Joakim Blikstad. Breaking $O(nr)$ for matroid intersection. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 198, pages 31:1–31:17, 2021. doi:10.4230/LIPIcs.ICALP.2021.31.
[7] Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, and Ta-Wei Tu. Fast algorithms via dynamic-oracle matroids. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pages 1229–1242, 2023. doi:10.1145/3564246.3585219.
[8] Joakim Blikstad and Ta-Wei Tu. Efficient matroid intersection via a batch-update auction algorithm. In Proceedings of the 8th Symposium on Simplicity in Algorithms (SOSA 2025), pages 226–237. SIAM, 2025. doi:10.1137/1.9781611978315.18.
[9] Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, and Danupon Nanongkai. Breaking the quadratic barrier for matroid intersection. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), pages 421–432, 2021. doi:10.1145/3406325.3451092.
[10] Cornelius Brand and Kevin Pratt. Parameterized applications of symbolic differentiation of (totally) multilinear polynomials. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 38:1–38:19, 2021. doi:10.4230/LIPIcs.ICALP.2021.38.
[11] James R Bunch and John E Hopcroft. Triangular factorization and inversion by fast matrix multiplication. Mathematics of Computation, 28(125):231–236, 1974.
[12] Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, and Sam Chiu-wai Wong. Faster matroid intersection. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 1146–1168. IEEE, 2019. doi:10.1109/FOCS.2019.00072.
[13] Chandra Chekuri and Kent Quanrud. A fast approximation for maximum weight matroid intersection. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pages 445–457. SIAM, 2016. doi:10.1137/1.9781611974331.ch33.
[14] Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. Fast matrix rank algorithms and applications. Journal of the ACM (JACM), 60(5):1–25, 2013. Preliminary version in STOC 2012. doi:10.1145/2528404.
[15] Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung. Algebraic algorithms for linear matroid parity problems. ACM Transactions on Algorithms (TALG), 10(3):1–26, 2014. Preliminary version in SODA 2011. doi:10.1145/2601066.
[16] William H Cunningham. Improved bounds for matroid partition and intersection algorithms. SIAM Journal on Computing, 15(4):948–957, 1986. doi:10.1137/0215066.
[17] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[18] Aditi Dudeja and Mara Grilnberger. A weighted-to-unweighted reduction for matroid intersection. arXiv preprint arXiv:2602.15702, 2026. doi:10.48550/arXiv.2602.15702.
[19] Jean-Guillaume Dumas, Clément Pernet, and Ziad Sultan. Simultaneous computation of the row and column rank profiles. In Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (ISSAC 2013), pages 181–188, 2013. doi:10.1145/2465506.2465517.
[20] Jean-Guillaume Dumas, Clément Pernet, and Ziad Sultan. Fast computation of the rank profile matrix and the generalized bruhat decomposition. Journal of Symbolic Computation, 83:187–210, 2017. doi:10.1016/j.jsc.2016.11.011.
[21] Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and Their Applications, pages 69–87, 1970.
[22] Jack Edmonds. Matroid intersection. In Annals of Discrete Mathematics, volume 4, pages 39–49. Elsevier, 1979. doi:10.1016/S0167-5060(08)70817-3.
[23] Eduard Eiben, Tomohiro Koana, and Magnus Wahlström. Determinantal sieving. TheoretiCS, 4, 2025. Preliminary version in SODA 2024. doi:10.46298/theoretics.25.21.
[24] Rūsiņš Freivalds. Fast probabilistic algorithms. In Proceedings of the 8th International Symposium on Mathematical Foundations of Computer Science (MFCS 1979), pages 57–69. Springer, 1979.
[25] Satoru Fujishige and Zhang Xiaodong. An efficient cost scaling algorithm for the independent assignment problem. Journal of the Operations Research Society of Japan, 38(1):124–136, 1995.
[26] Harold N Gabow and Matthias Stallmann. Efficient algorithms for graphic matroid intersection and parity. In Proceedings of the 12th Colloquium on Automata, Languages and Programming (ICALP 1985), pages 210–220. Springer, 1985. doi:10.1007/BFb0015746.
[27] Harold N Gabow and Robert E Tarjan. Efficient algorithms for simple matroid intersection problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FOCS 1979), pages 196–204. IEEE, 1979. doi:10.1109/SFCS.1979.14.
[28] Harold N Gabow and Ying Xu. Efficient algorithms for independent assignment on graphic and linear matroids. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), pages 106–111. IEEE Computer Society, 1989. doi:10.1109/SFCS.1989.63463.
[29] Harold N Gabow and Ying Xu. Efficient theoretic and practical algorithms for linear matroid intersection problems. Journal of Computer and System Sciences, 53(1):129–147, 1996. doi:10.1006/jcss.1996.0054.
[30] Rohit Gurjar, Taihei Oki, and Roshan Raj. Fractional linear matroid matching is in Quasi-NC. In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024), volume 308, pages 63:1–63:14, 2024. doi:10.4230/LIPIcs.ESA.2024.63.
[31] Rohit Gurjar and Thomas Thierauf. Linear matroid intersection is in Quasi-NC. computational complexity, 29(2):9, 2020. Preliminary version in STOC 2017. doi:10.1007/s00037-020-00200-z.
[32] Nicholas JA Harvey. An algebraic algorithm for weighted linear matroid intersection. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pages 444–453, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283430.
[33] Nicholas JA Harvey. Algebraic algorithms for matching and matroid problems. SIAM Journal on Computing, 39(2):679–702, 2009. Preliminary version in FOCS 2006. doi:10.1137/070684008.
[34] Nicholas James Alexander Harvey. Matchings, matroids and submodular functions. PhD thesis, Massachusetts Institute of Technology, 2008.
[35] Chien-Chung Huang, Naonori Kakimura, and Naoyuki Kamiyama. Exact and approximation algorithms for weighted matroid intersection. Mathematical Programming, 177(1-2):85–112, 2019. Preliminary version in SODA 2016. doi:10.1007/s10107-018-1260-x.
[36] Claude-Pierre Jeannerod, Clément Pernet, and Arne Storjohann. Rank-profile revealing gaussian elimination and the cup matrix decomposition. Journal of Symbolic Computation, 56:46–68, 2013. doi:10.1016/j.jsc.2013.04.004.
[37] Tomohiro Koana and Magnus Wahlström. Faster algorithms on linear delta-matroids. In Proceedings of 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), volume 327, pages 62:1–62:19, 2025. doi:10.4230/LIPIcs.STACS.2025.62.
[38] Eugene L Lawler. Matroid intersection algorithms. Mathematical Programming, 9(1):31–56, 1975. doi:10.1007/BF01681329.
[39] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), pages 1049–1065. IEEE, 2015. doi:10.1109/FOCS.2015.68.
[40] Dániel Marx. A parameterized view on matroid optimization problems. Theoretical Computer Science, 410(44):4471–4479, 2009. Preliminary version in ICALP 2006. doi:10.1016/j.tcs.2009.07.027.
[41] Kazuki Matoya and Taihei Oki. Pfaffian pairs and parities: Counting on linear matroid intersection and parity problems. SIAM Journal on Discrete Mathematics, 36(3):2121–2158, 2022. Preliminary version in IPCO 2021. doi:10.1137/21m1421751.
[42] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. doi:10.1017/cbo9780511814075.
[43] Harihar Narayanan, Huzur Saran, and Vijay V Vazirani. Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjoint spanning trees. SIAM Journal on Computing, 23(2):387–397, 1994. Preliminary version in SODA 1992. doi:10.1137/S0097539791195245.
[44] Huy L Nguyen. Fast greedy for linear matroids. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 516–524. SIAM, 2019. doi:10.1137/1.9781611975482.32.
[45] Huy L Nguyen. A note on Cunningham’s algorithm for matroid intersection. arXiv preprint arXiv:1904.04129, 2019. doi:10.48550/arXiv.1904.04129.
[46] Taihei Oki and Tasuku Soma. Algebraic algorithms for fractional linear matroid parity via noncommutative rank. SIAM Journal on Computing, 54(1):134–162, 2025. Preliminary version in SODA 2023. doi:10.1137/22m1537096.
[47] James G Oxley. Matroid theory, volume 3. Oxford University Press, USA, 2006.
[48] Kent Quanrud. Adaptive sparsification for matroid intersection. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297, pages 118:1–118:20, 2024. doi:10.4230/LIPIcs.ICALP.2024.118.
[49] Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
[50] Jacob T Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM (JACM), 27(4):701–717, 1980. doi:10.1145/322217.322225.
[51] Maiko Shigeno and Satoru Iwata. A dual approximation approach to weighted matroid intersection. Operations Research Letters, 18(3):153–156, 1995. doi:10.1016/0167-6377(95)00047-X.
[52] Arne Storjohann and Shiyun Yang. Linear independence oracles and applications to rectangular and low rank linear systems. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pages 381–388, 2014. doi:10.1145/2608628.2608673.
[53] Tatsuya Terao. Deterministic $(2/3-\varepsilon)$ -approximation of matroid intersection using nearly-linear independence-oracle queries. In Proceedings of the 19th International Symposium on Algorithms and Data Structures (WADS 2025), volume 349, pages 50:1–50:18, 2025. doi:10.4230/LIPIcs.WADS.2025.50.
[54] Tatsuya Terao. Faster approximate linear matroid intersection. arXiv preprint arXiv:2604.11725, 2026. doi:10.48550/arXiv.2604.11725.
[55] Nobuaki Tomizawa and Masao Iri. An algorithm for determining the rank of a triple matrix product AXB with application to the problem of discerning the existence of the unique solution in a network. Electronics and Communications in Japan (Scripta Electronica Japonica II), 57(11):50–57, 1974.
[56] Ta-Wei Tu. Subquadratic weighted matroid intersection under rank oracles. In Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248, pages 63:1–63:14, 2022. doi:10.4230/LIPIcs.ISAAC.2022.63.
[57] Jan van den Brand. Unifying matrix data structures: Simplifying and speeding up iterative algorithms. In Proceedings of Symposium on Simplicity in Algorithms (SOSA 2021), pages 1–13. SIAM, 2021. doi:10.1137/1.9781611976496.1.
[58] Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 456–480. IEEE, 2019. doi:10.1109/FOCS.2019.00036.
[59] Ying Xu and Harold N Gabow. Fast algorithms for transversal matroid intersection problems. In Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC 1994), pages 625–633. Springer, 1994. doi:10.1007/3-540-58325-4_231.

[bib.bib1] [1] Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra. Linear matroid intersection is in catalytic logspace. In Proceedings of the 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362, pages 3:1–3:23, 2026. doi:10.4230/LIPIcs.ITCS.2026.3.

[bib.bib2] [2] Martin Aigner and Thomas A Dowling. Matching theory for combinatorial geometries. Transactions of the American Mathematical Society, 158(1):231–245, 1971. doi:10.1090/S0002-9947-1971-0286689-5.

[bib.bib3] [3] Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 2005–2039. SIAM, 2025. doi:10.1137/1.9781611978322.63.

[bib.bib4] [4] Sepehr Assadi. A simple $(1-\varepsilon)$ -approximation semi-streaming algorithm for maximum (weighted) matching. TheoretiCS, 4, 2025. Preliminary version in SOSA 2024. doi:10.46298/theoretics.25.16.

[bib.bib5] [5] Alexander I Barvinok. New algorithms for linear $k$ -matroid intersection and matroid $k$ -parity problems. Mathematical Programming, 69(1):449–470, 1995. doi:10.1007/BF01585571.

[bib.bib6] [6] Joakim Blikstad. Breaking $O(nr)$ for matroid intersection. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 198, pages 31:1–31:17, 2021. doi:10.4230/LIPIcs.ICALP.2021.31.

[bib.bib7] [7] Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, and Ta-Wei Tu. Fast algorithms via dynamic-oracle matroids. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pages 1229–1242, 2023. doi:10.1145/3564246.3585219.

[bib.bib8] [8] Joakim Blikstad and Ta-Wei Tu. Efficient matroid intersection via a batch-update auction algorithm. In Proceedings of the 8th Symposium on Simplicity in Algorithms (SOSA 2025), pages 226–237. SIAM, 2025. doi:10.1137/1.9781611978315.18.

[bib.bib9] [9] Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, and Danupon Nanongkai. Breaking the quadratic barrier for matroid intersection. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), pages 421–432, 2021. doi:10.1145/3406325.3451092.

[bib.bib10] [10] Cornelius Brand and Kevin Pratt. Parameterized applications of symbolic differentiation of (totally) multilinear polynomials. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 38:1–38:19, 2021. doi:10.4230/LIPIcs.ICALP.2021.38.

[bib.bib11] [11] James R Bunch and John E Hopcroft. Triangular factorization and inversion by fast matrix multiplication. Mathematics of Computation, 28(125):231–236, 1974.

[bib.bib12] [12] Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, and Sam Chiu-wai Wong. Faster matroid intersection. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 1146–1168. IEEE, 2019. doi:10.1109/FOCS.2019.00072.

[bib.bib13] [13] Chandra Chekuri and Kent Quanrud. A fast approximation for maximum weight matroid intersection. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pages 445–457. SIAM, 2016. doi:10.1137/1.9781611974331.ch33.

[bib.bib14] [14] Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. Fast matrix rank algorithms and applications. Journal of the ACM (JACM), 60(5):1–25, 2013. Preliminary version in STOC 2012. doi:10.1145/2528404.

[bib.bib15] [15] Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung. Algebraic algorithms for linear matroid parity problems. ACM Transactions on Algorithms (TALG), 10(3):1–26, 2014. Preliminary version in SODA 2011. doi:10.1145/2601066.

[bib.bib16] [16] William H Cunningham. Improved bounds for matroid partition and intersection algorithms. SIAM Journal on Computing, 15(4):948–957, 1986. doi:10.1137/0215066.

[bib.bib17] [17] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib18] [18] Aditi Dudeja and Mara Grilnberger. A weighted-to-unweighted reduction for matroid intersection. arXiv preprint arXiv:2602.15702, 2026. doi:10.48550/arXiv.2602.15702.

[bib.bib19] [19] Jean-Guillaume Dumas, Clément Pernet, and Ziad Sultan. Simultaneous computation of the row and column rank profiles. In Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (ISSAC 2013), pages 181–188, 2013. doi:10.1145/2465506.2465517.

[bib.bib20] [20] Jean-Guillaume Dumas, Clément Pernet, and Ziad Sultan. Fast computation of the rank profile matrix and the generalized bruhat decomposition. Journal of Symbolic Computation, 83:187–210, 2017. doi:10.1016/j.jsc.2016.11.011.

[bib.bib21] [21] Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and Their Applications, pages 69–87, 1970.

[bib.bib22] [22] Jack Edmonds. Matroid intersection. In Annals of Discrete Mathematics, volume 4, pages 39–49. Elsevier, 1979. doi:10.1016/S0167-5060(08)70817-3.

[bib.bib23] [23] Eduard Eiben, Tomohiro Koana, and Magnus Wahlström. Determinantal sieving. TheoretiCS, 4, 2025. Preliminary version in SODA 2024. doi:10.46298/theoretics.25.21.

[bib.bib24] [24] Rūsiņš Freivalds. Fast probabilistic algorithms. In Proceedings of the 8th International Symposium on Mathematical Foundations of Computer Science (MFCS 1979), pages 57–69. Springer, 1979.

[bib.bib25] [25] Satoru Fujishige and Zhang Xiaodong. An efficient cost scaling algorithm for the independent assignment problem. Journal of the Operations Research Society of Japan, 38(1):124–136, 1995.

[bib.bib26] [26] Harold N Gabow and Matthias Stallmann. Efficient algorithms for graphic matroid intersection and parity. In Proceedings of the 12th Colloquium on Automata, Languages and Programming (ICALP 1985), pages 210–220. Springer, 1985. doi:10.1007/BFb0015746.

[bib.bib27] [27] Harold N Gabow and Robert E Tarjan. Efficient algorithms for simple matroid intersection problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FOCS 1979), pages 196–204. IEEE, 1979. doi:10.1109/SFCS.1979.14.

[bib.bib28] [28] Harold N Gabow and Ying Xu. Efficient algorithms for independent assignment on graphic and linear matroids. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), pages 106–111. IEEE Computer Society, 1989. doi:10.1109/SFCS.1989.63463.

[bib.bib29] [29] Harold N Gabow and Ying Xu. Efficient theoretic and practical algorithms for linear matroid intersection problems. Journal of Computer and System Sciences, 53(1):129–147, 1996. doi:10.1006/jcss.1996.0054.

[bib.bib30] [30] Rohit Gurjar, Taihei Oki, and Roshan Raj. Fractional linear matroid matching is in Quasi-NC. In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024), volume 308, pages 63:1–63:14, 2024. doi:10.4230/LIPIcs.ESA.2024.63.

[bib.bib31] [31] Rohit Gurjar and Thomas Thierauf. Linear matroid intersection is in Quasi-NC. computational complexity, 29(2):9, 2020. Preliminary version in STOC 2017. doi:10.1007/s00037-020-00200-z.

[bib.bib32] [32] Nicholas JA Harvey. An algebraic algorithm for weighted linear matroid intersection. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pages 444–453, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283430.

[bib.bib33] [33] Nicholas JA Harvey. Algebraic algorithms for matching and matroid problems. SIAM Journal on Computing, 39(2):679–702, 2009. Preliminary version in FOCS 2006. doi:10.1137/070684008.

[bib.bib34] [34] Nicholas James Alexander Harvey. Matchings, matroids and submodular functions. PhD thesis, Massachusetts Institute of Technology, 2008.

[bib.bib35] [35] Chien-Chung Huang, Naonori Kakimura, and Naoyuki Kamiyama. Exact and approximation algorithms for weighted matroid intersection. Mathematical Programming, 177(1-2):85–112, 2019. Preliminary version in SODA 2016. doi:10.1007/s10107-018-1260-x.

[bib.bib36] [36] Claude-Pierre Jeannerod, Clément Pernet, and Arne Storjohann. Rank-profile revealing gaussian elimination and the cup matrix decomposition. Journal of Symbolic Computation, 56:46–68, 2013. doi:10.1016/j.jsc.2013.04.004.

[bib.bib37] [37] Tomohiro Koana and Magnus Wahlström. Faster algorithms on linear delta-matroids. In Proceedings of 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), volume 327, pages 62:1–62:19, 2025. doi:10.4230/LIPIcs.STACS.2025.62.

[bib.bib38] [38] Eugene L Lawler. Matroid intersection algorithms. Mathematical Programming, 9(1):31–56, 1975. doi:10.1007/BF01681329.

[bib.bib39] [39] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), pages 1049–1065. IEEE, 2015. doi:10.1109/FOCS.2015.68.

[bib.bib40] [40] Dániel Marx. A parameterized view on matroid optimization problems. Theoretical Computer Science, 410(44):4471–4479, 2009. Preliminary version in ICALP 2006. doi:10.1016/j.tcs.2009.07.027.

[bib.bib41] [41] Kazuki Matoya and Taihei Oki. Pfaffian pairs and parities: Counting on linear matroid intersection and parity problems. SIAM Journal on Discrete Mathematics, 36(3):2121–2158, 2022. Preliminary version in IPCO 2021. doi:10.1137/21m1421751.

[bib.bib42] [42] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. doi:10.1017/cbo9780511814075.

[bib.bib43] [43] Harihar Narayanan, Huzur Saran, and Vijay V Vazirani. Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjoint spanning trees. SIAM Journal on Computing, 23(2):387–397, 1994. Preliminary version in SODA 1992. doi:10.1137/S0097539791195245.

[bib.bib44] [44] Huy L Nguyen. Fast greedy for linear matroids. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 516–524. SIAM, 2019. doi:10.1137/1.9781611975482.32.

[bib.bib45] [45] Huy L Nguyen. A note on Cunningham’s algorithm for matroid intersection. arXiv preprint arXiv:1904.04129, 2019. doi:10.48550/arXiv.1904.04129.

[bib.bib46] [46] Taihei Oki and Tasuku Soma. Algebraic algorithms for fractional linear matroid parity via noncommutative rank. SIAM Journal on Computing, 54(1):134–162, 2025. Preliminary version in SODA 2023. doi:10.1137/22m1537096.

[bib.bib47] [47] James G Oxley. Matroid theory, volume 3. Oxford University Press, USA, 2006.

[bib.bib48] [48] Kent Quanrud. Adaptive sparsification for matroid intersection. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297, pages 118:1–118:20, 2024. doi:10.4230/LIPIcs.ICALP.2024.118.

[bib.bib49] [49] Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.

[bib.bib50] [50] Jacob T Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM (JACM), 27(4):701–717, 1980. doi:10.1145/322217.322225.

[bib.bib51] [51] Maiko Shigeno and Satoru Iwata. A dual approximation approach to weighted matroid intersection. Operations Research Letters, 18(3):153–156, 1995. doi:10.1016/0167-6377(95)00047-X.

[bib.bib52] [52] Arne Storjohann and Shiyun Yang. Linear independence oracles and applications to rectangular and low rank linear systems. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pages 381–388, 2014. doi:10.1145/2608628.2608673.

[bib.bib53] [53] Tatsuya Terao. Deterministic $(2/3-\varepsilon)$ -approximation of matroid intersection using nearly-linear independence-oracle queries. In Proceedings of the 19th International Symposium on Algorithms and Data Structures (WADS 2025), volume 349, pages 50:1–50:18, 2025. doi:10.4230/LIPIcs.WADS.2025.50.

[bib.bib54] [54] Tatsuya Terao. Faster approximate linear matroid intersection. arXiv preprint arXiv:2604.11725, 2026. doi:10.48550/arXiv.2604.11725.

[bib.bib55] [55] Nobuaki Tomizawa and Masao Iri. An algorithm for determining the rank of a triple matrix product AXB with application to the problem of discerning the existence of the unique solution in a network. Electronics and Communications in Japan (Scripta Electronica Japonica II), 57(11):50–57, 1974.

[bib.bib56] [56] Ta-Wei Tu. Subquadratic weighted matroid intersection under rank oracles. In Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248, pages 63:1–63:14, 2022. doi:10.4230/LIPIcs.ISAAC.2022.63.

[bib.bib57] [57] Jan van den Brand. Unifying matrix data structures: Simplifying and speeding up iterative algorithms. In Proceedings of Symposium on Simplicity in Algorithms (SOSA 2021), pages 1–13. SIAM, 2021. doi:10.1137/1.9781611976496.1.

[bib.bib58] [58] Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 456–480. IEEE, 2019. doi:10.1109/FOCS.2019.00036.

[bib.bib59] [59] Ying Xu and Harold N Gabow. Fast algorithms for transversal matroid intersection problems. In Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC 1994), pages 625–633. Springer, 1994. doi:10.1007/3-540-58325-4_231.

Faster Approximate Linear Matroid Intersection

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Fast Algorithms for Linear Matroid Problems.

Linear Matroid Intersection.

Our Result for Maximum Cardinality Linear Matroid Intersection.

Theorem 1.

Weighted Linear Matroid Intersection.

Our Result for Maximum Weight Linear Matroid Intersection.

Theorem 2.

1.1 Technical Overview

Adaptive Sparsification Framework of Quanrud [48].

Challenge in Computing a Span.

Challenge for Weighted Linear Matroid Intersection.

1.2 Related Work

Faster Matroid Intersection under Oracle Models.

Additional Related Work.

Concurrent Work.

2 Preliminaries

2.1 Basic Notation

2.2 Assumptions and Conventions

Lemma 3 (from [14, Lemma 2.1]).

Lemma 4 (Schwartz–Zippel Lemma [50]).

2.3 Matroid Preliminaries

Matroid Rank and Span.

Matroid Intersection.

Theorem 5 (Matroid intersection theorem [21]; see also [49, Theorem 41.1]).

Theorem 6 (Harvey’s exact linear matroid intersection algorithm; see [33, Section 4.6]).

2.4 Sketching Technique of Cheung–Kwok–Lau

Lemma 7 (Sketching technique of Cheung–Kwok–Lau [14]; from [14, Lemma 2.9]).

Lemma 8 (Fast computation of a basis of the orthogonal complement of the column space).

Lemma 9 (from [14, Theorem 1.3(2)]; see also [14, Section 4.1.2]).

2.5 Fast Gram–Schmidt Orthonormalization

Lemma 10 (Fast Gram–Schmidt orthonormalization; from van den Brand [57, Section 4.5]).

3 Fast Span Computation Algorithm

Lemma 11.

Proof.

Claim 12.

Proof of Claim 12.

4 Adaptive Sparsification Framework of Quanrud

4.1 Maximum Cardinality Matroid Intersection

4.2 Maximum Weight Matroid Intersection

5 Linear Matroid Intersection Algorithms

5.1 Maximum Cardinality Linear Matroid Intersection

Theorem 13.

Proof.

Proof of Theorem 1.

5.2 Maximum Weight Linear Matroid Intersection

Theorem 14.

Lemma 15.

Lemma 16.

Proof of Lemma 16 for matrices over ℝ.

Proof of Theorem 14.

Proof of Theorem 2.

References

Proof of Lemma 16 for matrices over $\mathbb{R}$ .