Accession Number:

ADA608089

Title:

Comments on Sympathy: Fast Exact Minimization of Fixed Polarity Reed-Muller Expansion for Symmetric Functions

Descriptive Note:

Journal article

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

Personal Author(s):

• Butler, Jon T.
• Dueck, Gerhard W.
• Shmerko, Vlad P.
• Yanuskevich, Svetlana

Report Date:

2000-11-01

Pagination or Media Count:

0.0

Abstract:

The above paper finds an optimal fixed-polarity Reed-Muller expansion of an eta-variable totally symmetric function using an OFDD-based algorithm that requires On7 time and On6 storage space. However, an algorithm based on Supruns transeunt triangles requires only On3 time and On2 storage space. An implementation of this algorithm yields computation times lower by several orders of magnitude.

Descriptors:

• *FUNCTIONS(MATHEMATICS)
• *POLARITY
• *SYMMETRY
• ALGORITHMS
• MATRICES(MATHEMATICS)

Subject Categories:

• Numerical Mathematics
• Theoretical Mathematics
• Electricity and Magnetism

Distribution Statement:

APPROVED FOR PUBLIC RELEASE