Core-Sparse Monge Matrix Multiplication

We consider the core-sparse Monge matrix multiplication problem from the combinatorial and algorithmic points of view, and confirm that the core size is the right parameter that enables fast min-plus matrix multiplication. Let $\delta (A)$, or the core size of $A$, denote the number of non-zero elements in $A^{\mathrm{\square }}$. We begin with analyzing, in Section 3, how the core size of $A\otimes B$ depends on the core sizes of $A$ and $B$.

We stress that this the first bound on $\delta (A\otimes B)$ in terms of $\delta (A)$ and $\delta (B)$: the complexity analysis of Russo’s algorithm [34] requires a bound on all $\delta (A)$, $\delta (B)$, and $\delta (A\otimes B)$.

Next, in Section 4, we generalize Tiskin’s algorithm (but fully avoiding the formalism of the seaweed product) to solve the core-sparse Monge matrix multiplication problem. We believe that the more elementary interpretation makes our viewpoint not only more robust but also easier to understand. At the same time, the extension from simple unit-Monge matrices to general core-sparse Monge matrices introduces a few technical complications handled in the full version of the paper [21]. Notably, we need to keep track of the leftmost column and the bottommost row instead of assuming they are filled with zeroes. Further, the core does not form a permutation so splitting it into two halves of the same size requires some calculations.

The above complexity improves upon Russo’s [34] and matches Tiskin’s [41] for the simple unit-Monge case. Thanks to the more direct description, we can easily extend our algorithm to build (in the same complexity) an $𝒪(n+\delta )$-size data structure that, given $(i,k)$, in $𝒪(\log n)$ time computes the smallest witness $j$ such that $C_{i,k}=A_{i,j}+B_{j,k}$.

As an application of our witness recovery functionality, we consider the problem of range LIS queries. This task asks to preprocess an integer array $s[0..n)$ so that, later, given two indices , the longest increasing subsequence (LIS) of the sub-array $s[i..j)$ can be reported efficiently. Tiskin [38, 41] showed that the LIS size $\mathrm{\ell }$ can be reported in $𝒪(\log n)$ time after $𝒪(n{\log }^{2}n)$-time preprocessing. It was unclear, though, how to efficiently report the LIS itself. The recent work of Karthik C. S. and Rahul [27] achieved $𝒪(n^{1/2}{\log }^{3}n+\mathrm{\ell })$-time reporting (correct with high probability) after $𝒪(n^{3/2}{\log }^{3}n)$-time preprocessing. It is fairly easy to use our witness recovery algorithm to deterministically support $𝒪(\mathrm{\ell }{\log }^{2}n)$-time reporting after $𝒪(n{\log }^{2}n)$-time preprocessing; see Section 5 for an overview of this result. As further shown in the full version of the paper [21], the reporting time can be improved to $𝒪(\mathrm{\ell }\log n)$ and, with the preprocessing time increased to $𝒪(n{\log }^{3}n)$, all the way to $𝒪(\mathrm{\ell })$.

In parallel to this work, Gorbachev and Kociumaka [22] used core-sparse Monge matrix multiplication for the weighted edit distance with integer weights. Theorem 1.2 allowed for saving two logarithmic factors in the final time complexities compared to the initial preprint using Russo’s approach [34]. Weighted edit distance is known to be reducible to unweighted LCS only for a very limited class of so-called uniform weight functions [38], so this application requires the general core-sparse Monge matrix multiplication.

An interesting open problem is whether any non-trivial trade-off can be achieved for the weighted version of range LIS queries, where each element of $s$ has a weight, and the task is to compute a maximum-weight increasing subsequence of $s[i..j)$: either the weight alone or the whole subsequence. Surprisingly, as we show in the full version of the paper [21], if our bound $\delta (A\otimes B)\le 2\cdot (\delta (A)+\delta (B))$ of Theorem 1.1 can be improved to $\delta (A\otimes B)\le c\cdot (\delta (A)+\delta (B))+\stackrel{~}{}𝒪(p+q+r)$ for some , then our techniques automatically yield a solution with $\stackrel{~}{}𝒪(n^{1+{\log }_{2}c})$ preprocessing time, $\stackrel{~}{}𝒪(1)$ query time, and $\stackrel{~}{}𝒪(\mathrm{\ell })$ reporting time.

