  Counting the number of perfect matchings in bipartite graphs, or equivalently
computing the permanent of 0-1 matrices, is an important combinatorial problem
that has been extensively studied by theoreticians and practitioners alike. The
permanent is #P-Complete; hence it is unlikely that a polynomial-time algorithm
exists for the problem. Researchers have therefore focused on finding tractable
subclasses of matrices for permanent computation. One such subclass that has
received much attention is that of sparse matrices i.e. matrices with few
entries set to 1, the rest being 0. For this subclass, improved theoretical
upper bounds and practically efficient algorithms have been developed. In this
paper, we ask whether it is possible to go beyond sparse matrices in our quest
for developing scalable techniques for the permanent, and answer this question
affirmatively. Our key insight is to represent permanent computation
symbolically using Algebraic Decision Diagrams (ADDs). ADD-based techniques
naturally use dynamic programming, and hence avoid redundant computation
through memoization. This permits exploiting the hidden structure in a large
class of matrices that have so far remained beyond the reach of permanent
computation techniques. The availability of sophisticated libraries
implementing ADDs also makes the task of engineering practical solutions
relatively straightforward. While a complete characterization of matrices
admitting a compact ADD representation remains open, we provide strong
experimental evidence of the effectiveness of our approach for computing the
permanent, not just for sparse matrices, but also for dense matrices and for
matrices with "similar" rows.
