Change search
ReferencesLink to record
Permanent link

Direct link
Fast Zeta Transforms for Lattices with Few Irreducibles
Show others and affiliations
2016 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 12, no 1, 4Article in journal (Refereed) PublishedText
Abstract [en]

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.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2016. Vol. 12, no 1, 4
Keyword [en]
Arithmetic circuit, fast multiplication, lattice, zeta transform, Mobius transform, Mobius inversion, semigroup algebra
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-184971DOI: 10.1145/2629429ISI: 000371364600004ScopusID: 2-s2.0-84954312180OAI: oai:DiVA.org:kth-184971DiVA: diva2:917799
Conference
23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), JAN 17-19, 2012, Kyoto, JAPAN
Funder
Science for Life Laboratory - a national resource center for high-throughput molecular bioscience
Note

QC 20160407

Available from: 2016-04-07 Created: 2016-04-07 Last updated: 2016-04-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Parviainen, Pekka
By organisation
Science for Life Laboratory, SciLifeLabComputational Science and Technology (CST)
In the same journal
ACM Transactions on Algorithms
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 11 hits
ReferencesLink to record
Permanent link

Direct link