It suffices to sum the inequality in Definition 2.1 for all $i\in [a..b)$ and $j\in [c..d)$. $◀$

The min-plus product of two Monge matrices is also Monge.

In the context of Monge matrices, it is useful to define the core and the density matrix.

Note that, for a Monge matrix $A$, all entries of its density matrix are non-negative, and thus $\mathrm{core}(A)$ consists of triples $(i,j,v)$ with some positive values $v$.

For any matrix $A$ of size $p\times q$ and integers and , we write $A[a..b)[c..d)$ to denote the contiguous submatrix of $A$ consisting of all entries on the intersection of rows $[a..b)$ and columns $[c..d)$ of $A$. Matrices $A[a..b][c..d]$, $A(a..b][c..d)$, etc., are defined analogously.

By the definition of $A^{\mathrm{\square }}$, we have $A_{i,j}+A_{i+1,j+1}+A_{i,j}^{\mathrm{\square }}=A_{i,j+1}+A_{i+1,j}$ for all $i\in [a..b)$ and $j\in [c..d)$. The desired equality follows by summing up all these equalities. $◀$

An application of Observation 3.1 for $a=c=0$ implies that every value of $A$ can be uniquely reconstructed from $A$’s core and the values in the topmost row and the leftmost column of $A$.

By Observation 2.2, if $A$ is Monge, the Monge property holds for every (not necessarily contiguous) $2\times 2$ submatrix of $A$. In particular, it holds for contiguous $2\times 2$ submatrices of $A^{\prime }$, and thus $A^{\prime }$ satisfies Definition 2.1. $◀$

We next show a crucial property of the witness matrix.

We prove that ${𝒲}^{A,B}$ is non-decreasing by columns. The claim for rows is analogous. Fix some $i\in [0..p-1)$ and $k\in [0..r)$. Let $j^{\ast }≔{𝒲}_{i,k}^{A,B}$ and $j\in [0..j^{\ast })$. As $j^{\ast }$ is the smallest witness for $(i,k)$, we have $A_{i,j}+B_{j,k}>A_{i,j^{\ast }}+B_{j^{\ast },k}$. Using this fact and the Monge property for $A$, we derive

Since $A_{i+1,j}+B_{j,k}>A_{i+1,j^{\ast }}+B_{j^{\ast },k}$ for all $j\in [0..j^{\ast })$, we conclude that ${𝒲}_{i+1,k}^{A,B}\ge j^{\ast }={𝒲}_{i,k}^{A,B}$ holds as required. $◀$

We now show how to bound ${\delta }^{\mathrm{\Sigma }}(A\otimes B)$ in terms of ${\delta }^{\mathrm{\Sigma }}(A)$ and ${\delta }^{\mathrm{\Sigma }}(B)$.

Let $C≔A\otimes B$. Denote $j≔{𝒲}_{0,0}^{A,B}$ and $j^{\prime }≔{𝒲}_{p-1,r-1}^{A,B}$, where $j\le j^{\prime }$ due to Lemma 3.4. We have $C_{0,0}=A_{0,j}+B_{j,0}$ and $C_{p-1,r-1}=A_{p-1,j^{\prime }}+B_{j^{\prime },r-1}$. Furthermore, $C_{p-1,0}\le A_{p-1,j}+B_{j,0}$ and $C_{0,r-1}\le A_{0,j^{\prime }}+B_{j^{\prime },r-1}$ due to the definition of $C$. Hence, due to Observation 3.1, we obtain

The inequality ${\delta }^{\mathrm{\Sigma }}(C)\le {\delta }^{\mathrm{\Sigma }}(B)$ can be obtained using a symmetric argument. $◀$

The following corollary says that every core element of $A\otimes B$ can be attributed to at least one core element of $A$ and at least one core element of $B$.

Let $j={𝒲}_{i,k}^{A,B}$ and $j^{\prime }={𝒲}_{i+1,k+1}^{A,B}$. By monotonicity of ${𝒲}^{A,B}$ (Lemma 3.4), we have $j\le {𝒲}_{i,k+1}^{A,B},{𝒲}_{i+1,k}^{A,B}\le j^{\prime }$. Thus, $C[i..i+1][k..k+1]=A[i..i+1][j..j^{\prime }]\otimes B[j..j^{\prime }][k..k+1]$. Due to Lemma 3.5, we have . Thus, there exists a core element in $A^{\mathrm{\square }}[i..i+1)[j..j^{\prime })$.

Symmetrically, , and there exists a core element in $B^{\mathrm{\square }}[j..j^{\prime })[k..k+1)$. $◀$

We now use Corollary 3.6 to derive a bound on $\delta (A\otimes B)$ in terms of $\delta (A)$ and $\delta (B)$. The underlying idea is to show that every core element of $C$ is either the first or the last one (in the lexicographic ordering) that the mapping of Corollary 3.6 attributes to the corresponding core element of $A$ or $B$ (see Figure 1 for why the opposite would lead to a contradiction).

Let $C≔A\otimes B$. Define a function $f_A:\mathrm{core}(C)\to \mathrm{core}(A)$ that maps every core element $(i,k,C_{i,k}^{\mathrm{\square }})\in \mathrm{core}(C)$ to $(i,j,A_{i,j}^{\mathrm{\square }})$ for the smallest $j\in [{𝒲}_{i,k}^{A,B}..{𝒲}_{i+1,k+1}^{A,B})$ with $A_{i,j}^{\mathrm{\square }}\ne 0$; such a $j$ exists due to Corollary 3.6. Analogously, we define a function $f_B:\mathrm{core}(C)\to \mathrm{core}(B)$ that maps every core element $(i,k,C_{i,k}^{\mathrm{\square }})\in \mathrm{core}(C)$ to $(j,k,B_{j,k}^{\mathrm{\square }})$ for the smallest $j\in [{𝒲}_{i,k}^{A,B}..{𝒲}_{i+1,k+1}^{A,B})$ with $B_{j,k}^{\mathrm{\square }}\ne 0$; again, such a $j$ exists due to Corollary 3.6.

For a proof by contradiction, pick an element $c≔(i,k,C_{i,k}^{\mathrm{\square }})\in \mathrm{core}(C)$ violating the claim. Let $(i,j_A,A_{i,j_A}^{\mathrm{\square }})≔a≔f_A(c)$ and $(j_B,k,B_{j_B,k}^{\mathrm{\square }})≔b≔f_B(c)$. We make four symmetric arguments (all illustrated in Figure 1), with the first one presented in more detail.

1. 1.

   Since $c$ is not the minimal core element in $f_A^{-1}(a)$, we have $f_A(c^{\prime })=a$ for some core element $(i^{\prime },k^{\prime },C_{i^{\prime },k^{\prime }}^{\mathrm{\square }})≔c^{\prime }\in \mathrm{core}(C)$ that precedes $c$ in the lexicographical order, denoted $c^{\prime }\prec c$. Due to $f_A(c^{\prime })=a=(i,j_A,A_{i,j_A}^{\mathrm{\square }})$, we must have $i^{\prime }=i$ and . Since $i^{\prime }=i$, then $c^{\prime }\prec c$ implies $k^{\prime }+1\le k$. The monotonicity of the witness matrix (Lemma 3.4) thus yields ${𝒲}_{i+1,k^{\prime }+1}^{A,B}\le {𝒲}_{i+1,k}^{A,B}$. Overall, we conclude that .

2. 2.

   Since $c$ is not the maximal core element in $f_A^{-1}(a)$, we have $f_A(c^{\prime })=a$ for some core element $c^{\prime }\succ c$. In particular, $c^{\prime }=(i,k^{\prime },C_{i,k^{\prime }}^{\mathrm{\square }})\in \mathrm{core}(C)$ for some $k^{\prime }>k$. Then, ${𝒲}_{i,k+1}^{A,B}\le {𝒲}_{i,k^{\prime }}^{A,B}\le j_A$ follows from Lemma 3.4 and $f_A(c^{\prime })=a$, respectively.

3. 3.

   Since $c$ is not the minimal core element in $f_B^{-1}(b)$, we have $f_B(c^{\prime })=b$ for some core element $c^{\prime }\prec c$. In particular, $c^{\prime }=(i^{\prime },k,C_{i^{\prime },k}^{\mathrm{\square }})\in \mathrm{core}(C)$ for some . Then, ${𝒲}_{i,k+1}^{A,B}\ge {𝒲}_{i^{\prime }+1,k+1}^{A,B}>j_B$ follows from Lemma 3.4 and $f_B(c^{\prime })=b$, respectively.

4. 4.

   Since $c$ is not the maximal core element in $f_B^{-1}(b)$, we have $f_B(c^{\prime })=b$ for some core element $c^{\prime }\succ c$. In particular, $c^{\prime }=(i^{\prime },k,C_{i^{\prime },k}^{\mathrm{\square }})\in \mathrm{core}(C)$ for some $i^{\prime }>i$. Then, ${𝒲}_{i+1,k}^{A,B}\le {𝒲}_{i^{\prime },k}^{A,B}\le j_B$ follows from Lemma 3.4 and $f_B(c^{\prime })=b$, respectively.

Overall, we derive a contradiction: . $\mathrm{⊲}$ As every core element of $C$ is either the first or the last one in some pre-image under $f_A$ or $f_B$, we get that $\delta (C)\le 2\cdot (\delta (A)+\delta (B))$. $◀$

By Observation 3.1 applied for $a=c=0$, it suffices to answer orthogonal range sum queries on top of $\mathrm{core}(A)$. According to [45, Theorem 3], it can be done in $𝒪(\delta (A)\log (1+\delta (A)))$ preprocessing time and $𝒪(\log (2+\delta (A)))$ query time. $◀$

We now design another matrix oracle as an alternative to $\mathrm{𝖢𝖬𝖮}(A)$ for the situation in which one wants to query an entry of $A$ that is adjacent to some other already known entry.

The local core oracle data structure of $A$ stores all the values of the topmost row and the leftmost column of $A$, as well as two collections of lists: ${\mathrm{core}}_{i,\cdot }(A)$ for all $i\in [0..p-1)$ and ${\mathrm{core}}_{\cdot ,j}(A)$ for all $j\in [0..q-1)$. The values of the topmost row and the leftmost column of $A$ are already given. The lists ${\mathrm{core}}_{i,\cdot }(A)$ and ${\mathrm{core}}_{\cdot ,j}(A)$ can be computed in $𝒪(p+q+\delta (A))$ time from $\mathrm{core}(A)$. Hence, we can build $\mathrm{𝗅𝖼𝗈}(A)$ in time $𝒪(p+q+\delta (A))$.

Boundary access can be implemented trivially. We now show how to implement the vertically adjacent recomputation. Suppose that we are given $i\in [0..p-1)$ and $j\in [0..q)$. Due to Observation 3.1, we have $A_{i,j}+A_{i+1,0}=A_{i+1,j}+A_{i,0}+{\delta }^{\mathrm{\Sigma }}(A[i..i+1][0..j])$. Note that the values $A_{i,0}$ and $A_{i+1,0}$ can be computed in constant time using boundary access queries, and ${\delta }^{\mathrm{\Sigma }}(A[i..i+1][0..j])$ can be computed from ${\mathrm{core}}_{i,\cdot }(A)$ in time $𝒪({\delta }_{i,\cdot }(A)+1)$. Hence, $A_{i+1,j}-A_{i,j}$ can be computed in time $𝒪({\delta }_{i,\cdot }(A)+1)$.

The horizontally adjacent recomputation is implemented analogously so that $A_{i,j+1}-A_{i,j}$ can be computed in time $𝒪({\delta }_{\cdot ,j}(A)+1)$. $◀$

Note that vertically and horizontally adjacent recomputations allow computing the neighbors of any given entry $A_{i,j}$.

Say, $A^{\prime }=A[i..i^{\prime }][j..j^{\prime }]$. Note that $\mathrm{core}(A^{\prime })$ can be obtained in time $𝒪(\delta (A))$ by filtering out all elements of $\mathrm{core}(A)$ that lie outside of $[i..i^{\prime })\times [j..j^{\prime })$. It remains to obtain the topmost row and the leftmost column of $A^{\prime }$. In time $𝒪(p+q+\delta (A))$ we build $\mathrm{𝗅𝖼𝗈}(A)$ of Lemma 4.4. By starting from $A_{i,0}$ and repeatedly applying the horizontally adjacent recomputation, we can compute $A[i..i][0..q)$ (and thus $A[i..i][j..j^{\prime }]$) in time $𝒪({\sum }_{j\in [0..q)}({\delta }_{\cdot ,j}(A)+1))=𝒪(q+\delta (A))$. The leftmost column of $A^{\prime }$ can be computed in time $𝒪(p+\delta (A))$ analogously. $◀$

We now show a helper lemma that compresses “ultra-sparse” Monge matrices to limit their dimensions by the size of their core.

The compress algorithm deletes all rows of $A^{\ast }$ that do not contain any core elements and all columns of $B^{\ast }$ that do not contain any core elements. This way, $p\le \delta (A^{\ast })+1$ and $r\le \delta (B^{\ast })+1$ are guaranteed. Furthermore, all core elements of these two matrices are preserved. If there are no core elements between rows $i$ and $i+1$ of $A^{\ast }$, the corresponding entries of these two rows differ by some constant $c$, and thus all the entries of the row $i+1$ of $A^{\ast }\otimes B^{\ast }$ can be obtained from the corresponding entries of row $i$ of $A^{\ast }\otimes B^{\ast }$ by adding $c$. Since we can recover $c$ from $A^{\ast }$, no information about the answer is “lost” when deleting such rows. An analogous property holds for the removed columns of $B^{\ast }$. The decompress algorithm reverses the row and column removals performed by the compress algorithm.

The compress algorithm also reduces the number $q^{\ast }$ of columns of $A^{\ast }$ and rows of $B^{\ast }$ to $q\le \delta (A^{\ast })+\delta (B^{\ast })+1$. Observe that if there are no core elements between columns $j$ and $j+1$ of $A^{\ast }$ and between rows $j$ and $j+1$ of $B^{\ast }$, then the values $A_{i,j}^{\ast }+B_{j,k}^{\ast }$ and $A_{i,j+1}^{\ast }+B_{j+1,k}^{\ast }$ differ by a constant independent of $i$ and $k$. Depending on the sign of this constant difference, we can delete either the $j$-th column of $A^{\ast }$ and the $j$-th row of $B^{\ast }$ or the $(j+1)$-th column of $A^{\ast }$ and the $(j+1)$-th row of $B^{\ast }$ so that we do not change the min-plus product of these matrices. By repeating this process for all indices $j$ that do not “contribute” to the cores of $A^{\ast }$ and $B^{\ast }$, we get $q\le \delta (A^{\ast })+\delta (B^{\ast })+1$. The formal proof can be found in the full version of the paper [21]. $◀$

Finally, we show our main Monge matrix multiplication algorithm.