# Star Bicolouring of Bipartite Graphs
## 2 Sparse Jacobian Determination  
In this section, we provide a brief introduction to an application area that gives rise to the star bicolouring problem considered in this paper. Many algorithms in nonlinear optimisation and nonlinear equations require the knowledge of first- or higher-order derivatives of the underlying mathematical mappings. Exceptfor very simple functions, the hand calculation of derivatives is an error-prone and tedious process. Fortunately, there are interesting and effective alternatives such as finite differencing and algorithmic differentiation (AD) [19]. Let \(F\) be a once continuously differentiable function \(F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}\) for which the Jacobian \(F^{\prime}\) evaluated at \(x\in\mathbb{R}^{n}\) is sparse. Assuming that the sparsity pattern of matrix \(J\equiv F^{\prime}(x)\) is available, one can define \"seed matrices\" \(S\in\{0,1\}^{n\times p}\) and \(W\in\{0,1\}^{m\times q}\) based on the given sparsity pattern and compute the products  
\[B=JS\text{ and }C=W^{T}J\]  
using algorithmic differentiation. The compressed matrices \(B\) and \(C\) are obtained via \(p\)_forward passes_ and \(q\)_reverse passes_ of the AD, where each \"pass\" requires work proportional to a small constant multiple of the cost of evaluating the mapping \(F\) at the given argument [19]. For sparse problems numbers, \(p\) and \(q\) are usually much smaller than the matrix dimension \(n\) and \(m\), respectively. In a _direct method_, the nonzero entries of the Jacobian matrix can be recovered from the compressed matrices \(B\) and \(C\) by requiring that the seed matrices \(S\) and \(W\) be chosen such that, for each \(J_{ij}\
eq 0\), there is an index \(k\) for which  
\[J_{ij}=B_{ik}\text{ or }J_{ij}=C_{kj}.\]  
The goal is to minimise the work, i.e., to obtain suitable matrices \(S\) and \(W\) with \((p+q)\) minimised. [PERSON], [PERSON], and [PERSON] in a seminal paper [4] provided the first row compression algorithm (a row compression is a one-sided compression where only the seed matrix \(S\) is defined), which was later improved by [PERSON] and [PERSON] [2], who provided the first graph colouring interpretation of the compression problem. The classical arrowhead matrix example demonstrates that one-sided compression may not yield the full exploitation of sparsity. [PERSON] and [PERSON] [8] and [PERSON] and [PERSON] [3] independently proposed techniques for combined column and row compression for the sparse Jacobian determination problem. The following bicolouring formulation was provided in [8]. Let \(A\in\{0,1\}^{m\times n}\) be a matrix with a sparsity pattern identical to the Jacobian \(J\). Define bipartite graph  
\[G(A)=(L,R,E),\]  
where \(L\) and \(R\) are the sets of vertices corresponding to the columns and rows of \(A\), respectively, and \(E\) is the set of edges between vertices in \(u_{i}\in L\) and \(v_{j}\in R\) such that \(\{u_{i},v_{j}\}\in E\) if and only if \(a_{ij}\
eq 0\). Mapping \(\phi:L\cup R\rightarrow\{1,\ldots,(p+q)\}\) is a \((p+q)\)_bicolouring_[8] if the following conditions are satisfied:  
1. \(\{u_{i},v_{j}\}\in E\) implies that \(\phi(u_{i})\
eq\phi(v_{j})\). 2. The set of colours used on vertices in \(L\) and \(R\) are disjoint, i.e., for indices \(i\) and \(j\) with \(u_{i}\in L\) and \(v_{j}\in R\), \(\phi(u_{i})\
eq\phi(v_{j})\). 3. Every path \(u_{i}-v_{j}-u_{k}-v_{l}\) in \(G(A)\) uses at least three distinct colours. The minimum bicolouring of \(G(A)\) is a \((p+q)\) bicolouring with the sum \((p+q)\) minimised. Determining the Jacobian matrix \(J\) directly from the products \(JS\) and \(W^{\top}J\) for appropriate seed matrices \(S\in\{0,1\}^{n\times p}\) and \(W\{0,1\}^{m\times q}\) with \((p+q)\) minimized has been shown to be equivalent to the minimum bicolouring of the bipartite graph \(G(A)\)[8]. The \((p+q)\) bicolouring problem introduced above is also referred to as star bicolouring in the literature.