Name
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2629429 | SODA |
Keywords | DocType | Volume |
orthogonal basis,positive integer,finite lattice,bius algebra,fast zeta,finite vector space,set partition,fast multiplication,fast algorithm,finite set,positive divisor | Conference | 12 |
Issue | ISSN | ISBN |
1 | 1549-6325 | 978-1-61197-251-1 |
Citations | PageRank | References |
2 | 0.38 | 10 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas BjöRklund | 1 | 269 | 11.91 |
| Mikko Koivisto | 2 | 803 | 55.81 |
| Thore Husfeldt | 3 | 733 | 40.87 |
| Jesper Nederlof | 4 | 294 | 24.22 |
| Petteri Kaski | 5 | 912 | 66.03 |
| Pekka Parviainen | 6 | 79 | 8.95 |