A differential-operator approach to the permanental polynomial.
A recently published computational approach to the permanental polynomial scales very badly (approximately 2(n)) with problem size, relying as it does on examining the entire augmented adjacency matrix for nonzero products. The present study presents an entirely different algorithm that relies on symbolic computation of second partial derivatives. This approach has previously been applied to the matching polynomial but not the permanental polynomial. The differential-operator algorithm scales much better with problem size. For fullerene-type structures without perimeters, the two algorithms take about the same time to compute n = 32. On one n = 40 structure, the new algorithm was >45 times faster. Relative performance is even better for polycyclic aromatic hydrocarbon structures, which have perimeters.
Cash
Gordon G
GG
Risk Assessment Division (7403M), Office of Pollution Prevention and Toxics, United States Environmental Protection Agency, 1200 Pennsylvania Avenue, NW, Washington, DC 20460, USA. cash.gordon@epa.gov