Conjunction scheduling in image computation consists of clustering
the parts of a transition relation and ordering the clusters, so
that the size of the BDDs for the intermediate results of image
computation stay small. We present an approach based on the
analysis and permutation of the dependence matrix of the transition
relation. Our algorithm computes a bordered-block lower triangular
form of the matrix that heuristically minimized the active lifetime
of variables, that is, the number of conjunctions in which the
variables participate. The ordering procedure guides a clustering
algorithm based on the affinity of the transition relation parts.
The ordering procedure is then applied again to define the cluster
conjunction schedule. Our experimental results show the
effectiveness of the new algorithm.
