Fast Zeta Transforms for Lattices with Few Irreducibles

Research output: Contribution to journalArticleScientificpeer-review

Standard

Fast Zeta Transforms for Lattices with Few Irreducibles. / Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko; Nederlof, Jesper; Parviainen, Pekka.

In: ACM Transactions on Algorithms, Vol. 12, No. 1, 4, 02.2016.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

APA

Vancouver

Author

Björklund, Andreas ; Husfeldt, Thore ; Kaski, Petteri ; Koivisto, Mikko ; Nederlof, Jesper ; Parviainen, Pekka. / Fast Zeta Transforms for Lattices with Few Irreducibles. In: ACM Transactions on Algorithms. 2016 ; Vol. 12, No. 1.

Bibtex - Download

@article{1780980fd3f84e60a45a4c3686ca176b,
title = "Fast Zeta Transforms for Lattices with Few Irreducibles",
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.",
keywords = "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",
author = "Andreas Bj{\"o}rklund and Thore Husfeldt and Petteri Kaski and Mikko Koivisto and Jesper Nederlof and Pekka Parviainen",
note = "VK: Kaski, P.; HIIT",
year = "2016",
month = "2",
doi = "10.1145/2629429",
language = "English",
volume = "12",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
number = "1",

}

RIS - Download

TY - JOUR

T1 - Fast Zeta Transforms for Lattices with Few Irreducibles

AU - Björklund, Andreas

AU - Husfeldt, Thore

AU - Kaski, Petteri

AU - Koivisto, Mikko

AU - Nederlof, Jesper

AU - Parviainen, Pekka

N1 - VK: Kaski, P.; HIIT

PY - 2016/2

Y1 - 2016/2

N2 - 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.

AB - 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.

KW - Arithmetic circuit

KW - fast multiplication

KW - lattice

KW - zeta transform

KW - Mobius transform

KW - Mobius inversion

KW - semigroup algebra

KW - SEMIGROUP REPRESENTATION-THEORY

KW - FAST FOURIER-TRANSFORMS

KW - HYPERPLANE ARRANGEMENTS

KW - MOBIUS FUNCTIONS

KW - ALGEBRAS

KW - GRAPHS

KW - SET

UR - http://dx.doi.org/10.1145/2629429

U2 - 10.1145/2629429

DO - 10.1145/2629429

M3 - Article

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 1

M1 - 4

ER -

ID: 2007032