Manipulation of Large-Scale Polynomials Using BMDs

Dror ROTTER  Kiyoharu HAMAGUCHI  Shin-ichi MINATO  Shuzo YAJIMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.10   pp.1774-1781
Publication Date: 1997/10/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
zero-suppressed binary decision diagrams (BDD),  binary moment diagrams,  polynomials,  

Full Text: PDF>>
Buy this Article

Minato has proposed canonical representation for polynomial functions using zero-suppressed binary decision diagrams (ZBDDs). In this paper, we extend binary moment diagrams (BMDs) proposed by Bryant and Chen to handle variables with degrees higher than l. The experimental results show that this approach is much more efficient than the previous ZBDDs' approach. The proposed approach is expected to be useful for various problems, in particular, for computer algebra.