Fast Zeta Transforms for Lattices with Few Irreducibles

Research output: Contribution to journalArticleScientificpeer-review

Researchers

Research units

  • Lund University
  • University of Helsinki
  • Utrecht University
  • KTH Royal Institute of Technology

Abstract

We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Mobius algebras of finite lattices. We show that every lattice with v elements, n of which are nonzero and join-irreducible (or, by a dual result, nonzero and meet-irreducible), has arithmetic circuits of size O(vn) for computing the zeta transform and its inverse, thus enabling fast multiplication in the Mobius algebra. Furthermore, the circuit construction in fact gives optimal (up to constants) monotone circuits for several lattices of combinatorial and algebraic relevance, such as the lattice of subsets of a finite set, the lattice of set partitions of a finite set, the lattice of vector subspaces of a finite vector space, and the lattice of positive divisors of a positive integer.

Details

Original languageEnglish
Article number4
Number of pages19
JournalACM Transactions on Algorithms
Volume12
Issue number1
Publication statusPublished - Feb 2016
MoE publication typeA1 Journal article-refereed
EventACM-SIAM Symposium on Discrete Algorithms - Kyoto, Japan
Duration: 17 Jan 201219 Jan 2012
Conference number: 23

    Research areas

  • Arithmetic circuit, fast multiplication, lattice, zeta transform, Mobius transform, Mobius inversion, semigroup algebra, SEMIGROUP REPRESENTATION-THEORY, FAST FOURIER-TRANSFORMS, HYPERPLANE ARRANGEMENTS, MOBIUS FUNCTIONS, ALGEBRAS, GRAPHS, SET

ID: 2007032