Fast zeta transforms for lattices with few irreducibles

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

doi:10.1137/1.9781611973099.113

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 proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12, Kyoto, Japan, January 17-19, 2012)
Editors	Y. Rabani
Publisher	Society for Industrial and Applied Mathematics (SIAM)
Pages	1436-1444
ISBN (Print)	978-1-61197-210-8
DOIs	https://doi.org/10.1137/1.9781611973099.113
Publication status	Published - 2012
Externally published	Yes
Event	23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012) - Westin Miyako, Kyoto, Japan Duration: 17 Jan 2012 → 19 Jan 2012 Conference number: 23 http://www.siam.org/meetings/da12/

Conference

Conference	23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)
Abbreviated title	SODA '12
Country/Territory	Japan
City	Kyoto
Period	17/01/12 → 19/01/12
Internet address	http://www.siam.org/meetings/da12/

Access to Document

10.1137/1.9781611973099.113

Cite this

Björklund, A., Koivisto, M., Husfeldt, T., Nederlof, J., Kaski, P., & Parviainen, P. (2012). Fast zeta transforms for lattices with few irreducibles. In Y. Rabani (Ed.), 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12, Kyoto, Japan, January 17-19, 2012) (pp. 1436-1444). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611973099.113

@inproceedings{7b0b56af79f2437185f387093ed56f26,

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 M{\"o}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{\"o}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.",

author = "A. Bj{\"o}rklund and M. Koivisto and T. Husfeldt and J. Nederlof and P. Kaski and P. Parviainen",

year = "2012",

doi = "10.1137/1.9781611973099.113",

language = "English",

isbn = "978-1-61197-210-8",

pages = "1436--1444",

editor = "Y. Rabani",

booktitle = "23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12, Kyoto, Japan, January 17-19, 2012)",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

address = "United States",

note = "23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), SODA '12 ; Conference date: 17-01-2012 Through 19-01-2012",

url = "http://www.siam.org/meetings/da12/",

}

Björklund, A, Koivisto, M, Husfeldt, T, Nederlof, J, Kaski, P & Parviainen, P 2012, Fast zeta transforms for lattices with few irreducibles. in Y Rabani (ed.), 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12, Kyoto, Japan, January 17-19, 2012). Society for Industrial and Applied Mathematics (SIAM), pp. 1436-1444, 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), Kyoto, Japan, 17/01/12. https://doi.org/10.1137/1.9781611973099.113

Fast zeta transforms for lattices with few irreducibles. / Björklund, A.; Koivisto, M.; Husfeldt, T. et al.

23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12, Kyoto, Japan, January 17-19, 2012). ed. / Y. Rabani. Society for Industrial and Applied Mathematics (SIAM), 2012. p. 1436-1444.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Fast zeta transforms for lattices with few irreducibles

AU - Björklund, A.

AU - Koivisto, M.

AU - Husfeldt, T.

AU - Nederlof, J.

AU - Kaski, P.

AU - Parviainen, P.

N1 - Conference code: 23

PY - 2012

Y1 - 2012

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

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

U2 - 10.1137/1.9781611973099.113

DO - 10.1137/1.9781611973099.113

M3 - Conference contribution

SN - 978-1-61197-210-8

SP - 1436

EP - 1444

BT - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12, Kyoto, Japan, January 17-19, 2012)

A2 - Rabani, Y.

PB - Society for Industrial and Applied Mathematics (SIAM)

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)

Y2 - 17 January 2012 through 19 January 2012

ER -

Fast zeta transforms for lattices with few irreducibles

Abstract

Conference

Access to Document

Fingerprint

Cite this