Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Fast Zeta Transforms for Lattices with Few Irreducibles
Visa övriga samt affilieringar
2016 (Engelska)Ingår i: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 12, nr 1, artikel-id 4Artikel i tidskrift (Refereegranskat) Published
Resurstyp
Text
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.

Ort, förlag, år, upplaga, sidor
Association for Computing Machinery (ACM), 2016. Vol. 12, nr 1, artikel-id 4
Nyckelord [en]
Arithmetic circuit, fast multiplication, lattice, zeta transform, Mobius transform, Mobius inversion, semigroup algebra
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:kth:diva-184971DOI: 10.1145/2629429ISI: 000371364600004Scopus ID: 2-s2.0-84954312180OAI: oai:DiVA.org:kth-184971DiVA, id: diva2:917799
Konferens
23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), JAN 17-19, 2012, Kyoto, JAPAN
Forskningsfinansiär
Science for Life Laboratory - a national resource center for high-throughput molecular bioscience
Anmärkning

QC 20160407

Tillgänglig från: 2016-04-07 Skapad: 2016-04-07 Senast uppdaterad: 2018-01-10Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Sök vidare i DiVA

Av författaren/redaktören
Parviainen, Pekka
Av organisationen
Science for Life Laboratory, SciLifeLabBeräkningsvetenskap och beräkningsteknik (CST)
I samma tidskrift
ACM Transactions on Algorithms
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 167 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf