Fast zeta transforms for lattices with few irreducibles

A. Björklund, M. Koivisto, T. Husfeldt, J. Nederlof, P. Kaski, P. Parviainen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

Abstract

We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Möbius 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 Möbius algebra. Furthermore, the circuit construction in fact gives optimal (up to constants) circuits for a number of 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.
Original languageEnglish
Title of host publication23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12, Kyoto, Japan, January 17-19, 2012)
EditorsY. Rabani
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages1436-1444
ISBN (Print)978-1-61197-210-8
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012) - Westin Miyako, Kyoto, Japan
Duration: 17 Jan 201219 Jan 2012
Conference number: 23
http://www.siam.org/meetings/da12/

Conference

Conference23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)
Abbreviated titleSODA '12
CountryJapan
CityKyoto
Period17/01/1219/01/12
Internet address

Fingerprint Dive into the research topics of 'Fast zeta transforms for lattices with few irreducibles'. Together they form a unique fingerprint.

Cite this