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
Parallel Algorithms for Computing the Smith Normal Form of Large Matrices
Mathematisches Seminar der Christian-Albrechts-Universität zu Kiel, Germany.
2003 (English)In: Proceedings of 10th European PVM/MPI 2003 / [ed] J. Dongarra, D. Laforenza, S. Orlando, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2003, 170-179 p.Conference paper, Published paper (Refereed)
Abstract [en]

Smith normal form computation has many applications in group theory, module theory and number theory. As the entries of the matrix and of its corresponding transformation matrices can explode during the computation, it is a very difficult problem to compute the Smith normal form of large dense matrices. The computation has two main problems: the high execution time and the memory requirements, which might exceed the memory of one processor. To avoid these problems, we develop two parallel Smith normal form algorithms using MPI. These are the first algorithms computing the Smith normal form with corresponding transformation matrices, both over the rings Z and F[x]. We show that our parallel algorithms both have a good efficiency, i.e. by doubling the processes, the execution time is nearly halved, and succeed in computing the Smith normal form of dense example matrices over the rings Z and F2[x] with more than thousand rows and columns.

Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer Berlin/Heidelberg, 2003. 170-179 p.
Series
Lecture Notes in Computer Science, Volume 2840
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-84345OAI: oai:DiVA.org:umu-84345DiVA: diva2:683134
Conference
10th European PVM/MPI 2003
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: 40 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