Zero-Counting by Quadrants

The algorithm used in ALE is a specialized sparse matrix multiplication algorithm for semirings. Sorting of the rows and columns of the matrix takes place through the standard depth-first topological sorting algorithm provided in the last section. In such matrices,^3.1 the transitive closure of the matrix can be calculated as:
[Code--Upper Triangular Transitive Closure]

$$\quad \left( \begin{array}{cc} A & B \\ 0 & C \end{array... ...y}{cc} A^{*} & A^{*}BC^{*} \\ 0 & C^{*} \end{array}\right)$$

An algorithm to efficiently calculate this has been specially developed to make use of the sparseness property of these matrices.

Two functions are used to recursively divide a matrix evenly into quadrants. For any $i$ and $n$ such that $1\leq i\leq n$, let $d_n(i)$ be defined such that:

$$d_n(i) = \left\{ \begin{array}{ll} 0 & i=1\\ d_{\lceil n/... ...eil n/2\rceil) + 1 & i>\lceil n/2 \rceil \end{array} \right.$$

In addition, for any $d\geq d_n(i)$, let $q^{d}_n(i)$ be defined such that:

$$q^{d}_n(i) = \left\{ \begin{array}{ll} n & d=0\ (\textrm{th... ...l n/2\rceil) & d>0, i > \lceil n/2\rceil \end{array} \right.$$

One way of looking at them is as measures defined on a balanced binary tree with $n$ leaves. Given the $i$th leaf from the left, there will be some subtrees for which $i$ is the leftmost leaf. In that case, $d_n(i)$ is the least depth of such a subtree, and $q^{d}_n(i)$ is the total number of leaves that such a subtree at depth $d$ has.

Given a matrix $M$, we shall say that a submatrix is rooted at $M[i,j]$ iff $[i,j]$ is its leftmost, uppermost coordinate in $M$.

Given $i$, $j$, $m$ and $n$ such that $1\leq i \leq m$, and $1\leq j \leq n$, let $v_{\langle m,n\rangle}(i,j) = \max(d_m(i),d_n(j))$. When we divide an $m\times n$ matrix $M$ evenly into quadrants, then the largest quadrant rooted at $M[i,j]$ will be $q^{v_{\langle m,n\rangle}(i,j)}_m(i) \times q^{v_{\langle m,n\rangle}(i,j)}_n(j)$ in size. It can be proven that if $m$ and $n$ differ by no more than 1 in the original matrix, then these two dimensions will differ by no more than 1.

Now, given a Boolean matrix $M$, there is a unique matrix $Z(M)$ over the non-negative integers such that the value of $Z(M)[i,j]$ is the size of the largest zero-quadrant rooted at $M[i,j]$ in the largest quadrant rooted at $M[i,j]$. If this largest zero-quadrant is not square, then we use the larger of its dimensions as the value. As a simple example, consider the $4\times 4$ identity matrix as $M$:

$$\begin{array}{cc} M = \left( \begin{array}{llll} 1 & 0 & 0 &... ... 2 & 1 & 0 & 1\\ 1 & 1 & 1 & 0 \end{array} \right) \end{array}$$

Note that the 1s in $M$ are replaced by 0s in $Z(M)$--there are no zero-quadrants rooted at those coordinates. Also notice that many values of $Z(M)$ can be inferred from other values. The fact that $Z(M)[1,3]$ is 2, for example, tells us that $Z(M)[1,4]$, $Z(M)[2,3]$, and $Z(M)[2,4]$ must be 1, and vice versa. It is perhaps useful to conventionally write $Z(M)$ with as few values as can be used to infer the rest of the matrix:

$$Z(M) = \left( \begin{array}{llll} 0 & 1 & 2 & -\\ 1 & 0 & - & -\\ 2 & - & 0 & 1\\ - & - & 1 & 0 \end{array} \right)$$

This convention accentuates the sparseness of the original matrix $M$.