Change search
ReferencesLink to record
Permanent link

Direct link
Efficient parallelizations of Hermite and Smith normal form algorithms
Computer Science Institute, University of Halle-Wittenberg, D-06120 Halle (Saale), Germany.
denkwerk, Vogelsanger Straße 66, D-50823 Köln, Germany.
2009 (English)In: Parallel Computing, ISSN 0167-8191, Vol. 35, no 6, 345-357 p.Article in journal (Refereed) Published
Abstract [en]

Hermite and Smith normal form are important forms of matrices used in linear algebra. These terms have many applications in group 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 Hermite and Smith normal form of large dense matrices. The main problems of the computation are the large execution times and the memory requirements which might exceed the memory of one processor. To avoid these problems, we develop parallelizations of Hermite and Smith normal form algorithms. These are the first parallelizations of algorithms for computing the normal forms with corresponding transformation matrices, both over the rings Z and F[x]. We show that our parallel versions have good efficiency, i.e., by doubling the processes, the execution time is nearly halved. Furthermore, they succeed in computing normal forms of dense large example matrices over the rings Q[x], F3[x], and F5[x].

Place, publisher, year, edition, pages
Elsevier, 2009. Vol. 35, no 6, 345-357 p.
Keyword [en]
Hermite normal form, Smith normal form, parallelization
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-82324DOI: 10.1016/j.parco.2009.01.003OAI: diva2:660504
Available from: 2013-10-30 Created: 2013-10-30 Last updated: 2013-11-05Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jäger, Gerold
In the same journal
Parallel Computing
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 1238 hits
ReferencesLink to record
Permanent link

Direct link