umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A New Algorithm for Computing the Smith Normal Form and its Implementation on Parallel Machines
Mathematisches Seminar Christian-Albrechts-Universität zu Kiel, Germany.
2004 (English)In: Proceedings of 6th Workshop on Advances in Parallel and Distributed Computation Models, International Parallel and Distributed Processing Symposium (IPDPS 2004), IEEE Press, 2004Conference paper, Published paper (Refereed)
Abstract [en]

Smith normal form computation is important in many topics, e.g. group theory and number theory. For matrices over the rings Z and F2 [x], we introduce a new Smith normal form algorithm, called Triangular Band Matrix Algorithm, which first computes the Hermite Normalform and then step by step the diagonal form and the Smith normal form. In comparison to the Kannan Bachem Algorithm, which computes the Smith normal form by alternately computing the Hermite normal form and the left Hermite normal form, the theoretical advantage is, that we only once apply the expensive Hermite normal form step. We parallelize the Triangular Band Matrix Algorithm and get a better complexity analysis than for previous parallel algorithms, like the Kannan Bachem Algorithm and the Hartley Hawkes Algorithm. In the part, which is different to the Kannan Bachem Algorithm, the Triangular Band Matrix Algorithm leads to a better efficiency and smaller execution times, even for large example matrices.

Place, publisher, year, edition, pages
IEEE Press, 2004.
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-84346OAI: oai:DiVA.org:umu-84346DiVA: diva2:683139
Conference
6th Workshop on Advances in Parallel and Distributed Computation Models, International Parallel and Distributed Processing Symposium (IPDPS 2004)
Available from: 2014-01-02 Created: 2014-01-02 Last updated: 2014-03-25Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Jäger, Gerold
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 143 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf