Change search
ReferencesLink to record
Permanent link

Direct link
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 (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.
, Lecture Notes in Computer Science, Volume 2840
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-84345OAI: diva2:683134
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
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

Total: 10 hits
ReferencesLink to record
Permanent link

Direct link